Bessie and MEX (Codeforces 1942B)
Tags: Math, constructive algorithms

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.

Input: 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$$$.

Output: For each test case, output $$$n$$$ integers on a new line, the elements of $$$p$$$.If there are multiple solutions, print any of them.

Note: 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]$$$.

Sample Inputs:
3
5
1 1 -2 1 2
5
1 1 1 1 1
3
-2 1 2

Sample Outputs:
0 1 4 2 3 
0 1 2 3 4 
2 0 1

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    l = [int(x) for x in input().split()]
    mex = 0
    out = []
    for j in l:
        if j > 0:
            out.append(mex)
            mex = mex + j
        else:
            out.append(mex - j)
    print(' '.join(map(str, out)))

Solution (Python):
from heapq import *

def testcase():
    n = int(input())
    a = list(map(int, input().split()))
    nums = list(range(n))
    heapify(nums)
    vals = [0 for i in range(n)]
    mex = n
    for i in range(n - 1, -1, -1):
        vals[i] = mex - a[i]
        if mex > vals[i]:
            mex = vals[i]
    print(' '.join(map(str, vals)))
t = int(input())
for i in range(t):
    testcase()

Solution (Python):
t = int(input())
while t > 0:
    t -= 1
    n = int(input())
    a = list(map(int, input().split()))
    p = [0 for _ in range(n)]
    mex = 0
    seen = [0 for _ in range(n)]
    for i in range(n):
        if a[i] > 0:
            p[i] = mex
            seen[mex] = 1
            while mex < n and seen[mex] == 1:
                mex += 1
        else:
            p[i] = mex - a[i]
            seen[p[i]] = 1
    print(' '.join([str(x) for x in p]))