Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

"Out of 6 billion humans, the troublemakers are just a handful." - Dalai Lama

Nikitasha and Mansi are best friends. They have a binary sequence $A_{1}, A_{2}, \ldots, A_{N}$ (each element of this sequence is $0$ or $1$). Their friend Sakshi always finds ways to trouble them. This time, Sakshi altered their sequence by performing the following operation $Z$ times:
Create a new sequence $B_{1}, B_{2}, \ldots, B_{N}$. Initially, $A_{i} = B_{i}$ for each valid $i$.
For each valid $i$ such that $A_{i} = 0$ and $A_{i+1} = 1$, swap $B_{i}$ and $B_{i+1}$, i.e. set $B_{i} = 1$ and $B_{i+1} = 0$. Note that the order of swaps does not matter.
Replace the sequence $A$ by the sequence $B$.

Now, Sakshi challenges Nikitasha And Mansi to find the altered sequence (the resulting sequence $A$ after $Z$ steps). Help Nikitasha and Mansi find this sequence.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $Z$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing $N$ space-separated integers — the altered sequence.

------  Constraints  ------
$1 ≤ T ≤ 1,000$
$1 ≤ N, Z ≤ 10^{6}$
$0 ≤ A_{i} ≤ 1$ for each valid $i$
the sum of $N$ over all test cases does not exceed $10^{6}$

------  Subtasks ------
Subtask #1 (10 points):
$1 ≤ N, Z ≤ 3,000$
the sum of $N$ over all test cases does not exceed $3,000$

Subtask #2 (90 points): original constraints

----- Sample Input 1 ------ 
2

6 2

0 1 1 0 1 1

4 4

0 1 0 1
----- Sample Output 1 ------ 
1 1 0 1 1 0 	

1 1 0 0
----- explanation 1 ------ 
Example case 1: After the first step, the sequence becomes $(1, 0, 1, 1, 0, 1)$. After the second step, it becomes $(1, 1, 0, 1, 1, 0)$.

Example case 2: After the first step, the sequence becomes $(1, 0, 1, 0)$. After the second step, the sequence becomes $(1, 1, 0, 0)$. Applying more steps does not alter the sequence anymore, so after the third and fourth step, the sequence remains $(1, 1, 0, 0)$.

Source: codechef | Difficulty: VERY_HARD
Tags: Data structures

Greedy algorithms


Solutions:
for _ in range(int(input())):
	(n, z) = map(int, input().split())
	a = list(map(int, input().split()))
	dp = []
	temp = []
	record = []
	total = 0
	ones = 0
	zeros = 0
	for i in range(n):
		if a[i] == 1:
			if len(temp) >= z and temp[-z] == 1:
				total -= 1
			total += 1
			temp.append(1)
			record.append(len(temp) - 1)
			if zeros != 0:
				total -= zeros
				counter = min(len(temp), zeros)
				for v in record[:-z - 1:-1]:
					temp[v] = 0
					counter -= 1
					del record[-1]
					if counter == 0:
						break
				zeros = 0
			total = max(0, total)
			dp.append(total)
		else:
			zeros += 1
	ans = [0] * n
	ind = 0
	for i in range(n):
		if a[i] == 1:
			shift = i - (z - dp[ind])
			ans[max(shift, ind)] = 1
			ind += 1
	print(' '.join((str(v) for v in ans)))


