B.Box

题目：盒子##

题目：排列p是一个整数序列 p = [p1, p2,...,pn]，由n个唯一的正整数组成
唯一的线索是你需要打开上锁的盒子
你只知道前缀的最大数，q1, q2, ..., qn，保证qi <= qi+1例如
q1 = p1
q2 = max(p1, p2)
q3 = max(p1, p2, p3)
...
qn = max(p1, p2, ..., pn)

你需要构造任意合适的序列

分析：显然，如果qi不等于qi+1，那么pi = qi，因为qi <= qi+1，假设q0 = 0，其它位置的数可以被填充为从左到右增加的序列，构造完后检查构造的序列即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
 
using namespace std;
int t;
const int N = 100005;
int p[N];
int secret[N];//构造好的秘密
vector<int> v;
bool used[N];
int main()
{
	scanf("%d", &t);
 
	while (t--)
	{
		int n;
		bool flag = false;
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i)
		{
			scanf("%d", &p[i]);
		}
 
		secret[1] = p[1];
		used[p[1]] = true;
		for (int i = 2; i <= n; ++i)
		{
			if (p[i] != p[i - 1])
			{
				secret[i] = p[i];
				used[p[i]] = true;
			}
		}
 
		for (int i = 1; i <= n; ++i)
		{
			if (!used[i])
				v.push_back(i);
		}
 
		for (int i = 1, j = 0; i <= n; ++i)
		{
			if (!secret[i])
			{
				int t = v[j];
				if(t <= p[i])
				  secret[i] = v[j++];
				else
				{
					flag = true;
					break;
				}
			}
		}
		
		if (!flag)
		{
			for (int i = 1; i <= n; ++i)
			{
				printf("%d ", secret[i]);
			}
 
			printf("
");
		}
		else {
			puts("-1");
		}
		v.clear();
		memset(used, 0, sizeof used);
		memset(p, 0, sizeof p);
		memset(secret, 0, sizeof secret);
	
	}
 
 
 
 
	return 0;
}