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.


-----Examples-----

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

Source: codeforces | Difficulty: HARD
Tags: Constructive algorithms

Amortized analysis

Implementation

Greedy algorithms

Mathematics

Data structures


Solutions:
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))


def reversesortsum(nums):
	total = sum(nums)
	k = total // n
	ans = [0] * n
	b = [0] * n
	lf = n - k
	for i in range(lf, n):
		b[i] = n - 1
	for i in range(n - 1, -1, -1):
		if lf > i:
			break
		cur = nums[i] - (b[i] - i)
		if cur == i + 1:
			ans[i] = 1
		elif cur == 1:
			ans[i] = 0
			lf -= 1
			b[lf] = i - 1
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	nums = [int(x) for x in input().split()]
	res = reversesortsum(nums)
	print(' '.join((str(x) for x in res)))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	it = -1
	ans = [1] * n
	for i in range(n):
		if ans[i] == 0:
			it = a[i] + i
		elif a[i] == 0:
			it = i
		else:
			it = a[i]
		if it == n:
			break
		ans[it] = 0
	print(*ans)


T = int(input())
for t in range(T):
	N = int(input())
	C = list(map(int, input().split()))
	ans = [0] * N
	k = sum(C) // N
	i = N - 1
	while i > -1 and k > 0:
		if C[i] == N:
			ans[i] = 1
			k -= 1
		else:
			C[i - k] += N - i
		i -= 1
	print(*ans)


from builtins import map

def main():
	for t in range(int(input())):
		n = int(input())
		ans = [0 for i in range(n)]
		a = list(map(lambda ai: int(ai), input().split(' ')))
		k = sum(a) // n
		lb = n - k
		for i in range(1, k + 1):
			a[n - i] -= i
		for i in range(n - 1, -1, -1):
			if a[i] == i and k > 0:
				k -= 1
				ans[i] = 1
			else:
				ans[i] = 0
				lb -= 1
				if lb >= 0:
					a[lb] -= k
		for i in range(n):
			print(ans[i], end=' ')
		print(end='\n')
main()


def solve():
	n = int(input())
	c = list(map(int, input().split()))
	sum = 0
	for i in range(n):
		sum += c[i]
	ones = sum // n
	ans = [1 for _ in range(n + 1)]
	first_0 = c[0]
	ans[first_0] = 0
	for i in range(n):
		if ans[i] == 1:
			if c[i] == 0:
				ans[i] = 0
		if ans[i] == 1:
			next_0 = c[i]
			ans[next_0] = 0
		else:
			next_0 = i + c[i]
			ans[next_0] = 0
		print(ans[i], end=' ')
	print()
t = int(input())
for _ in range(t):
	solve()


import sys

def solve():
	inp = sys.stdin.readline
	n = int(input())
	c = list(map(int, inp().split()))
	a = ['0'] * n
	sub = [0] * (n + 1)
	have = 0
	j = 0
	cur = 0
	for i in range(0, n):
		sub[i - have + 1] += 1
		sub[i + 1] -= 1
		if j >= i - have + 1:
			cur += 1
		while j < i - have:
			j += 1
			cur += sub[j]
		while j > i - have:
			cur -= sub[j]
			j -= 1
		if j >= 0 and cur < c[j]:
			a[i] = '1'
			sub[i] += i
			sub[i + 1] -= i
			if j == i:
				cur += i
			have += 1
			if i - have + 1 < i + 1:
				sub[i - have + 1] += 1
				sub[i - have + 2] -= 1
				if j == i - have + 1:
					cur += 1
	print(' '.join(a))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
input = sys.stdin.readline
from collections import deque

def solve():
	n = int(input())
	C = list(map(int, input().split()))
	k = sum(C) // n
	ans = [0] * n
	idx = n - 1
	cnt = 0
	st = deque([])
	while idx > 0:
		fk = 1 if k else 0
		if not fk:
			print(*ans)
			return
		while st and idx < st[0]:
			cnt -= 1
			st.popleft()
		ak = (C[idx] - cnt - fk) // idx
		ans[idx] = ak
		cnt += 1
		st.append(idx - k + 1)
		k -= 1 if ak else 0
		idx -= 1
	ans[0] = 1 if k else 0
	print(*ans)
	return
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	ones = s // n
	rem = [0 for i in range(n)]
	curr = 0
	sol = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		curr -= rem[i]
		if ones:
			curr += 1
			if i - ones >= 0:
				rem[i - ones] += 1
		l[i] -= curr
		if l[i] == i and ones:
			sol[i] = 1
			ones -= 1
	print(*sol)


for i in range(int(input())):
	n = int(input())
	dat = list(map(int, input().split()))
	s = sum(dat)
	num = s // n
	nul = [0 for i in range(n)]
	c = 0
	rs = [0 for i in range(n)]
	for i in range(n - 1, -1, -1):
		c -= nul[i]
		if num:
			c += 1
			if i - num >= 0:
				nul[i - num] += 1
		dat[i] -= c
		if dat[i] == i and num:
			rs[i] = 1
			num -= 1
	print(*rs)


import queue

def solve(bits):
	ones_encountered = 0
	depth = 0
	next_zeros = queue.Queue()
	answer = []
	for (pos, sum) in enumerate(bits):
		if sum == 0:
			answer.append(0)
		elif ones_encountered == 0:
			answer.append(1)
			ones_encountered += 1
			depth = sum
			next_zeros.put(depth)
			next_zero = next_zeros.get()
		elif pos < next_zero:
			answer.append(1)
			ones_encountered += 1
			depth = sum
			next_zeros.put(depth)
		else:
			answer.append(0)
			depth = pos + sum
			next_zeros.put(depth)
			next_zero = next_zeros.get()
	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))