← 返回题目列表

Codeforces · 1942/B

B. 贝西和 MEX

中文机器翻译题面 查看原题

Farmer John 有一个排列 $$$p_1, p_2, \ldots, p_n$$$,其中从 $$$0$$$ 到 $$$n-1$$$ 的每个整数都恰好出现一次。他给 Bessie 一个长度为 $$$n$$$ 的数组 $$$a$$$,并挑战她根据 $$$a$$$ 构造 $$$p$$$。

构造数组 $$$a$$$ 使得 $$$a_i$$$ = $$$\texttt{MEX}(p_1, p_2, \ldots, p_i) - p_i$$$,其中数组的 $$$\texttt{MEX}$$$ 是未出现在该数组中的最小非负整数。例如,$$$\texttt{MEX}(1, 2, 3) = 0$$$ 和 $$$\texttt{MEX}(3, 1, 0) = 2$$$。

帮助 Bessie 构造满足 $$$a$$$ 的任何有效排列 $$$p$$$。输入以至少存在一个有效的 $$$p$$$ 的方式给出。如果有多个可能的$$$p$$$,则打印其中之一就足够了。

输入

第一行包含 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — $$$p$$$ 和 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-n \leq a_i \leq n$$$) — 数组 $$$a$$$ 的元素。

保证给定数据至少有一个有效的$$$p$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在新行中输出 $$$n$$$ 个整数,即 $$$p$$$ 的元素。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3
5
1 1 -2 1 2
5
1 1 1 1 1
3
-2 1 2

输出 #1

0 1 4 2 3 
0 1 2 3 4 
2 0 1

注意

在第一种情况下,$$$p = [0, 1, 4, 2, 3]$$$ 是一个可能的输出。

$$$a$$$ 将计算为 $$$a_1 = \texttt{MEX}(0) - 0 = 1$$$, $$$a_2 = \texttt{MEX}(0, 1) - 1 = 1$$$, $$$a_3 = \texttt{MEX}(0, 1, 4) - 4 = -2$$$, $$$a_4 = \texttt{MEX}(0, 1, 4, 2) - 2 = 1$$$, $$$a_5 = \texttt{MEX}(0, 1, 4, 2, 3) - 3 = 2$$$。

因此,根据要求,$$$a$$$ 将是 $$$[1, 1, -2, 1, 2]$$$。