分数: 266 分
问题陈述
高桥是该大学奖学金评选委员会的成员。今年,有 N 奖学金的类型,对于每一种奖学金,必须从申请的学生中确定获奖者。
大学有 M 申请人、申请人 j (1 \leq j \leq M) 已分配评估分数 P_j 基于他们的学业表现。评估分数对于每个申请人来说是一个固定值,值越高意味着评估越高。不同的申请人有可能具有相同的评估分数。
单个申请人可以申请多项奖学金。由于每项奖学金的获得者都是独立确定的,因此单个申请人可能会获得多项奖学金。
每项奖学金 i (1 \leq i \leq N), 申请人编号 给出了申请该奖学金的 C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} 的 K_i 申请人。收件人由以下规则确定:
- 如果没有申请人(K_i = 0),该奖学金没有获得者。
- 如有申请者,评价分数最高的申请者获得奖学金。如果评估分数最高的申请人有多个,则由其中申请人数最少的申请人获得。
对于每项奖学金,确定最终获得该奖学金的人的申请人编号。如果没有接收者,则输出 0.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq P_j \leq 10^9 (1 \leq j \leq M)
- 0 \leq K_i \leq M (1 \leq i \leq N)
- 1 \leq C_{i,k} \leq M (1 \leq i \leq N, 1 \leq k \leq K_i)
- 同一申请人不会多次获得同一奖学金(C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} 是不同的)
- \displaystyle \sum_{i=1}^{N} K_i \leq 2 \times 10^5
- 所有输入值均为整数
输入
N M
P_1 P_2 \ldots P_M
K_1 C_{1,1} C_{1,2} \ldots C_{1,K_1}
K_2 C_{2,1} C_{2,2} \ldots C_{2,K_2}
\vdots
K_N C_{N,1} C_{N,2} \ldots C_{N,K_N}
- 第一行包含一个整数 N 代表奖学金类型的数量和一个整数 M 代表申请人数,以空格分隔。
- 第二行包含整数 P_1, P_2, \ldots, P_M 代表每个申请人的评价分数,以空格分隔。 P_j 代表申请者的评价分数 j.
- 的 (2 + i)第行 (1 \leq i \leq N) 包含有关申请奖学金的学生的信息 i。首先,一个整数 K_i 表示申请人数,后跟整数 C_{i,1}, C_{i,2}, \ldots, C_{i,K_i} 代表申请人编号,以空格分隔。如果 K_i = 0,仅 该行给出了 K_i 。
输出
输出 N 行。的 i第行 (1 \leq i \leq N) 应包含获得奖学金者的申请人编号 i。如果没有接收者,则输出 0.
示例输入 1
3 4 100 80 100 90 2 1 2 3 2 3 4 0
示例输出 1
1 3 0
示例输入 2
5 6 50 50 50 30 70 70 3 1 2 3 2 5 6 4 1 4 5 6 1 4 0
示例输出 2
1 5 5 4 0
示例输入 3
8 10 1000000000 999999999 500000000 750000000 1000000000 250000000 750000000 100000000 999999999 500000000 5 1 2 3 4 5 3 6 7 8 4 2 5 9 10 0 2 1 5 6 1 2 3 4 5 6 1 8 10 1 2 3 4 5 6 7 8 9 10
示例输出 3
1 7 5 0 1 1 8 1