import math
t = int(input())
while t > 0:
	(n, z) = [int(x) for x in input().split()]
	seq = [int(x) for x in input().split()]
	run = []
	last = 0
	ones = False
	timer = []
	ans = []
	ct = 0
	tots = -1
	iso = True
	for i in range(n):
		if seq[i] == 1:
			ans.append(z)
			tots += 1
			if last == 1:
				run.append(0)
			act = ct - 1
			marked = []
			for m in range(len(run) - 1, -1, -1):
				run[m] += 1
				if act > 0:
					act -= 1
					marked.append(m)
				elif run[m] <= z:
					ans[tots] -= 1
				else:
					marked.append(m)
			marked.sort(reverse=True)
			for b in marked:
				del run[b]
			ct = 0
			last = seq[i]
		else:
			ct += 1
		last = seq[i]
	final = []
	last = -1
	tots = -1
	for l in range(n):
		if seq[l] == 1:
			tots += 1
			if ans[tots] > 0:
				temp = ans[tots]
			else:
				temp = 0
			if l - temp > last:
				final.append(l - temp)
				last = l - temp
			else:
				final.append(last + 1)
				last += 1
	fk = 0
	mx = len(final)
	for f in range(n):
		if fk < mx and final[fk] == f:
			print(1, end=' ')
			fk += 1
		else:
			print(0, end=' ')
	if t != 1:
		print('')
	else:
		print('', end='')
	t -= 1


test = int(input())
while test != 0:
	(n, z) = map(int, input().split())
	a = list(map(int, input().split()))
	ones = []
	for i in range(n):
		if a[i] == 1:
			ones.append(i)
	while z > 0:
		flag = True
		flag2 = False
		cluster = False
		for i in range(len(ones) - 1):
			if ones[i + 1] - ones[i] > 1:
				flag2 = True
				continue
			if flag2:
				if ones[i + 1] - ones[i] == 1:
					cluster = True
					break
		if cluster == False:
			break
		for i in range(len(ones)):
			if i == len(ones) - 1:
				if flag:
					if ones[i] - 1 < i:
						ones[i] = i
					else:
						ones[i] -= 1
			elif flag:
				if ones[i + 1] - ones[i] == 1:
					flag = False
				if ones[i] - 1 < i:
					ones[i] = i
				else:
					ones[i] -= 1
			elif ones[i + 1] - ones[i] > 1:
				flag = True
		z -= 1
	if z > 0:
		for i in range(len(ones)):
			if ones[i] - z < i:
				ones[i] = i
			else:
				ones[i] -= z
	ptr = 0
	for i in range(n):
		if i == ones[ptr]:
			print('1 ', end='')
			if ptr + 1 < len(ones):
				ptr += 1
		else:
			print('0 ', end='')
	print('')
	test -= 1


t = int(input())
for naman in range(t):
	(n, z) = map(int, input().split())
	l = list(map(int, input().split()))
	listof1 = []
	ans = [0] * n
	for i in range(len(l)):
		if l[i] == 1:
			listof1.append(i)
	n1 = len(listof1)
	for i in range(n1 - 1):
		if listof1[i + 1] - listof1[i] == 1:
			cont = True
			break
	k = z
	while cont and k > 0:
		flag2 = 0
		flag = 0
		flag3 = 0
		for i in range(n1):
			if flag == 1:
				if i != n1 - 1:
					if listof1[i + 1] - listof1[i] != 1:
						flag = 0
			elif i != n1 - 1 and i != 0:
				if listof1[i + 1] - listof1[i] == 1:
					listof1[i] = max(listof1[i - 1] + 1, listof1[i] - 1)
					flag = 1
				else:
					listof1[i] = max(listof1[i - 1] + 1, listof1[i] - 1)
					flag = 0
			elif i == 0:
				if listof1[i + 1] - listof1[i] == 1:
					listof1[i] = max(listof1[i] - 1, 0)
					flag = 1
				else:
					listof1[i] = max(listof1[i] - 1, 0)
					flag = 0
			else:
				listof1[i] = max(listof1[i - 1] + 1, listof1[i] - 1)
		k = k - 1
		for i in range(n1 - 1):
			if flag3 == 0:
				if listof1[i + 1] - listof1[i] != 1:
					flag3 = 1
			elif listof1[i + 1] - listof1[i] == 1:
				cont = True
				flag2 = 1
				break
		if flag2 == 0:
			cont = False
	if k > 0:
		for i in range(n1):
			if i == 0:
				listof1[i] = max(0, listof1[i] - k)
			else:
				listof1[i] = max(listof1[i - 1] + 1, listof1[i] - k)
		for i in listof1:
			ans[i] = 1
		for i in ans:
			print(i, end=' ')
	else:
		for i in listof1:
			ans[i] = 1
		for i in ans:
			print(i, end=' ')
	print()


