Reverse Sort Sum (Codeforces 1659D)
Tags: Greedy, two pointers

Suppose you had an array $$$A$$$ of $$$n$$$ elements, each of which is $$$0$$$ or $$$1$$$.Let us define a function $$$f(k,A)$$$ which returns another array $$$B$$$, the result of sorting the first $$$k$$$ elements of $$$A$$$ in non-decreasing order. For example, $$$f(4,[0,1,1,0,0,1,0]) = [0,0,1,1,0,1,0]$$$. Note that the first $$$4$$$ elements were sorted.Now consider the arrays $$$B_1, B_2,\ldots, B_n$$$ generated by $$$f(1,A), f(2,A),\ldots,f(n,A)$$$. Let $$$C$$$ be the array obtained by taking the element-wise sum of $$$B_1, B_2,\ldots, B_n$$$.For example, let $$$A=[0,1,0,1]$$$. Then we have $$$B_1=[0,1,0,1]$$$, $$$B_2=[0,1,0,1]$$$, $$$B_3=[0,0,1,1]$$$, $$$B_4=[0,0,1,1]$$$. Then $$$C=B_1+B_2+B_3+B_4=[0,1,0,1]+[0,1,0,1]+[0,0,1,1]+[0,0,1,1]=[0,2,2,4]$$$.You are given $$$C$$$. Determine a binary array $$$A$$$ that would give $$$C$$$ when processed as above. It is guaranteed that an array $$$A$$$ exists for given $$$C$$$ in the input. 

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$)  — the number of test cases.Each test case has two lines. The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).The second line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$0 \leq c_i \leq n$$$). It is guaranteed that a valid array $$$A$$$ exists for the given $$$C$$$.The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single line containing $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i$$$ is $$$0$$$ or $$$1$$$). If there are multiple answers, you may output any of them.

Note: Here's the explanation for the first test case. Given that $$$A=[1,1,0,1]$$$, we can construct each $$$B_i$$$:   $$$B_1=[\color{blue}{1},1,0,1]$$$;  $$$B_2=[\color{blue}{1},\color{blue}{1},0,1]$$$;  $$$B_3=[\color{blue}{0},\color{blue}{1},\color{blue}{1},1]$$$;  $$$B_4=[\color{blue}{0},\color{blue}{1},\color{blue}{1},\color{blue}{1}]$$$  And then, we can sum up each column above to get $$$C=[1+1+0+0,1+1+1+1,0+0+1+1,1+1+1+1]=[2,4,2,4]$$$.

Sample Inputs:
5
4
2 4 2 4
7
0 3 4 2 3 2 7
3
0 0 0
4
0 0 0 4
3
1 2 3

Sample Outputs:
1 1 0 1 
0 1 1 0 0 0 1 
0 0 0 
0 0 0 1 
1 0 1

Solution (Python):
def solve(bits):
    first_one_encountered = False
    depth = 0
    next_zero = set()
    answer = []
    for (i, sum) in enumerate(bits):
        if sum == 0:
            answer.append(0)
        elif not first_one_encountered:
            answer.append(1)
            first_one_encountered = True
            depth = sum
            next_zero.add(depth)
        elif i in next_zero:
            answer.append(0)
            depth = i + sum
            next_zero.add(depth)
        else:
            answer.append(1)
            depth = sum
            next_zero.add(depth)
    return ' '.join(list(map(str, answer)))
t = int(input())
for _ in range(t):
    n = int(input())
    bits = list(map(int, input().split()))
    print(solve(bits))

Solution (Python):
def solve(bits):
    ones_encountered = 0
    depth = 0
    next_zero = set()
    answer = []
    for (i, sum) in enumerate(bits):
        if sum == 0:
            answer.append(0)
        elif ones_encountered == 0:
            answer.append(1)
            ones_encountered += 1
            depth = sum
            next_zero.add(depth)
        elif i not in next_zero:
            answer.append(1)
            ones_encountered += 1
            depth = sum
            next_zero.add(depth)
        else:
            answer.append(0)
            depth = i + sum
            next_zero.add(depth)
    return ' '.join(list(map(str, answer)))
t = int(input())
for _ in range(t):
    n = int(input())
    bits = list(map(int, input().split()))
    print(solve(bits))

Solution (Python):
def solve(bits):
    ones_encountered = 0
    depth = 0
    next_zero = set()
    answer = []
    for (i, sum) in enumerate(bits):
        if sum == 0:
            answer.append(0)
        elif ones_encountered == 0:
            answer.append(1)
            ones_encountered += 1
            depth = sum
            next_zero.add(depth)
        elif i not in next_zero:
            answer.append(1)
            ones_encountered += 1
            depth = sum
            next_zero.add(depth)
        else:
            next_zero.remove(i)
            answer.append(0)
            depth = i + sum
            next_zero.add(depth)
    return ' '.join(list(map(str, answer)))
t = int(input())
for _ in range(t):
    n = int(input())
    bits = list(map(int, input().split()))
    print(solve(bits))