← 返回题目列表

Codeforces · 1839/C

C. 插入零和反转前缀

中文机器翻译题面 查看原题

您有一个长度为 $$$n$$$ 的序列 $$$a_1, a_2, \ldots, a_n$$$,其中每个元素为 $$$0$$$ 或 $$$1$$$,以及一个最初为空的序列 $$$b$$$。

您将执行 $$$n$$$ 操作。在每一个上,您都将 $$$b$$$ 的长度增加 $$$1$$$。

- 在第 $$$i$$$ 操作中,您选择 $$$0$$$ 和 $$$i-1$$$ 之间的整数 $$$p$$$。您将 $$$0$$$ 插入序列 $$$b$$$ 中的 $$$p+1$$$ 位置(在第一个 $$$p$$$ 元素之后),然后反转 $$$b$$$ 的第一个 $$$p$$$ 元素。
- 更正式地说:让我们将第 $$$i$$$ ($$$1 \le i \le n$$$) 操作之前的序列 $$$b$$$ 表示为 $$$b_1, b_2, \ldots, b_{i-1}$$$。在第 $$$i$$$ 操作中,您选择 $$$0$$$ 和 $$$i-1$$$ 之间的整数 $$$p$$$,并将 $$$b$$$ 替换为 $$$\overline{b_1}、\overline{b_2}、\ldots、\overline{b_{p}}、0、b_{p+1}、b_{p+2}、\ldots, b_{i-1}$$$。这里,$$$\overline{x}$$$表示二进制反转。因此,$$$\overline{0} = 1$$$ 且 $$$\overline{1} = 0$$$。

您可以在注释部分找到操作示例。

确定是否存在使 $$$b$$$ 等于 $$$a$$$ 的操作序列。如果存在这样的操作序列,请找到它。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 序列 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 1$$$) - 序列 $$$a$$$。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例:

- 如果使用给定的操作不可能使$$$b$$$等于$$$a$$$,则输出“NO”;
- 否则,在第一行输出“YES”,在第二行输出 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \le p_i \le i-1$$$) — 使 $$$b$$$ 等于 $$$a$$$ 的操作序列的描述。这里,$$$p_i$$$ 应该是您在第 $$$i$$$ 操作中选择的整数。如果有多个解,可以输出任意一个。

示例

输入 #1

4
5
1 1 0 0 0
1
1
3
0 1 1
6
1 0 0 1 1 0

输出 #1

YES
0 0 2 1 3
NO
NO
YES
0 1 0 2 4 2

注意

在第一个测试用例中,

1. 在第一次操作之前,$$$b = [\,]$$$。您选择 $$$p = 0$$$ 并将 $$$b$$$ 替换为 $$$[\, \underline{0} \,]$$$
2. 在第二个操作中,选择 $$$p = 0$$$ 并将 $$$b$$$ 替换为 $$$[\, \underline{0}, 0 \,]$$$。
3. 在第三个操作中,您选择 $$$p = 2$$$ 并将 $$$b$$$ 替换为 $$$[\, 1, 1, \underline{0} \,]$$$。
4. 在第四个操作中,您选择 $$$p = 1$$$ 并将 $$$b$$$ 替换为 $$$[\, 0, \underline{0}, 1, 0 \,]$$$。
5. 在第五次操作中,您选择 $$$p = 3$$$ 并将 $$$b$$$ 替换为 $$$[\, 1, 1, 0, \underline{0}, 0 \,]$$$。

因此,序列 $$$b$$$ 按以下方式更改: $$$[\,]$$$ $$$\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, \下划线{0}, 0 \,]$$$。最后序列$$$b$$$等于序列$$$a$$$,所以这种执行操作的方式是正确答案之一。

在第二个测试用例中,$$$n = 1$$$,唯一可实现的序列$$$b$$$ 是$$$[\, 0 \, ]$$$。

在第三个测试用例中,有六种可能的操作序列:

1. $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0}, 0 \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \下划线{0}, 0, 0 \,]$$$。
2. $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0}, 0 \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 1, \下划线{0}, 0 \,]$$$。
3. $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0}, 0 \,]$$$ $$$\xrightarrow{p \, = \, 2}$$$ $$$[\, 1, 1, \下划线{0} \,]$$$。
4. $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 1, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \下划线{0}, 1, 0 \,]$$$。
5. $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 1, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 0, \下划线{0}, 0 \,]$$$。
6. $$$[\,]$$$ $$$\xrightarrow{p \, = \, 0}$$$ $$$[\, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 1}$$$ $$$[\, 1, \underline{0} \,]$$$ $$$\xrightarrow{p \, = \, 2}$$$ $$$[\, 0, 1, \下划线{0} \,]$$$。

它们都不能使 $$$b$$$ 等于 $$$[\, 0, 1, 1 \,]$$$,所以答案是“NO”。