P5338 [TJOI2019] 甲苯先生的滚榜
题目描述
甲苯先生正在制作一个 Online Judge,他发现参加比赛的人们很关心自己的排名。
在 ACM 赛制的比赛中,排名规则如下:
∙通过题目数量多的人排名更靠前;
∙通过题目数量相同时,罚时更少的人排名更靠前。
一共有 m 名选手,编号为 1∼m,初始时每名选手通过题目数量与罚时均为 0。一共有 n 次 AC(已经去重,即不存在同一名选手对同一道题目的重复提交)。甲苯先生希望你在每次有人通过一道题目之后,告诉他有多少名选手的成绩严格优于这名选手(通过题目数量与罚时都相同的选手不计入其中)。
输入格式
每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦15) 代表数据组数,每组测试数据描述如下:
在一行上输入三个整数 $m, n, \mathrm{seed} \left(1 \leqq m \leqq 10^5;\ 1 \leqq n \leqq 10^6;\ 0 \leqq \mathrm{seed} < 2^{32}\right)$,分别代表参赛人数、AC 次数与生成数据的种子。
接下来使用下面的函数生成数据:
typedef unsigned int ui ;
ui randNum( ui& seed , ui last , const ui m){
seed = seed * 17 + last ; return seed % m + 1;
}
其中参数与返回值均为 32 位无符号整数,乘法与加法都按 232 取模。
每次 AC 依次调用两次该函数,得到 Ria 与 Rib:
∙第一次调用得到 $\mathrm{Ria} \left(1 \leqq \mathrm{Ria} \leqq m\right)$,代表本次 AC 的选手编号;
∙第二次调用得到 $\mathrm{Rib} \left(1 \leqq \mathrm{Rib} \leqq m\right)$,代表这名选手本次的罚时增量,即他的罚时增加 Rib,同时通过题目数量增加 1。
调用时传入的 last 为上一次输出的答案;若此前还没有输出过答案,则 last=7。多组测试数据之间 last 不重置,即沿用上一组最后一次输出的答案。
对于所有数据,保证罚时增量之和不超过 1.5×106。
输出格式
对于每次 AC,新起一行输出一个整数,代表这次 AC 之后成绩严格优于 Ria 的选手数量。所有测试数据的输出按顺序依次给出,组与组之间不额外输出空行。
测试样例
1
7 3 1
0
1
0
样例 1 解释
初始时 last=7,七名选手的通过题目数量与罚时都是 0。三次 AC 的生成过程如下:
∙第 1 次 AC:seed 变为 1×17+7=24,得到 Ria=24mod7+1=4;随后 seed 变为 24×17+7=415,得到 Rib=415mod7+1=3。选手 4 通过 1 题、罚时 3,其余选手都是 0 题,故成绩优于他的有 0 人,输出 0,并令 last=0;
∙第 2 次 AC:seed 变为 415×17+0=7055,得到 Ria=7055mod7+1=7;随后 seed 变为 7055×17+0=119935,得到 Rib=119935mod7+1=5。选手 7 通过 1 题、罚时 5,而选手 4 同样通过 1 题但罚时 3 更少,故成绩优于他的有 1 人,输出 1,并令 last=1;
∙第 3 次 AC:seed 变为 119935×17+1=2038896,得到 Ria=2038896mod7+1=7;随后 seed 变为 2038896×17+1=34661233,得到 Rib=34661233mod7+1=6。选手 7 累计通过 2 题、罚时 11,成绩最好,故成绩优于他的有 0 人,输出 0。
因此依次输出 0,1,0。
2
5 4 7
4 3 100
0
0
1
1
0
0
0
提示
各测试点的数据规模如下(同一列中的测试点规模相同):
| 测试点 |
1,2 |
3,4 |
5 |
6,7,8 |
9,10 |
| T |
≦10 |
≦5 |
≦15 |
≦5 |
| m |
≦103 |
≦104 |
≦105 |
≦104 |
≦105 |
| n |
≦106 |
所有测试数据的罚时增量之和不超过 1.5×106。