Farmer John's Favorite Permutation
브론즈 II의견: 0
Farmer John has a permutation \(p\) of length \(N\) (\(2 \leq N \leq 10^5)\),
containing each positive integer from \(1\) to \(N\) exactly once. However, Farmer
Nhoj has broken into FJ's barn and disassembled \(p\). To not be too cruel, FN has
written some hints that will help FJ reconstruct \(p\). While there is more than
one element remaining in \(p\), FN does the following:
Let the remaining elements of \(p\) be
\(p'_1, p'_2, \dots , p'_n\),
- If \(p'_1 > p'_n\), he writes down \(p'_2\) and removes \(p'_1\) from the permutation.
- Otherwise, he writes down \(p'_{n-1}\) and removes \(p'_n\) from the permutation.
At the end, Farmer Nhoj will have written down \(N - 1\) integers
\(h_1, h_2, \dots, h_{N-1}\), in that order. Given \(h\), Farmer John wants to
enlist your help to reconstruct the lexicographically minimum \(p\) consistent
with Farmer Nhoj's hints, or determine that Farmer Nhoj must have made a
mistake. Recall that if you are given two permutations \(p\) and \(p'\),
\(p\) is lexicographically smaller than \(p'\) if \(p_i < p'_i\) at the first
position \(i\) where the two differ.
Problem credits: Chongtian Ma
SCORING
- Input 2: \(N\le 8\)
- Inputs 3-6: \(N\le 100\)
- Inputs 7-11: No additional constraints.
Problem credits: Chongtian Ma
Each input consists of \(T\) independent test cases (\(1\le T\le 10\)). Each test
case is described as follows:
The first line contains \(N\).
The second line contains \(N - 1\) integers \(h_1, h_2, \dots, h_{N-1}\)
(\(1\le h_i\le N\)).
Output \(T\) lines, one for each test case.
If there is a permutation \(p\) of \(1\dots N\) consistent with \(h\), output the
lexicographically smallest such \(p\). If no such \(p\) exists, output \(-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
평가 및 의견
Farmer John's Favorite Permutation
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Farmer John's Favorite Permutation