#P17887. Classement Nationale

Classement Nationale

有 nn 名运动员和按时间排列的 mm 场比赛。运动员 11 可以选择跳过自己原本参加的任意一些比赛。其他人的参赛安排和比赛用时均不变。求这样可以得到的运动员 11 在最后一场比赛所在日结束后的所有不同评级,按严格递减顺序输出。

下面完整定义评级系统。比赛 jj 的日期为 djd_j,特殊标记为 sj∈{0,1}s_j\in\{0,1\}。运动员 ii 的初始评级为 CNi,baseCN_{i,\mathrm{base}},在时刻 tt 的评级记为 CNi,tCN_{i,t}。比赛用时 Ri,j=0R_{i,j}=0 表示被取消资格(DSQ),否则用时越小名次越好。

每年固定为 365 天,第一个年份为 [0,365)[0,365),第二个为 [365,730)[365,730),依此类推。第一年的归一化系数 Knorm=10000K_{\mathrm{norm}}=10000。

一场比赛如何产生记录

处理日期为 djd_j 的比赛时,先查询所有参赛者在 dj−15d_j-15 日的评级。

设未被取消资格的人数为 FjF_j,令

Ninfl=max⁡(3,⌊2Fj/3⌋).N_{\mathrm{infl}}=\max(3,\lfloor2F_j/3\rfloor).

若 Fj<NinflF_j<N_{\mathrm{infl}},这场比赛不计评级,任何参赛者都不产生记录,包括 DSQ 记录。

否则,将未被取消资格者按用时递增排序;用时相同时,15 天前评级较高的人在前。记排序后的运动员为 Pos1,…,PosFj\mathrm{Pos}_1,\ldots,\mathrm{Pos}_{F_j}。计算

$$\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.$$

每位参赛者新增一条记录,包含日期 djd_j、特殊标记 sjs_j 和表现分:

$$\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}$$

如何由历史记录计算评级

查询运动员 ii 在 tt 日的评级时,只考虑日期处于 (t−365,t](t-365,t] 的记录,其多重集记为 HiH_i。

若 HiH_i 为空:截至 tt 从未产生过任何记录,则评级仍为初始评级;曾有记录但现在全部过期,则评级为 00。

若 HiH_i 非空,令

h=min⁡(max⁡(⌊0.4∣Hi∣⌋,4),∣Hi∣).h=\min(\max(\lfloor0.4|H_i|\rfloor,4),|H_i|).

从中取最大的至多 hh 个非负表现分,得到多重集 SS;表现分相同时优先取特殊比赛的记录。

复制 SS 得到 S′S'。若 ∣S∣>1|S|>1 且最高分对应的记录中没有特殊比赛,则从 S′S' 删除一个最高分;否则不删除。特别地,∣S∣≤1|S|\le1 时不删除。

令 avg\mathrm{avg} 为 S′S' 的平均分,S′S' 为空时取 00。若 ∣S∣<4|S|<4,每少一场施加 2%2\% 的扣减;如果 HiH_i 含 DSQ 记录,扣减比例减少 22 个百分点,最低为 00。注意,扣减比例按删除最高分之前的 ∣S∣|S| 计算,DSQ 次数不影响减免幅度。

设最终扣减比例为 p%p\%,则

$$CN_{i,t}=\left\lfloor\mathrm{avg}\cdot\frac{100-p}{100}\right\rfloor.$$

平均与扣减过程中不提前取整,只在这个表达式最后向下取整一次。

跨年处理

在正整数 tt 满足 t≡0(mod365)t\equiv0\pmod{365} 的当天,处理任何比赛之前,计算

M=max⁡iCNi,t−1.M=\max_i CN_{i,t-1}.

若 M=0M=0,新的 Knorm=10000K_{\mathrm{norm}}=10000;否则新的 Knorm=MK_{\mathrm{norm}}=M。该系数用于接下来的一年。

运动员 11 跳过一场比赛,意味着从该场参赛列表中完全删去他,可能影响该比赛是否计评级、比赛分及后续所有人的评级。允许跳过全部比赛。

输入格式

第一行两个整数 n,mn,m,1≤n,m≤10001\le n,m\le1000。

第二行 nn 个初始评级,均在 [1,12000][1,12000]。

第三行 mm 个比赛日期,1≤dj≤20001\le d_j\le2000,且 dj≤dj+1d_j\le d_{j+1}。

第四行 mm 个特殊标记,均为 00 或 11。

随后依次给出每位运动员的参赛信息。先输入一个整数 nin_i,0≤ni≤100\le n_i\le10;接下来 nin_i 行各包含比赛编号 bjb_j 和用时 Ri,bjR_{i,b_j}。其中 1≤bj≤m1\le b_j\le m,用时为 00 或 [600,9000][600,9000] 内的整数。同一运动员的比赛编号互不相同,输入顺序不一定按日期排列。

输出格式

第一行输出不同最终评级的数量 cc。接下来 cc 行按严格递减顺序输出这些评级。

样例

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

第一组中,跳过全部比赛得到初始评级 62006200;只参加第 90 天的第一场比赛,其记录在第 464 天已经过期,得到 00。