题面：FJ’s Favorite Permutation B

题目描述

Farmer John 有一个长为 $N$（$2\le N\le 10^5$）的排列 $p$，包含从 $1$ 到 $N$ 的每个正整数恰好一次。然而，Farmer Nhoj 闯入了 FJ 的牛棚并拆散了 $p$。为了不至于太过残忍，FN 写了一些能够帮助 FJ 重建 $p$ 的提示。当 $p$ 中剩余多于一个元素时，FN 会执行以下操作：

令 $p$ 的剩余元素为 $p_1^\prime,p_2^\prime,\ldots,p_n^\prime$，

  • 如果 $p_1^\prime>p_n^\prime$，他写下 $p_2^\prime$ 并从排列中删除 $p_1^\prime$。
  • 否则，他写下 $p_{n−1}^\prime$ 并从排列中删除 $p_n^\prime$。

最终，Farmer Nhoj 将按顺序写下 $N−1$ 个整数 $h_1,h_2,\ldots,h_{N−1}$。给定 $h$，Farmer John 希望得到你的帮助重建与 Farmer Nhoj 的提示相一致的最小字典序 $p$，或者判断 Farmer Nhoj 一定犯了错误。我们知道，给定两个排列 $p$ 和 $p^\prime$，如果在第一个两者不同的位置 $i$ 处有 $p_i<p_i^\prime$，则 $p$ 的字典序小于 $p^\prime$。

输入格式

每个测试点包含 $T$ 个独立的测试用例（$1\le T\le 10$）。每个测试用例的描述如下：

第一行包含 $N$。

第二行包含 $N−1$ 个整数 $h_1,h_2,\ldots,h_{N−1}$（$1\le h_i\le N$）。

输出格式

输出 $T$ 行，每个测试用例一行。

如果存在与 $h$ 相一致的 $1\ldots N$ 的排列 $p$，输出字典顺序最小的 $p$。如果不存在这样的 $p$，输出 $-1$。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
5
2
1
2
2
4
1 1 1
4
2 1 1
4
3 2 1

样例输出 #1

1
2
3
4
5
1 2
-1
-1
3 1 2 4
1 2 3 4

提示

对于第四个测试用例，如果 $p=[3,1,2,4]$ 则 FN 将写下 $h=[2,1,1]$。

1
2
3
4
5
6
7
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]

注意排列 $p=[4,2,1,3]$ 也会产生同样的 $h$，但 $[3,1,2,4]$ 字典序更小。

对于第二个测试用例，不存在与 $h$ 相一致的 $p$；$p=[1,2]$ 和 $p=[2,1]$ 均会产生 $h=[1]$，并非 $h=[2]$。

测试点性质

  • 测试点 $2$：$N\le 8$。
  • 测试点 $3-6$：$N\le 100$。
  • 测试点 $7-11$：没有额外限制。

思路

题目交给我们的生成序列的方式，我们不难注意到一个点，他每次只比较第一个和最后一个的大小，然后把较大的删去。这时候我们就会发现，这是一个排列，也就是说 $1\sim N$ 的数字会且仅会出现一次。那么我们就会发现，这个序列的 $1$ ，会把整个序列的一边硬控，直到只剩下一个数字。

那么我们就不难想到最后一刻，整个序列一定是只会剩下一了。那么最后一次删除前的序列一定是 $[1,x]$ 或者 $[x,1]$ ，这时候，我们就发现题目的第一个性质 $h_{n-1} = 1$ 。如果输入的 $h$ 不满足这个要求，那么是无解的。

那么我们首先就可以确定，至少会有一个数字没有出现，那么这个没有出现的数字，一定是没有被记录就删除了，所以说把它放在边缘是可以的。那么还有一边放什么呢？我们说过一最多出现两次，也就是说，如果一只出现一次，还有一个没出现的数字，刚刚好就是 $n-1$ 个数字，也就是说当一只出现一次的时候，边缘是 1 和一个未出现的数字。那么如果一出现两次呢？那么就说明 $n - 1$ 个数字还有一个是没出现的，这时候也是一样的处理，即当一出现两次的时候，边缘是两个未出现的数字。为什么把未出现的数字安排在边缘呢？因为这两个位置天生不会被记录，这两个位置首先会被排掉一个，另外如果剩下的一边不是一，他还会被小于他的数字排除掉，如果它是一，就会像 $[1,x]$ 或者 $[x,1]$ 这样，被删掉而不被记录。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 1e5 + 10;

int n;
int h[N];

int cnt[N];
int p[N];

inline void Input() {
    read(n);
    for(int i = 1; i < n; i++) {
        read(h[i]);
    }
}

inline void Init() {
    for(int i = 1; i <= n; i++) {
        cnt[i] = 1; p[i] = 0;
    }
    cnt[1] = 2;
    for(int i = 1; i < n; i++) {
        cnt[h[i]]--;
    }
}

inline void Work() {
    if(h[n - 1] != 1) {
        printf("-1\n");
        return ;
    }
    Init();
    for(int i = 1; i <= n; i++) {
        if(cnt[i] < 0 || cnt[i] > 1) {
            printf("-1\n");
            return ;
        }
        if(cnt[i] == 1) {
            if(p[1] == 0) p[1] = i;
            else p[n] = i;
        }
    }
    if(p[1] == 0 || p[n] == 0) {
        printf("-1\n");
        return ;
    }
    int l = 1, r = n;
    for(int i = 1; i < n - 1; i++) {
        if(p[l] > p[r]) p[++l] = h[i];
        else if(p[l] < p[r]) p[--r] = h[i];
    }
    for(int i = 1; i <= n; i++) printf("%d ", p[i]);
    printf("\n");
}

int main() {
    int T = read();
    while(T--) {
        Input();
        Work();
    }
    return 0;
}