[Solution] Reverse Sort Sum solution codeforces

Reverse Sort Sum solution codeforces – 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, 0, 1, 0]$ . Note that the first $4$ elements were sorted.

[Solution] Reverse Sort Sum solution codeforces

Now consider the arrays $B_{1}, B_{2}, \dots, B_{n}$ generated by $f (1, A), f (2, A), \dots, f (n, A)$ . Let $C$ be the array obtained by taking the element-wise sum of $B_{1}, B_{2}, \dots, 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}, \dots, 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}$ .

[Solution] Reverse Sort Sum solution codeforces

For each test case, output a single line containing $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ ( $a_{i}$ is $0$ or $1$ ). If there are multiple answers, you may output any of them.

Example

input

Copy

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

output

Copy

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

Reverse Sort Sum solution codeforces

Here’s the explanation for the first test case. Given that $A = [1, 1, 0, 1]$ , we can construct each $B_{i}$ :

$B_{1} = [1, 1, 0, 1]$ ;
$B_{2} = [1, 1, 0, 1]$ ;
$B_{3} = [0, 1, 1, 1]$ ;
$B_{4} = [0, 1, 1, 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]$ .

[Solution] Reverse Sort Sum solution codeforces

[Solution] Reverse Sort Sum solution codeforces

[Solution] Reverse Sort Sum solution codeforces

Reverse Sort Sum solution codeforces

For Solution

“Click here“

Leave a Comment Cancel reply