https://codeforces.com/problemset/problem/1759/G
输入 T(≤1e4) 表示 T 组数据。所有数据的 n 之和 ≤2e5。
每组数据输入偶数 n(2≤n≤2e5) 和长为 n/2 的数组 b(1≤b[i]≤n),下标从 1 开始。
构造一个长为 n 的 1~n 的排列 p(下标从 1 开始),满足 max(p[2i-1],p[2i]) = b[i]。
如果无法构造,输出 -1,否则输出字典序最小的 p。
输入
6
6
4 3 6
4
2 4
8
8 7 2 3
6
6 4 2
4
4 4
8
8 7 4 5
输出
1 4 2 3 5 6
1 2 3 4
-1
5 6 3 4 1 2
-1
1 8 6 7 2 4 3 5
倒序遍历找到小于b[i]的最大且没有被使用过的数
并查集能快速判断 如果一个数s被使用了,那么它的祖先指向s - 1的祖先
#include <bits/stdc++.h>
using namespace std;
vector<int> p;
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
void solve()
{
int n;
cin >> n;
vector<int> ans(2 * n + 1), b(n + 1);
p.resize(n + 1);
vector<bool> st(n + 1, false);
for(int i = 0; i <= n; i ++) p[i] = i;
for(int i = 1; i <= n / 2; i ++){
cin >> b[i];
int pb = find(b[i]), pa = find(b[i] - 1);
p[pb] = pa;
}
bool ok = true;
for(int i = n / 2; i >= 1; i --){
if(st[b[i]]){
ok = false;
break;
}
ans[i * 2] = b[i];
st[b[i]] = true;
int t = find(b[i] - 1);
if(t == 0)
{
ok = false;
break;
}
else{
ans[i * 2 - 1] = t;
st[t] = true;
p[t] = find(t - 1);
}
}
if(ok){
for(int i = 1; i <= n; i ++){
cout << ans[i] << ' ';
}
cout << endl;
}
else puts("-1");
}
int main ()
{
int T;
cin >> T;
while(T --){
solve();
}
return 0;
}