[Solution] Reverse Sort Sum solution codeforces

Reverse Sort Sum solution codeforces – Suppose you had an array 𝐴A of 𝑛n elements, each of which is 00 or 11.

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, 𝑓(4,[0,1,1,0,0,1,0])=[0,0,1,1,0,0,1,0]f(4,[0,1,1,0,0,1,0])=[0,0,1,1,0,0,1,0]. Note that the first 44 elements were sorted.

[Solution] Reverse Sort Sum solution codeforces

Now consider the arrays 𝐵1,𝐵2,,𝐵𝑛B1,B2,…,Bn generated by 𝑓(1,𝐴),𝑓(2,𝐴),,𝑓(𝑛,𝐴)f(1,A),f(2,A),…,f(n,A). Let 𝐶C be the array obtained by taking the element-wise sum of 𝐵1,𝐵2,,𝐵𝑛B1,B2,…,Bn.

For example, let 𝐴=[0,1,0,1]A=[0,1,0,1]. Then we have 𝐵1=[0,1,0,1]B1=[0,1,0,1]𝐵2=[0,1,0,1]B2=[0,1,0,1]𝐵3=[0,0,1,1]B3=[0,0,1,1]𝐵4=[0,0,1,1]B4=[0,0,1,1]. Then 𝐶=𝐵1+𝐵2+𝐵3+𝐵4=[0,1,0,1]+[0,1,0,1]+[0,0,1,1]+[0,0,1,1]=[0,2,2,4]C=B1+B2+B3+B4=[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𝑡10001≤t≤1000)  — the number of test cases.

Each test case has two lines. The first line contains a single integer 𝑛n (1𝑛21051≤n≤2⋅105).

The second line contains 𝑛n integers 𝑐1,𝑐2,,𝑐𝑛c1,c2,…,cn (0𝑐𝑖𝑛0≤ci≤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 21052⋅105.

[Solution] Reverse Sort Sum solution codeforces

For each test case, output a single line containing 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (𝑎𝑖ai is 00 or 11). 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 𝐴=[1,1,0,1]A=[1,1,0,1], we can construct each 𝐵𝑖Bi:

  • 𝐵1=[1,1,0,1]B1=[1,1,0,1];
  • 𝐵2=[1,1,0,1]B2=[1,1,0,1];
  • 𝐵3=[0,1,1,1]B3=[0,1,1,1];
  • 𝐵4=[0,1,1,1]B4=[0,1,1,1]

And then, we can sum up each column above to get 𝐶=[1+1+0+0,1+1+1+1,0+0+1+1,1+1+1+1]=[2,4,2,4]C=[1+1+0+0,1+1+1+1,0+0+1+1,1+1+1+1]=[2,4,2,4].

For Solution

Click here

Leave a Comment