Bessie and MEX

题面翻译

约翰农夫有一个排列 p1,p2,…,pn
，其中从 0
到 n-1
的每个整数恰好出现一次。他给贝西一个长度为 n
的数组 a
，并挑战她基于 a
构建 p
。

数组 a
被构建为 ai
= MEX(p1,p2,…,pi)-pi
，其中数组的 MEX
是不在该数组中出现的最小非负整数。例如，MEX(1,2,3)=0
和 MEX(3,1,0)=2
。

帮助贝西构建满足 a
的任何有效排列 p
。输入以这样的方式给出，至少存在一个有效的 p
。如果存在多个可能的 p
，只需打印其中一个即可。

题目描述

MOOO! - Doja Cat

⠀

Farmer John has a permutation $ p_1, p_2, \ldots, p_n $ , where every integer from $ 0 $ to $ n-1 $ occurs exactly once. He gives Bessie an array $ a $ of length $ n $ and challenges her to construct $ p $ based on $ a $ .

The array $ a $ is constructed so that $ a_i $ = $ \texttt{MEX}(p_1, p_2, \ldots, p_i) - p_i $ , where the $ \texttt{MEX} $ of an array is the minimum non-negative integer that does not appear in that array. For example, $ \texttt{MEX}(1, 2, 3) = 0 $ and $ \texttt{MEX}(3, 1, 0) = 2 $ .

Help Bessie construct any valid permutation $ p $ that satisfies $ a $ . The input is given in such a way that at least one valid $ p $ exists. If there are multiple possible $ p $ , it is enough to print one of them.

输入格式

The first line contains $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases.

The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the lengths of $ p $ and $ a $ .

The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -n \leq a_i \leq n $ ) — the elements of array $ a $ .

It is guaranteed that there is at least one valid $ p $ for the given data.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, output $ n $ integers on a new line, the elements of $ p $ .

If there are multiple solutions, print any of them.

样例 #1

样例输入 #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

提示

In the first case, $ p = [0, 1, 4, 2, 3] $ is one possible output.

$ a $ will then be calculated as $ 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 $ .

So, as required, $ a $ will be $ [1, 1, -2, 1, 2] $ .

const int N = 3e5 + 10;
int a[N];
int b[N];
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int top = n;
    for (int i = n; i >= 1; i--) 
    {
        b[i] = top - a[i];
        top = min(top, b[i]);
    }
    for (int i = 1; i <= n; i++) cout << b[i] << ' ';
    cout << '\n';
}