#PU1421. USACO 2024 US Open Contest, Bronze — Problem 3. Farmer John's Favorite Permutation
USACO 2024 US Open Contest, Bronze — Problem 3. Farmer John's Favorite Permutation
USACO 2024 US Open Contest, Bronze — Problem 3. Farmer John's Favorite Permutation
题目描述
Farmer John has a permutation of length (, containing each positive integer from to exactly once. However, Farmer Nhoj has broken into FJ's barn and disassembled . To not be too cruel, FN has written some hints that will help FJ reconstruct . While there is more than one element remaining in , FN does the following: Let the remaining elements of be , If , he writes down and removes from the permutation. Otherwise, he writes down and removes from the permutation. At the end, Farmer Nhoj will have written down integers , in that order. Given , Farmer John wants to enlist your help to reconstruct the lexicographically minimum consistent with Farmer Nhoj's hints, or determine that Farmer Nhoj must have made a mistake. Recall that if you are given two permutations and , is lexicographically smaller than if at the first position where the two differ.
输入格式
Each input consists of independent test cases (). Each test case is described as follows: The first line contains . The second line contains integers ().
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5
2
1
2
2
4
1 1 1
4
2 1 1
4
3 2 1
1 2
-1
-1
3 1 2 4
1 2 3 4
For 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]
提示
is lexiocgraphically smaller. For the second test case, there is no consistent with ; both and would produce , not .