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

[TJOI2019] 甲苯先生的滚榜

题目描述

甲苯先生在制作一个 Online Judge,他发现做比赛的人们很关心自己的排名(显而易见)。

在 ACM 赛制的比赛中,如果通过题目数量不相等,则通过题目数量多的人排名更靠前;
如果通过题目数量相等,则罚时更少的人排名更高。

甲苯先生想让大家帮忙设计一个程序,每次有人通过之后,就告诉他排名在他的前面有多少人。
(不包括和他罚时题数都相同的同学)

输入格式

第一行输入一个整数 TT 表示测试样例的个数。

对于每一个样例,输入三个整数 m,n,seedm, n, \text{seed}
mm 表示参赛总人数(编号 1m1 \sim m),nn 表示一共有 nn 次 AC(假设 AC 已经去重,即不存在相同人的相同题目提交)。
seed\text{seed} 表示生成数据的种子。

接下来要求同学们使用之下的函数生成数据:

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

last\texttt{last} 为上一次输出的结果,在没有输出结果时 last=7\texttt{last} = 7,多组数据时 last\texttt{last} 不需要重新赋值)
要求每次生成两个数据 Ria,Rib\texttt{Ria}, \texttt{Rib},表示第 Ria\texttt{Ria} 个人 AC 了一道题目,他的罚时为 Rib\texttt{Rib}
(也就是说 Ria\texttt{Ria} 的题目数量 +1+1,罚时长度 +Rib+\texttt{Rib})。

要求一共生成 nn 组数据,代表一共有 nn 次提交。

对于所有数据,保证罚时总和不超过 1.5×1061.5\times 10^6

输出格式

每次提交输出一行整数,表示在第 Ria\texttt{Ria} 个人 AC 后,比 Ria\texttt{Ria} 成绩高的有多少个选手。

1
7 3 1

0
1
0

提示

测试点# 1, 2 3, 4 5 6, 7, 8 9, 10
TT 10\le10 5\le5 15\le15 5\le5
mm 1000\le1000 10000\le10000 105\le10^5 104\le10^4 105\le10^5
nn 106\le10^6