CF1759G

Description

{a}为一个n个数排列，$\mathrm{给}n\mathrm{/}2\mathrm{个}\mathrm{数}给n\; /\; 2个数${$bb$},$b_i\mathrm{表}\mathrm{示}max(a_{2i-1},a_{2i})b\_i表示max(a\_\{2i\; -\; 1\},a\_\{2i\})$

求字典序最小的{a}

sample

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 

Solution

每次需要选一个数放到$b_{i}b\_i$前，需要保证后面的$b_{i}b\_i$有比他小的数可选，且每次选的数尽量小（后面的数选的数尽量大）。

用set 1.判重，2. 二分查找 ，， 从后往前选，每次选刚好比他小的数。

code

int T,n,a[200010];

int main(){
	cin >> T;
	while(T--){
		set<int> s;
		cin >> n;
		bool yo = 1;
		rep(i,1,n)s.insert(i);
		rep(i,1,n / 2){
			rd(a[i * 2 ]);
			yo &= s.count(a[i * 2]);
			s.erase(a[i * 2]);
		}
		
		if(!yo){
			puts("-1");
			continue;
		}
		
		per(i,n / 2,1){
			auto it = s.lower_bound(a[i * 2]);
			if(it == s.begin()){
				yo = 0;
				break;
			}
			a[2 * i - 1] = *--it;
			s.erase(it);
		}
		if(!yo){
			puts("-1");
			continue;
		}
		else rep(i,1,n)printf("%d ",a[i]);
		printf("\n");
	}
	return 0;
}