def find(arr):
	if arr == []:
		return []
	elif arr[-1] == 0:
		return find(arr[:-1])
	else:
		aux = []
		count = 0
		for i in range(1, len(arr) + 1):
			if arr[-i] == 0:
				aux += [arr[-i]]
				count += 1
			elif arr[-i] == 1:
				if count > 0:
					count -= 1
				else:
					aux += [1]
	aux = aux[::-1]
	return aux
t = int(input())
for _ in range(t):
	(n, z) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	onespos = {i: float('inf') for i in range(1, len(arr) + 1)}
	jumps = []
	currentones = 0
	currentzeros = 0
	numones = 0
	pos = 0
	count = 0
	for i in range(len(arr)):
		if arr[i] == 1:
			pos = i
			numones = 1
			currentones = 1
			currentzeros = min(i, z)
			jumps += [min(i, z)]
			onespos[1] = i
			break
	for i in range(pos + 1, len(arr)):
		if arr[i] == 0:
			count += 1
		else:
			currentones += 1
			numones -= count
			if numones <= 0:
				pos = i - currentones + 1
				jumps += [min(z, pos)]
				numones = 1
				onespos[1] = pos
				count = 0
				currentzeros = min(z, pos)
			else:
				pos += 1
				till = onespos[numones]
				if pos - z <= 0:
					currentzeros = currentzeros + count
				else:
					numone = z - currentzeros
					if count <= numone:
						for i in range(1, len(arr) + 1):
							if onespos[i] > pos - z - 1:
								currentzeros = currentzeros + count - 1
								break
							elif onespos[i] == pos - z - 1:
								currentzeros = currentzeros + count
								break
					else:
						count = numone
						currentzeros += count
				jumps += [currentzeros]
				numones += 1
				onespos[numones] = pos
				count = 0
	ans = [0 for i in range(len(arr))]
	for i in range(len(arr)):
		if arr[i] == 1:
			ans[i - jumps[0]] = 1
			jumps.pop(0)
	ans = list(map(str, ans))
	print(' '.join(ans))


def myfunction0(binary, Z, origlength):
	seperated = False
	while not seperated:
		Z -= 1
		totalincongestion = 0
		incongestion = 0
		for i in range(len(binary) + 1):
			if i > 1:
				if binary[i - 2] == binary[i - 1] - 1:
					incongestion += 1
					if i - 1 == len(binary) - 1 and binary[i - 1] != origlength - 1:
						totalincongestion += incongestion
				else:
					totalincongestion += incongestion
					incongestion = 0
			if i <= len(binary) - 1:
				if i == len(binary) - 1:
					if binary[i] != origlength - 1:
						binary[i] += 1
				elif binary[i + 1] == binary[i] + 1:
					pass
				else:
					binary[i] += 1
		if Z == 0:
			return binary
		if totalincongestion == 0:
			seperated = True
	for i in range(len(binary) - 1, -1, -1):
		if binary[i] + Z > origlength - 1:
			if i == len(binary) - 1:
				binary[i] = origlength - 1
			else:
				binary[i] = binary[i + 1] - 1
		elif i == len(binary) - 1:
			binary[i] += Z
		elif binary[i] + Z >= binary[i + 1]:
			binary[i] = binary[i + 1] - 1
		else:
			binary[i] += Z
	return binary

