HDUOJ 5096 - ACM Rank

Author Avatar
Jimmy Zhang Jul 29, 2018
  • Read this article on other devices

题面

让我们来为某场 ICPC 比赛写一个排名系统吧!

ICPC 的规则就不再细讲了吧(逃

算了还是简单讲讲吧,首先排名按照 AC 题目顺序由大到小排。如果两队 AC 题目数量相同,则罚时较小的队伍在前。若两队 AC 题目和罚时大小都相同,则两队排名相同。一次未通过的提交会使得该队该题上的罚时额外加 2020 分钟,但只有在该题 AC 后才会被计入总罚时。若该队在某题上第一次提交就 AC 了,则罚时为 AC 时的时间。

这场比赛有 NN 支队伍参加,且包含 MM 道题目。

排名系统会收到三种指令:

1. 提交

格式: S [提交时间]:[队伍 ID]:[题目 ID]:[评测结果]

如果一个队伍重复提交某道他们之前已经 AC 过的题目,或是本次提交据上次有效提交少于 55 分钟,则此次提交会被认定为无效并被系统忽略。否则,系统认定本次提交有效。

2. 依据队伍 ID 查询排名

格式:R [队伍ID]

需要注意的是,如前面所讲,可能出现若干队排名相同的情况。

3. 依据排名查询队伍 ID

格式:T [排名]

如果该排名下由多支队伍,则输出上次 AC 时间最早的队伍。如果所有队伍都没有 AC 题目,则输出 ID 最小的队伍。如果该排名不存在,则输出 1-1

数据范围

比赛时长不会超过 55 小时(300300 分钟)

1N1041 \le N \le 10^4

1M101 \le M \le 10

每次比赛的指令次数不超过 10510^5 次。

题目链接

分析

这种查询排名的题目一看就会勾引我们往平衡树想…… 正巧前天瞎学了学无旋转的 Treap,于是我们就来试试能不能水过这道题吧……

我们可以首先把一个队伍的 AC 题目数量和罚时打包成一个代表分数的结构体,并将其小于和等于符号重载掉。

那么 Treap 上维护什么呢…… 如果我们把每个队伍都当作一个节点放到 Treap 上维护的话,更新队伍的分数是很难做到的。毕竟本蒟蒻只会不带旋转的 Treap,如果要改变某节点的值必须要先将原节点删除然后再插入新节点,这样的话光删除操作就很难实现,所以…… 看起来行不通。

不过我们可以换个思路,考虑一个分数一个节点,然后在每个节点上再套一个 setset 来记录该分数下有哪些队伍。这样就要方便不少。不过这样一来,以某节点为根的子树大小就不再是 leftSon+rightSon+1\text{leftSon} + \text{rightSon} + 1 了,而应该是 leftSon+rightSon+set.size()\text{leftSon} + \text{rightSon} + set.\text{size()}。同时,插入和删除时就变成了先通过 split 操作分离出代表需更新队伍的分数的节点(如果该节点不存在的话就需要新建一个),然后对该节点上的 setset 进行 insert\text{insert} 或者 erase\text{erase} 操作,最后再把它们 merge 回去。setset 内可以根据第三类操作的输出顺序排序,这样在执行第三类操作时直接返回第一个元素就好了。至于很多其它细节,看看参考代码大概就会了。

怎么题面比口胡题解还长啊…… 羞愧 🙈

实现

完整参考代码

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/07/29/hduoj-5096/