← 返回题目列表

Codeforces · 1031/E

E. 三重翻转

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

给定一个数组 $$$a$$$,长度为 $$$n$$$,由零和一组成。

您可以多次执行以下操作。操作分为两步:

1. 选择三个整数 $$$1 \le x < y < z \le n$$$,组成算术级数 ($$$y - x = z - y$$$)。
2. 翻转值 $$$a_x、a_y、a_z$$$(即将 $$$1$$$ 更改为 $$$0$$$,将 $$$0$$$ 更改为 $$$1$$$)。

确定是否可以使数组的所有元素都等于 0。如果是,则打印导致全零状态的操作。您的解决方案不应包含超过 $$$(\lfloor \frac{n}{3} \rfloor + 12)$$$ 操作。这里 $$$\lfloor q \rfloor$$$ 表示数字 $$$q$$$ 向下舍入。我们可以证明,只要有可能,就可以在不超过此数量的操作中使所有元素等于零。

输入

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 10^5$$$) — 数组的长度。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 1$$$) — 数组的元素。

输出

如果答案存在,则打印“YES”(不带引号),否则打印“NO”(不带引号)。您可以以任何大小写(大写或小写)打印每个字母。

如果有答案,请在第二行中打印一个整数 $$$m$$$ ($$$0 \le m \le (\lfloor \frac{n}{3} \rfloor + 12)$$$) — 答案中的操作数。

之后,在第 ($$$i + 2$$$) 行中打印第 $$$i$$$ 操作 — 整数 $$$x_i、y_i、z_i$$$。您可以按任意顺序打印它们。

示例

输入 #1

5
1 1 0 1 1

输出 #1

YES
2
1 3 5
2 3 4

输入 #2

3
0 1 0

输出 #2

NO

注意

在第一个示例中,显示的输出对应于以下解决方案:

- 1 1 0 1 1(初始状态);
- 0 1 1 1 0(翻转位置为第一个、第三个和第五个元素);
- 0 0 0 0 0(翻转的位置是第二个、第三个和第四个元素)。

其他答案也是可能的。在此测试中,操作数不应超过 $$$\lfloor \frac{5}{3} \rfloor + 12 = 1 + 12 = 13$$$。

在第二个示例中,唯一可用的操作是翻转所有元素。这样只能得到数组0 1 0和1 0 1,但不可能让所有元素都等于0。