2018 우객다교 제4회 J문제 Hash Function(사고+병렬조사집)

제목 설명

Chiaki has just learned hash in today's lesson. A hash function is any function that can be used to map data of arbitrary size to data of fixed size. As a beginner, Chiaki simply chooses a hash table of size n with hash function . Unfortunately, the hash function may map two distinct values to the same hash value. For example, when n = 9 we have h(7) = h(16) = 7. It will cause a failure in the procession of insertion. In this case, Chiaki will check whether the next position  is available or not. This task will not be finished until an available position is found. If we insert {7, 8, 16} into a hash table of size 9, we will finally get {16, -1, -1, -1, -1, -1, -1, 7, 8}. Available positions are marked as -1. After done all the exercises, Chiaki became curious to the inverse problem. Can we rebuild the insertion sequence from a hash table? If there are multiple available insertion sequences, Chiaki would like to find the smallest one under lexicographical order. Sequence a1, a2, ..., an is lexicographically smaller than sequence b1, b2, ..., bn if and only if there exists i (1 ≤ i ≤ n) satisfy that ai < bi and aj = bj for all 1 ≤ j < i.

설명 입력:

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line of each case contains a positive integer n (1 ≤ n ≤ 2 x 105) -- the length of the hash table. 
The second line contains exactly n integers a1,a2,...,an (-1 ≤ ai ≤ 109).
It is guaranteed that the sum of all n does not exceed 2 x 106.

출력 설명:

For each case, please output smallest available insertion sequence in a single line. Print an empty line when the available insertion sequence is empty. If there's no such available insertion sequence, just output -1 in a single line.

예제 1

입력

3
9
16 -1 -1 -1 -1 -1 -1 7 8
4
8 5 2 3
10
8 10 -1 -1 34 75 86 55 88 18

출력

7 8 16
2 3 5 8
34 75 86 55 88 18 8 10

제목: 해시 규칙에 따라 해낸 서열을 제시하고 사전 서열의 가장 작은 입력 순서를 제시한다.
사고방식: 우리는 우선 대기열로 사전의 순서를 최소화하고 충돌이 없는 요소에 대해서는 언제든지 놓을 수 있기 때문에 우리는 처음부터 그를 우선 대기열에 넣을 수 있다.
충돌이 있는 원소에 대해서는 그의 위치와 그가 있어야 할 위치(즉%n의 위치) 사이에 원소를 가득 넣었을 때만 놓을 수 있고, 즉 우선 대기열에 눌릴 수 있다.그래서 어떤 원소를 안치한 후에 그의 뒤에 원래 안치할 수 없었던 원소가 그의 안치로 인해 안치할 기회를 얻을 수 있는지.그래서 우리는 배치된 위치의 아버지를 다음 위치의 아버지로 설정하고 보호하는 것을 사용하고 수집한다. 그러면 어떤 원소가 배치될 수 있는지 판단할 때 그와 그가 있어야 할 위치(즉%n의 위치)가 아버지인지 확인하면 된다. 그렇다면 대열에 눌러 넣는다.
코드:

#include
#define mem(a,b) memset(a,b,sizeof(a))
#define mod 1000000007
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const double eps = 1e-12;
const int inf = 0x3f3f3f3f;
map::iterator it;

struct node
{
    int val;
    int pos;
    node(){}
    node (int val,int pos):val(val),pos(pos){}
    friend bool operator < (node x,node y)
    {
    	return x.val> y.val;
	}
};

int n;
int a[maxn],pre[maxn],vis[maxn],ans[maxn];

int find(int x)
{
	return pre[x] == x?x:pre[x] = find(pre[x]);
}

int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		mem(vis,0);
		priority_queue q;
		scanf("%d",&n);
		for(int i = 0;i< n;i++)
			scanf("%d",&a[i]),pre[i] = i;
		
		int num = 0;
		for(int i = 0;i< n;i++)
		{
			if(a[i] == -1) continue;
			if(a[i]%n == i)
			{
				q.push(node(a[i],i));// 
				vis[i] = 1;// 
			}
			num++;
		}
		
		int cnt = 0;
		while(!q.empty())
		{
			node tmp = q.top();
			q.pop();
			ans[++cnt] = tmp.val;
			pre[find(tmp.pos)] = find((tmp.pos+1)%n);// 
			int np = pre[tmp.pos];//np 
			if(vis[np]||a[np] == -1||find(a[np]%n)!= np) continue;//a[np]%n  
			q.push(node(a[np],np));
			vis[np] = 1;
		}
		
		if(cnt< num)
			printf("-1
");
		else if(cnt == 0) printf("
");
		else
		{
			for(int i = 1;i< cnt;i++)
				printf("%d ",ans[i]);
			printf("%d
",ans[cnt]);
		}
	}
	
	return 0;
}