1942B.md (2068B)
1 Source: https://codeforces.com/problemset/problem/1942/B 2 3 B. Bessie and MEX 4 5 time limit per test 6 7 1.5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 [MOOO! - Doja Cat](https://soundcloud.com/amalaofficial/mooo) 22 23 ⠀ 24 25 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$. 26 27 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$. 28 29 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. 30 31 Input 32 33 The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 34 35 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$. 36 37 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$. 38 39 It is guaranteed that there is at least one valid $p$ for the given data. 40 41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 42 43 Output 44 45 For each test case, output $n$ integers on a new line, the elements of $p$. 46 47 If there are multiple solutions, print any of them. 48 49 Example 50 51 Input 52 53 ``` 54 3 55 56 5 57 58 1 1 -2 1 2 59 60 5 61 62 1 1 1 1 1 63 64 3 65 66 -2 1 2 67 ``` 68 69 Output 70 71 ``` 72 0 1 4 2 3 73 0 1 2 3 4 74 2 0 1 75 ``` 76 77 Note 78 79 In the first case, $p = [0, 1, 4, 2, 3]$ is one possible output. 80 81 $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$. 82 83 So, as required, $a$ will be $[1, 1, -2, 1, 2]$.