#P5338. [TJOI2019] 甲苯先生的滚榜

[TJOI2019] 甲苯先生的滚榜

P5338 [TJOI2019] 甲苯先生的滚榜

题目描述

\hspace{15pt}甲苯先生正在制作一个 Online Judge,他发现参加比赛的人们很关心自己的排名。

\hspace{15pt}在 ACM 赛制的比赛中,排名规则如下:

∙ \hspace{23pt}\bullet\,通过题目数量多的人排名更靠前;

∙ \hspace{23pt}\bullet\,通过题目数量相同时,罚时更少的人排名更靠前。

\hspace{15pt}一共有 mm 名选手,编号为 1∼m1 \sim m,初始时每名选手通过题目数量与罚时均为 00。一共有 nn 次 AC(已经去重,即不存在同一名选手对同一道题目的重复提交)。甲苯先生希望你在每次有人通过一道题目之后,告诉他有多少名选手的成绩严格优于这名选手(通过题目数量与罚时都相同的选手不计入其中)。

输入格式

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T(1≦T≦15)T \left(1 \leqq T \leqq 15\right) 代表数据组数,每组测试数据描述如下:

\hspace{15pt}在一行上输入三个整数 $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 次数与生成数据的种子。

\hspace{15pt}接下来使用下面的函数生成数据:

typedef unsigned int ui ;
ui randNum( ui& seed , ui last , const ui m){ 
    seed = seed * 17 + last ; return seed % m + 1; 
}

\hspace{15pt}其中参数与返回值均为 3232 位无符号整数,乘法与加法都按 2322^{32} 取模。

\hspace{15pt}每次 AC 依次调用两次该函数,得到 Ria\mathrm{Ria} 与 Rib\mathrm{Rib}:

∙ \hspace{23pt}\bullet\,第一次调用得到 $\mathrm{Ria} \left(1 \leqq \mathrm{Ria} \leqq m\right)$,代表本次 AC 的选手编号;

∙ \hspace{23pt}\bullet\,第二次调用得到 $\mathrm{Rib} \left(1 \leqq \mathrm{Rib} \leqq m\right)$,代表这名选手本次的罚时增量,即他的罚时增加 Rib\mathrm{Rib},同时通过题目数量增加 11。

\hspace{15pt}调用时传入的 last\mathrm{last} 为上一次输出的答案;若此前还没有输出过答案,则 last=7\mathrm{last} = 7。多组测试数据之间 last\mathrm{last} 不重置,即沿用上一组最后一次输出的答案。

\hspace{15pt}对于所有数据,保证罚时增量之和不超过 1.5×1061.5 \times 10^6。

输出格式

\hspace{15pt}对于每次 AC,新起一行输出一个整数,代表这次 AC 之后成绩严格优于 Ria\mathrm{Ria} 的选手数量。所有测试数据的输出按顺序依次给出,组与组之间不额外输出空行。

测试样例

1
7 3 1
0
1
0

样例 1 解释

\hspace{15pt}初始时 last=7\mathrm{last} = 7,七名选手的通过题目数量与罚时都是 00。三次 AC 的生成过程如下:

∙ \hspace{23pt}\bullet\,第 11 次 AC:seed\mathrm{seed} 变为 1×17+7=241 \times 17 + 7 = 24,得到 Ria=24 mod 7+1=4\mathrm{Ria} = 24 \bmod 7 + 1 = 4;随后 seed\mathrm{seed} 变为 24×17+7=41524 \times 17 + 7 = 415,得到 Rib=415 mod 7+1=3\mathrm{Rib} = 415 \bmod 7 + 1 = 3。选手 44 通过 11 题、罚时 33,其余选手都是 00 题,故成绩优于他的有 00 人,输出 00,并令 last=0\mathrm{last} = 0;

∙ \hspace{23pt}\bullet\,第 22 次 AC:seed\mathrm{seed} 变为 415×17+0=7055415 \times 17 + 0 = 7055,得到 Ria=7055 mod 7+1=7\mathrm{Ria} = 7055 \bmod 7 + 1 = 7;随后 seed\mathrm{seed} 变为 7055×17+0=1199357055 \times 17 + 0 = 119935,得到 Rib=119935 mod 7+1=5\mathrm{Rib} = 119935 \bmod 7 + 1 = 5。选手 77 通过 11 题、罚时 55,而选手 44 同样通过 11 题但罚时 33 更少,故成绩优于他的有 11 人,输出 11,并令 last=1\mathrm{last} = 1;

∙ \hspace{23pt}\bullet\,第 33 次 AC:seed\mathrm{seed} 变为 119935×17+1=2038896119935 \times 17 + 1 = 2038896,得到 Ria=2038896 mod 7+1=7\mathrm{Ria} = 2038896 \bmod 7 + 1 = 7;随后 seed\mathrm{seed} 变为 2038896×17+1=346612332038896 \times 17 + 1 = 34661233,得到 Rib=34661233 mod 7+1=6\mathrm{Rib} = 34661233 \bmod 7 + 1 = 6。选手 77 累计通过 22 题、罚时 1111,成绩最好,故成绩优于他的有 00 人,输出 00。

\hspace{15pt}因此依次输出 0,1,00, 1, 0。

2
5 4 7
4 3 100
0
0
1
1
0
0
0

提示

\hspace{15pt}各测试点的数据规模如下(同一列中的测试点规模相同):

测试点 1,21, 2 3,43, 4 55 6,7,86, 7, 8 9,109, 10
TT ≦10\leqq 10 ≦5\leqq 5 ≦15\leqq 15 ≦5\leqq 5
mm ≦103\leqq 10^3 ≦104\leqq 10^4 ≦105\leqq 10^5 ≦104\leqq 10^4 ≦105\leqq 10^5
nn ≦106\leqq 10^6

\hspace{15pt}所有测试数据的罚时增量之和不超过 1.5×1061.5 \times 10^6。