#P17887. Classement Nationale
Classement Nationale
有 名运动员和按时间排列的 场比赛。运动员 可以选择跳过自己原本参加的任意一些比赛。其他人的参赛安排和比赛用时均不变。求这样可以得到的运动员 在最后一场比赛所在日结束后的所有不同评级,按严格递减顺序输出。
下面完整定义评级系统。比赛 的日期为 ,特殊标记为 。运动员 的初始评级为 ,在时刻 的评级记为 。比赛用时 表示被取消资格(DSQ),否则用时越小名次越好。
每年固定为 365 天,第一个年份为 ,第二个为 ,依此类推。第一年的归一化系数 。
一场比赛如何产生记录
处理日期为 的比赛时,先查询所有参赛者在 日的评级。
设未被取消资格的人数为 ,令
若 ,这场比赛不计评级,任何参赛者都不产生记录,包括 DSQ 记录。
否则,将未被取消资格者按用时递增排序;用时相同时,15 天前评级较高的人在前。记排序后的运动员为 。计算
$$\mathrm{RaceScore}_j=\left\lfloor\frac{10000\sum_{p=1}^{N_{\mathrm{infl}}} R_{\mathrm{Pos}_p,j}CN_{\mathrm{Pos}_p,d_j-15}}{N_{\mathrm{infl}}K_{\mathrm{norm}}}\right\rfloor.$$每位参赛者新增一条记录,包含日期 、特殊标记 和表现分:
$$\mathrm{Performance}_{i,j}=\begin{cases}-1,&R_{i,j}=0,\\\lfloor\mathrm{RaceScore}_j/R_{i,j}\rfloor,&R_{i,j}>0.\end{cases}$$如何由历史记录计算评级
查询运动员 在 日的评级时,只考虑日期处于 的记录,其多重集记为 。
若 为空:截至 从未产生过任何记录,则评级仍为初始评级;曾有记录但现在全部过期,则评级为 。
若 非空,令
从中取最大的至多 个非负表现分,得到多重集 ;表现分相同时优先取特殊比赛的记录。
复制 得到 。若 且最高分对应的记录中没有特殊比赛,则从 删除一个最高分;否则不删除。特别地, 时不删除。
令 为 的平均分, 为空时取 。若 ,每少一场施加 的扣减;如果 含 DSQ 记录,扣减比例减少 个百分点,最低为 。注意,扣减比例按删除最高分之前的 计算,DSQ 次数不影响减免幅度。
设最终扣减比例为 ,则
$$CN_{i,t}=\left\lfloor\mathrm{avg}\cdot\frac{100-p}{100}\right\rfloor.$$平均与扣减过程中不提前取整,只在这个表达式最后向下取整一次。
跨年处理
在正整数 满足 的当天,处理任何比赛之前,计算
若 ,新的 ;否则新的 。该系数用于接下来的一年。
运动员 跳过一场比赛,意味着从该场参赛列表中完全删去他,可能影响该比赛是否计评级、比赛分及后续所有人的评级。允许跳过全部比赛。
输入格式
第一行两个整数 ,。
第二行 个初始评级,均在 。
第三行 个比赛日期,,且 。
第四行 个特殊标记,均为 或 。
随后依次给出每位运动员的参赛信息。先输入一个整数 ,;接下来 行各包含比赛编号 和用时 。其中 ,用时为 或 内的整数。同一运动员的比赛编号互不相同,输入顺序不一定按日期排列。
输出格式
第一行输出不同最终评级的数量 。接下来 行按严格递减顺序输出这些评级。
样例
3 4
6200 7800 10200
90 100 300 464
1 1 1 1
4
1 1950
2 1940
3 900
4 1800
4
1 1920
2 1800
3 844
4 1800
4
1 1860
2 1670
3 769
4 1800
15
9156
8120
8016
7981
7920
7828
7719
7433
6983
6965
6960
6899
6600
6200
0
6 2
10118 10485 10427 9158 9307 10044
356 365
0 0
2
1 1105
2 791
1
2 960
1
1 929
1
1 841
0
2
1 1043
2 1195
4
11360
10118
8068
7900
第一组中,跳过全部比赛得到初始评级 ;只参加第 90 天的第一场比赛,其记录在第 464 天已经过期,得到 。