CF1942B.Bessie and MEX

MOOO! - Doja Cat

⠀

农夫 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 \times 10^5$），表示 $p$ 和 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-n \leq a_i \leq n$），表示数组 $a$ 的元素。

保证对于给定的数据，至少存在一个合法的 $p$。

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

对于每个测试用例，输出一行 $n$ 个整数，表示排列 $p$ 的元素。

如果有多组解，输出任意一组均可。

在第一个样例中，$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]$，与题意一致。

由 ChatGPT 4.1 翻译