def myfunction1(binary, Z, origlength):
	seperated = False
	while not seperated:
		Z -= 1
		totalincongestion = 0
		incongestion = 0
		for i in range(len(binary) - 1, -2, -1):
			if i < len(binary) - 2:
				if binary[i + 2] == binary[i + 1] + 1:
					incongestion += 1
					if i + 1 == 0 and binary[i + 1] != 0:
						totalincongestion += incongestion
				else:
					totalincongestion += incongestion
					incongestion = 0
			if i >= 0:
				if i == 0:
					if binary[i] != 0:
						binary[i] -= 1
				elif binary[i - 1] == binary[i] - 1:
					pass
				else:
					binary[i] -= 1
		if Z == 0:
			return binary
		if totalincongestion == 0:
			seperated = True
	for i in range(len(binary)):
		if binary[i] - Z < 0:
			if i == 0:
				binary[i] = 0
			else:
				binary[i] = binary[i - 1] + 1
		elif i == 0:
			binary[i] -= Z
		elif binary[i] - Z <= binary[i - 1]:
			binary[i] = binary[i - 1] + 1
		else:
			binary[i] -= Z
	return binary
for i in range(int(input())):
	(g, Z) = list(map(int, input().split()))
	mylist = input().split()
	zerolist = []
	onelist = []
	for j in range(len(mylist)):
		if mylist[j] == '0':
			zerolist.append(j)
		else:
			onelist.append(j)
	if len(zerolist) < len(onelist):
		new_array = myfunction0(zerolist, Z, len(mylist))
		for i in range(len(mylist)):
			if len(new_array) == 0:
				print('1 ' * (len(mylist) - i))
				break
			elif i == new_array[0]:
				new_array.pop(0)
				if i == len(mylist) - 1:
					print('0')
				else:
					print('0', end=' ')
			elif i == len(mylist) - 1:
				print('1')
			else:
				print('1', end=' ')
	else:
		new_array = myfunction1(onelist, Z, len(mylist))
		for i in range(len(mylist)):
			if len(new_array) == 0:
				print('0 ' * (len(mylist) - i))
				break
			elif i == new_array[0]:
				new_array.pop(0)
				if i == len(mylist) - 1:
					print('1')
				else:
					print('1', end=' ')
			elif i == len(mylist) - 1:
				print('0')
			else:
				print('0', end=' ')


t = int(input())
for i in range(t):
	(n, z) = map(int, input().split(' '))
	bin_seq = list(map(int, input().split(' ')))
	req1 = []
	curr = 0
	while curr <= n:
		num = 0
		for j in range(curr, n):
			if bin_seq[j] == 0:
				num += 1
			else:
				break
		req1.append(num)
		curr += num + 1
	req2 = []
	curr = 0
	len_req1 = len(req1)
	while curr < len_req1 - 1:
		inx1 = -1
		inx2 = -1
		while curr < len_req1 - 1:
			if req1[curr] == 0:
				curr += 1
			else:
				inx1 = curr
				curr += 1
				break
		while curr < len_req1 - 1:
			if req1[curr] != 0:
				curr += 1
			else:
				inx2 = curr
				curr += 1
				break
		if inx1 != -1 and inx2 == -1:
			inx2 = len_req1 - 1
			req2.append([inx1, inx2])
		elif inx1 != -1 and inx2 != -1:
			req2.append([inx1, inx2])
	for j in range(z):
		if len(req2) == 0:
			break
		for k in req2:
			req1[k[0]] -= 1
			req1[k[1]] += 1
			if k[1] != len_req1 - 1:
				k[1] += 1
		prev_req2 = req2
		req2 = []
		cons = 0
		while cons < len(prev_req2):
			inx1 = prev_req2[cons][0]
			inx2 = prev_req2[cons][1]
			if req1[inx1] == 0:
				if inx1 != len(req1) - 2:
					inx1 += 1
				else:
					cons += 1
					continue
			if req1[inx2] != 0 and inx2 != len(req1) - 1:
				try:
					while req1[inx2] != 0:
						cons += 1
						inx2 = prev_req2[cons][1]
				except:
					inx2 = len_req1 - 1
			cons += 1
			req2.append([inx1, inx2])
	ans_str = ''
	for j in req1:
		for k in range(j):
			ans_str += '0 '
		ans_str += '1 '
	print(ans_str[:-3])