Reverse Sort Sum
Contest: Codeforces Round 782 (Div. 2)
Difficulty rating: 1900
Tags: constructive algorithms, data structures, greedy, implementation, math, 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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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}]$$$

Example input:
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

Example output:
1 1 0 1 
0 1 1 0 0 0 1 
0 0 0 
0 0 0 1 
1 0 1

Editorial:
The first thing to notice is that any $$$1$$$ in the initial array $$$A$$$, will contribute to the sum of elements of array $$$C$$$ exactly $$$n$$$ times. That means, if $$$S=c_1+c_2+...+c_n$$$, $$$S$$$ must be divisible by $$$n$$$.
Let $$$k=\frac{S}{n}$$$ be the number of $$$1$$$s in the initial array $$$A$$$.
Observation: The $$$1$$$s in $$$B_n$$$ form a suffix of it.
We'll process the array $$$C$$$ from right to left.
Assume $$$a_n$$$ was $$$1$$$. Then, it is clear that $$$c_n=n$$$. Then, we can place a $$$1$$$ there. Now assume $$$a_n$$$ was $$$0$$$. Then, it is clear that if there were any $$$1$$$s in $$$A$$$ (in other words, if $$$k>0$$$), then $$$c_n=1$$$. Otherwise $$$c_n=0$$$. If this is the case, we can place a $$$0$$$ there and move on. Finally, we must subtract $$$1$$$ from each of the last $$$k$$$ elements provided $$$k>0$$$. Decrement $$$k$$$ if a $$$1$$$ was placed. In essence, we simulated removing $$$B_n$$$ from the elementwise sum.
Once we've processed $$$c_n$$$, we can forget about it and continue solving the problem assuming there are $$$n-1$$$ elements, and so on.
The last thing is to handle subtracting $$$1$$$ from the last $$$k$$$ elements. It is possible to do it using a segment tree/BIT, but that is overkill for this problem. A simpler way is to maintain a left border for the suffix, and keep track of when the border crosses an element (say $$$t_i$$$) and when we reach it. Then we can get a simple formula for the value of the element that looks something like $$$c_i-(t_i-i)$$$.
Time complexity: $$$\mathcal{O}(n)$$$ or $$$\mathcal{O}(n\log{n})$$$