레이팅 미적용농부 존은 소들의 새 무리 대장을 뽑으려 한다. 이를 위해 \(N\)마리 (\(2 \leq N \leq 10^5\))의 소를 면접했다. \(i\)번째 지원자를 면접한 뒤, 그 지원자의 리더십 능력과 관련된 \(1\) 이상 \(C\) 이하 (\(1 \leq C \leq 10^9\))의 정수 "소 역량" 점수 \(c_i\)를 매겼다.
너무 많은 소를 면접했기 때문에 농부 존은 모든 소 역량 점수를 기억하지 못한다. 하지만 \(Q\) (\(1 \leq Q < N\))개의 수 쌍 \((a_j, h_j)\)는 기억하는데, 이는 소 \(h_j\)가 소 \(1\)부터 \(a_j\)까지의 모든 소보다 순 크게(strictly greater) 높은 소 역량 점수를 가진 첫 번째 소였다는 뜻이다 (따라서 \(1 \leq a_j < h_j \leq N\)).
농부 존이 수열 \(c_1, \dots, c_N\) (\(c_i = 0\)이면 소 \(i\)의 소 역량 점수를 잊어버렸다는 뜻)과 \(Q\)개의 쌍 \((a_j, h_j)\)를 알려 준다. 이 정보와 모순되지 않는 사전순으로 가장 작은 소 역량 점수 수열을 구하거나, 그런 수열이 존재하지 않음을 판정하여라! 두 점수 수열이 처음으로 달라지는 소에서 더 작은 점수를 부여하는 수열이 사전순으로 더 작은 수열이다.
각 입력은 \(T\) \((1 \leq T \leq 20)\)개의 독립적인 테스트 케이스를 포함한다. 모든 테스트 케이스에 대한 \(N\)의 합이 \(3 \cdot 10^5\)를 넘지 않음이 보장된다.
출제: Suhas Nagar
배점
- 입력 3: \(N \leq 10\), \(Q, C \leq 4\).
- 입력 4-8: \(N \leq 1000\).
- 입력 9-12: 추가 제약 없음.
출제: Suhas Nagar
첫째 줄에 독립적인 테스트 케이스의 개수 \(T\)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.
- 먼저 \(N\), \(Q\), \(C\)가 한 줄에 주어진다.
- 다음 줄에 수열 \(c_1, \dots, c_N\) \((0 \leq c_i \leq C)\)이 주어진다.
- 마지막으로 \(Q\)개의 줄에 각각 쌍 \((a_j, h_j)\)가 주어진다. 한 테스트 케이스 안에서 모든 \(a_j\)는 서로 다름이 보장된다.
각 테스트 케이스마다, 농부 존이 기억하는 정보와 모순되지 않는 사전순으로 가장 작은 소 역량 점수 수열을 한 줄에 출력한다. 그런 수열이 존재하지 않으면 \(-1\)을 출력한다.
1
7 3 5
1 0 2 3 0 4 0
1 2
3 4
4 51 2 2 3 4 4 1We can see that the given output satisfies all of Farmer John's remembered
pairs.
- \(\max(c_1) = 1\), \(c_2 = 2\) and \(1<2\) so the first pair is satisfied
- \(\max(c_1,c_2,c_3) = 2\), \(c_4 = 3\) and \(2<3\) so the second pair is satisfied
- \(\max(c_1,c_2,c_3,c_4) = 3\), \(c_5 = 4\) and \(3<4\) so the third pair is satisfied
There are several other sequences consistent with Farmer John's memory, such as
1 2 2 3 5 4 1
1 2 2 3 4 4 5
However, none of these are lexicographically smaller than the given output.
5
7 6 10
0 0 0 0 0 0 0
1 2
2 3
3 4
4 5
5 6
6 7
8 4 9
0 0 0 0 1 6 0 6
1 3
6 7
4 7
2 3
2 1 1
0 0
1 2
10 4 10
1 2 0 2 1 5 8 6 0 3
4 7
1 2
5 7
3 7
10 2 8
1 0 0 0 0 5 7 0 0 0
4 6
6 91 2 3 4 5 6 7
1 1 2 6 1 6 7 6
-1
1 2 5 2 1 5 8 6 1 3
-1In test case 3, since \(C=1\), the only potential sequence is
1 1
However, in this case, cow 2 does not have a greater score than cow 1, so we
cannot satisfy the condition.
In test case 5, \(a_1\) and \(h_1\) tell us that cow 6 is the first cow to have a
strictly greater score than cows 1 through 4. Therefore, the largest score for
cows 1 through 6 is that of cow 6: 5. Since cow 7 has a score of 7, cow 7 is
the first cow to have a greater score than cows 1 through 6. So, the second
statement that cow 9 is the first cow to have a greater score than cows 1
through 6 cannot be true.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > January > Silver