Declining Invitations
골드 I의견: 0
\(N\) contestants participated in a contest, each placing a distinct rank from \(1\)
to \(N\). There are \(C\) criteria used to invite contestants to participate in the
final round, and the \(i\)th-ranked contestant satisfies a specified \(n_i\) of them
(\(1\le n_i\le C\)).
The invitation process runs as follows. First, the top \(f_1\) students who
satisfy the \(1\)st criteria will be invited. Then, out of all students who
haven't yet been invited, the top \(f_2\) (or all remaining if there are fewer
than \(f_2\) remaining) students who satisfy the \(2\)nd criterion will be invited.
This process repeats, for each \(i\) from \(1\) to \(C\)
(\(1\le f_i\le N\)).
However, some contestants will decline to participate in the final round, in
which case they will be ignored when determining who to invite.
You are given a permutation \(p_1, p_2, \dots, p_N\) of \(1\dots N\). For each \(i\)
from \(0\) to \(N-1\), determine the sum of the ranks of the contestants who will be
invited if the participants with ranks given by the first \(i\) elements of \(p\)
decline to attend.
Problem credits: Benjamin Qi
SCORING
- Inputs 4-6: \(N, C \le 10^3, \sum n_i \le 10^4\)
- Inputs 7-8: \(C=1\)
- Inputs 9-10: \(C=2\)
- Inputs 11-16: No additional constraints.
Problem credits: Benjamin Qi
The first line contains \(N\) and \(C\) (\(1\le N,C\le 10^5\)).
The next line contains \(f_1,f_2, \dots, f_C\).
The next line contains \(p_1, \dots, p_N\).
The next \(N\) lines each contain \(n_i\) (\(1\le n_i\le C\)), followed by \(n_i\)
distinct integers in \([1, C]\), representing the criteria that the \(i\)th-ranked
contestant satisfies. It is guaranteed that \(\sum n_i\le 10^6\).
Output \(N\) lines, the sum of ranks of invitees before each declination.
5 1
3
5 1 3 2 4
1 1
1 1
1 1
1 1
1 16
6
9
6
4There is only one criterion. The top three remaining contestants who have not
declined will be invited.
5 4
1 1 1 1
1 2 3 4 5
1 1
2 1 2
2 2 3
2 3 4
1 410
14
12
9
5Initially, the \(i\)th contestant gets invited under criterion \(i\) for all
\(1\le i\le 4\).
After the first declination, the \(i+1\)th contestant gets invited under criterion
\(i\) for all \(1\le i\le 4\).
6 10
5 6 4 1 3 3 3 6 5 3
1 4 6 5 2 3
1 9
5 4 3 9 5 10
10 6 2 10 1 7 8 3 9 4 5
10 4 5 3 1 2 9 10 6 7 8
2 3 1
8 1 9 7 4 3 10 6 221
20
16
10
5
3riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Second Contest > Silver
평가 및 의견
Declining Invitations
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Declining Invitations