Insert Zero and Invert Prefix (Codeforces 1839C)
Tags: Others, constructive algorithms

You have a sequence $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, each element of which is either $$$0$$$ or $$$1$$$, and a sequence $$$b$$$, which is initially empty.You are going to perform $$$n$$$ operations. On each of them you will increase the length of $$$b$$$ by $$$1$$$.  On the $$$i$$$-th operation you choose an integer $$$p$$$ between $$$0$$$ and $$$i-1$$$. You insert $$$0$$$ in the sequence $$$b$$$ on position $$$p+1$$$ (after the first $$$p$$$ elements), and then you invert the first $$$p$$$ elements of $$$b$$$. More formally: let's denote the sequence $$$b$$$ before the $$$i$$$-th ($$$1 \le i \le n$$$) operation as $$$b_1, b_2, \ldots, b_{i-1}$$$. On the $$$i$$$-th operation you choose an integer $$$p$$$ between $$$0$$$ and $$$i-1$$$ and replace $$$b$$$ with $$$\overline{b_1}, \overline{b_2}, \ldots, \overline{b_{p}}, 0, b_{p+1}, b_{p+2}, \ldots, b_{i-1}$$$. Here, $$$\overline{x}$$$ denotes the binary inversion. Hence, $$$\overline{0} = 1$$$ and $$$\overline{1} = 0$$$. You can find examples of operations in the Notes section.Determine if there exists a sequence of operations that makes $$$b$$$ equal to $$$a$$$. If such sequence of operations exists, find it.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the sequence $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 1$$$) — the sequence $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output: For each test case:   output "NO", if it is impossible to make $$$b$$$ equal to $$$a$$$ using the given operations;  otherwise, output "YES" in the first line and $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \le p_i \le i-1$$$) in the second line — the description of sequence of operations that makes $$$b$$$ equal to $$$a$$$. Here, $$$p_i$$$ should be the integer you choose on the $$$i$$$-th operation. If there are multiple solutions, you can output any of them. 

Note: In the first test case,   Before the first operation, $$$b = [\,]$$$. You choose $$$p = 0$$$ and replace $$$b$$$ with $$$[\, \underline{0} \,]$$$  On the second operation you choose $$$p = 0$$$ and replace $$$b$$$ with $$$[\, \underline{0}, 0 \,]$$$.  On the third operation you choose $$$p = 2$$$ and replace $$$b$$$ with $$$[\, 1, 1, \underline{0} \,]$$$.  On the fourth operation you choose $$$p = 1$$$ and replace $$$b$$$ with $$$[\, 0, \underline{0}, 1, 0 \,]$$$.  On the fifth operation you choose $$$p = 3$$$ and replace $$$b$$$ with $$$[\, 1, 1, 0, \underline{0}, 0 \,]$$$. Hence, sequence $$$b$$$ changes in the following way: $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0}, 0 \,]$$$ $$$\xrightarrow{p \, = \, 2}$$$ $$$[\, 1, 1, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 0, \underline{0}, 1, 0 \,]$$$ $$$\xrightarrow{p \, = \, 3}$$$ $$$[\, 1, 1, 0, \underline{0}, 0 \,]$$$. In the end the sequence $$$b$$$ is equal to the sequence $$$a$$$, so this way to perform operations is one of the correct answers.In the second test case, $$$n = 1$$$ and the only achiveable sequence $$$b$$$ is $$$[\, 0 \, ]$$$.In the third test case, there are six possible sequences of operations:  $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0}, 0 \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0}, 0, 0 \,]$$$.  $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0}, 0 \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 1, \underline{0}, 0 \,]$$$.  $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0}, 0 \,]$$$ $$$\xrightarrow{p \, = \, 2}$$$ $$$[\, 1, 1, \underline{0} \,]$$$.  $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 1, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0}, 1, 0 \,]$$$.  $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 1, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 0, \underline{0}, 0 \,]$$$.  $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 1, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 2}$$$ $$$[\, 0, 1, \underline{0} \,]$$$. None of them makes $$$b$$$ equal to $$$[\, 0, 1, 1 \,]$$$, so the answer is "NO".

Sample Inputs:
4
5
1 1 0 0 0
1
1
3
0 1 1
6
1 0 0 1 1 0

Sample Outputs:
YES
0 0 2 1 3
NO
NO
YES
0 1 0 2 4 2

Solution (Python):
from io import StringIO
import sys

def main():
    out = StringIO()
    get_line = sys.stdin.readline

    def get_ints():
        return map(int, get_line().split(' '))

    def get_int():
        return int(get_line())
    for i in range(get_int()):
        n = get_int()
        a = list(get_ints())
        if a[-1] != 0:
            out.write('NO\n')
            continue
        zis = [idx for (idx, j) in enumerate(a) if j == 0]
        ops = []
        pz = -1
        st = 0
        for j in zis:
            ops.append(j - st)
            ops += [0] * (j - pz - 1)
            st += j - pz
            pz = j
        out.write('YES\n')
        out.write(' '.join(map(str, reversed(ops))))
        out.write('\n')
    sys.stdout.write(out.getvalue())
if __name__ == '__main__':
    main()
''

Solution (Python):
import math
import sys, bisect, heapq
from collections import defaultdict, deque
readline = sys.stdin.readline
read = lambda : [int(x) for x in readline().split()]
alloc = lambda dfv, *s: len(s) != 1 and [alloc(dfv, *s[1:]) for _ in range(int(s[0]))] or [dfv] * int(s[0])
bet = lambda a, b: a <= b and range(a, b + 1) or range(a, b - 1, -1)
show = lambda arr: print(' '.join(map(str, arr)))
INF = float('inf')
MOD = 10 ** 9 + 7
if __name__ == '__main__':
    for _wzl_ in range(int(input())):
        (n,) = read()
        a = read()
        res = []
        i = n - 1
        if a[i] == 1:
            print('NO')
            continue
        while i >= 0:
            j = i
            while j >= 0 and a[j] == 0:
                j -= 1
                res.append(0)
            i = j
            while j >= 0 and a[j] == 1:
                res.append(0)
                j -= 1
            res[-1] = i - j
            i = j
        print('YES')
        show(res)

Solution (Python):
import sys
from os import path

def input():
    return sys.stdin.readline().strip()
from typing import List

def in_int():
    return int(input())

def in_list():
    return list(input().split())

def in_list_int():
    return list(map(int, input().split()))

def in_str():
    s = input()
    return list(s)

def in_2d(arr, row, col):
    res = [[0 for _ in range(col)] for __ in range(row)]
    for (i, val) in enumerate(arr):
        res[i // col][i % col] = val
    return res

def print_str(arr: List[int], deter: str=' '):
    print(deter.join(map(str, arr)))

def solve(n, a):
    if a[-1] == 1:
        print('NO')
        return
    print('YES')
    res = []
    one = 0
    for i in range(n - 1, -1, -1):
        x = a[i]
        if x == 0:
            res.append(0)
            one = 0
        elif i == 0 or a[i - 1] == 0:
            res.append(one + 1)
        else:
            one += 1
            res.append(0)
    print_str(res)

def main():
    testcases = in_int()
    for _ in range(testcases):
        n = in_int()
        a = in_list_int()
        solve(n, a)
if __name__ == '__main__':
    if path.exists('input.txt'):
        sys.stdin = open('input.txt', 'r')
        sys.stdout = open('output.txt', 'w')
    main()