레이팅 미적용농부 존은 \(1\)부터 \(N\)까지의 각 양의 정수를 정확히 한 번씩 포함하는 길이 \(N\)(\(2 \leq N \leq 10^5\))의 순열 \(p\)를 가지고 있다. 그런데 농부 은조이가 존의 헛간에 침입해 \(p\)를 분해해 버렸다. 너무 잔인하지는 않도록, 은조이는 존이 \(p\)를 복원하는 데 도움이 될 힌트를 남겨 두었다. \(p\)에 원소가 두 개 이상 남아 있는 동안, 은조이는 다음을 반복한다.
\(p\)에 남아 있는 원소들을 \(p'_1, p'_2, \dots , p'_n\)이라 하자.
- \(p'_1 > p'_n\)이면, \(p'_2\)를 적고 \(p'_1\)을 순열에서 제거한다.
- 그렇지 않으면, \(p'_{n-1}\)을 적고 \(p'_n\)을 순열에서 제거한다.
결국 농부 은조이는 \(N - 1\)개의 정수 \(h_1, h_2, \dots, h_{N-1}\)을 이 순서대로 적게 된다. \(h\)가 주어졌을 때, 농부 존은 은조이의 힌트와 모순되지 않는 사전순으로 가장 작은 \(p\)를 복원하거나, 은조이가 실수를 했음이 분명하다고 판단하고 싶다. 두 순열 \(p\)와 \(p'\)가 주어졌을 때, 두 순열이 처음으로 달라지는 위치 \(i\)에서 \(p_i < p'_i\)이면 \(p\)가 \(p'\)보다 사전순으로 작다는 것을 기억하자.
문제 제공: Chongtian Ma
배점
- 입력 2: \(N\le 8\)
- 입력 3-6: \(N\le 100\)
- 입력 7-11: 추가 제약 없음.
문제 제공: Chongtian Ma
각 입력은 \(T\)개의 독립적인 테스트 케이스로 이루어진다 (\(1\le T\le 10\)). 각 테스트 케이스는 다음과 같이 주어진다.
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 \(N - 1\)개의 정수 \(h_1, h_2, \dots, h_{N-1}\)이 주어진다 (\(1\le h_i\le N\)).
테스트 케이스마다 한 줄씩, 총 \(T\)개의 줄을 출력한다.
\(h\)와 모순되지 않는 \(1\dots N\)의 순열 \(p\)가 존재하면, 그중 사전순으로 가장 작은 \(p\)를 출력한다. 그러한 \(p\)가 존재하지 않으면 \(-1\)을 출력한다.
5
2
1
2
2
4
1 1 1
4
2 1 1
4
3 2 11 2
-1
-1
3 1 2 4
1 2 3 4For the fourth test case, if \(p=[3,1,2,4]\) then FN will have written down
\(h=[2,1,1]\).
p' = [3,1,2,4]
p_1' < p_n' -> h_1 = 2
p' = [3,1,2]
p_1' > p_n' -> h_2 = 1
p' = [1,2]
p_1' < p_n' -> h_3 = 1
p' = [1]
Note that the permutation \(p=[4,2,1,3]\) would also produce the same \(h\), but
\([3,1,2,4]\) is lexiocgraphically smaller.
For the second test case, there is no \(p\) consistent with \(h\); both \(p=[1,2]\)
and \(p=[2,1]\) would produce \(h=[1]\), not \(h=[2]\).
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > US Open > Bronze