【牛客练习赛50】tokitsukaze and Hash Table

题目描述

tokitsukaze有n个数，需要按顺序把他们插入哈希表中，哈希表的位置为0到n-1。
插入的规则是：
刚开始哈希表是空的。
对于一个数 $x$x，在哈希表中，如果(x mod n)的位置是空的，就把x放在(x mod n)的位置上。如果不是空的，就从(x mod n)往右开始找到第一个空的位置插入。若一直到 $n-1$n−1都不是空的，就从位置 $0$0开始继续往右找第一个空的位置插入。
因为哈希表总共有 $n$n个空位，需要插入 $n$n个数，所以每个数都能被插入。
现在tokitsukaze想知道把这 $n$n个数按顺序插入哈希表后，哈希表中的每个位置分别对应的是哪个数。

输入描述:

第一行包含一个正整数 $n$n( $1\le n\le 10^6$1≤n≤106)。
第二行包含 $n$n个非负整数 $x$x( $0\le x\le 10^9$0≤x≤109)，这些数按从左到右的顺序依次插入哈希表。

输出描述:

输出一行，n个数，第i个数表示哈希表中位置为i所对应的数。( $0\le i\le n-1$0≤i≤n−1)

示例1

输入

1 2 6 5

输出

5 1 2 6

说明
插入1时，1 mod 4=1，是空的，在位置1插入。
插入2时，2 mod 4=2，是空的，在位置2插入。
插入6时，6 mod 4=2，不是空的，找到下一个空的位置为3，所以在位置3插入。
插入5时，5 mod 4=1，不是空的，找到下一个空的位置为0，所以在位置0插入。

示例2

输入

4
3 0 7 11

输出

0 7 11 3

说明
插入3时，3 mod 4=3，是空的，在位置3插入。
插入0时，0 mod 4=0，是空的，在位置0插入。
插入7时，7 mod 4=3，不是空的，找到下一个空的位置为1，所以在位置1插入。
插入11时，11 mod 4=3，不是空的，找到下一个空的位置为2，所以在位置2插入。

Solution

并查集维护每个位置应放在哪即可

#include <cstdio>

using namespace std;

int n, f[1000010], ans[1000010];

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

int main()
{
	scanf("%d", &n);
	for (int i = 0; i <= n; i++)
		f[i] = i;
	for (int i = 1; i <= n; i++)
	{
		int t, s; scanf("%d", &t); s = t;
		t %= n;
		if (find(t) < n)
		{
			ans[find(t)] = s;
			f[find(t)] = find(find(t) + 1);
		}
		else
		{
			ans[find(0)] = s;
			f[find(t)] = f[find(0)] = find(find(0) + 1);
		}
	}
	for (int i = 0; i < n; i++)
		printf("%d ", ans[i]);
	
	return 0;
}