Reverse Sort Sum

2000ms

262144K

Description:

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.

Sample 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

Sample Output:

1 1 0 1 
0 1 1 0 0 0 1 
0 0 0 
0 0 0 1 
1 0 1

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

Informação

Provedor Codeforces

Código CF1659D