← 返回题目列表

Codeforces · 1889/A

A. 青山爱弦2

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

青山有一个字符串$$$s$$$,它只包含$$$\texttt{0}$$$和$$$\texttt{1}$$$。

长度为 $$$k$$$ 的字符串 $$$a$$$ 是好的当且仅当

- $$$a_i \ne a_{k-i+1}$$$ 对于所有 $$$i=1,2,\ldots,k$$$。

对于分区。 2位参赛者,注意这个条件与问题B中的条件不同。

例如,$$$\texttt{10}$$$、$$$\texttt{1010}$$$、$$$\texttt{111000}$$$ 都不错,而 $$$\texttt{11}$$$、$$$\texttt{101}$$$、$$$\texttt{001}$$$、 $$$\texttt{001100}$$$ 不好。

青山想让$$$s$$$变得更好。为此,她最多可以执行以下操作 $$$300$$$ 次(可能为零):

- 将 $$$\texttt{01}$$$ 插入到 $$$s$$$ 的任意位置(获取新的 $$$s$$$)。

请告诉青山是否可以让$$$s$$$变得更好。如果可能的话,打印一系列使 $$$s$$$ 变好的操作。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n\le 100$$$) — 分别是字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含一个字符串 $$$s$$$,长度为 $$$n$$$。

保证 $$$s$$$ 仅由 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$ 组成。

输出

对于每个测试用例,如果不可能使 $$$s$$$ 良好,则输出 $$$-1$$$。

否则,在第一行输出 $$$p$$$ ($$$0 \le p \le 300$$$) — 操作数。

然后,在第二行输出$$$p$$$整数。第 $$$i$$$ 个整数应该是索引 $$$x_i$$$ ($$$0 \le x_i \le n+2i-2$$$) - 您要在当前 $$$s$$$ 中插入 $$$\texttt{01}$$$ 的位置。如果 $$$x_i=0$$$,则在 $$$s$$$ 的开头插入 $$$\texttt{01}$$$。否则,您将在 $$$s$$$ 的第 $$$x_i$$$ 个字符之后插入 $$$\texttt{01}$$$。

我们可以证明,在这个问题的约束下,如果存在答案,则总有一个最多需要 $$$300$$$ 操作的答案。

示例

输入 #1

6
2
01
3
000
4
1111
6
001110
10
0111001100
3
001

输出 #1

0

-1
-1
2
6 7
1
10
-1

注意

在第一个测试用例中,您可以进行零运算并得到 $$$s=\texttt{01}$$$,这很好。

另一种有效的解决方案是执行一个操作:(插入的 $$$\texttt{01}$$$ 带下划线)

1.$$$\texttt{0}\下划线{\texttt{01}}\texttt{1}$$$

并得到 $$$s = \texttt{0011}$$$,这很好。

在第二个和第三个测试用例中,不可能使$$$s$$$ 变得良好。

在第四个测试用例中,可以进行两个操作:

1.$$$\texttt{001110}\underline{\texttt{01}}$$$
2.$$$\texttt{0011100}\下划线{\texttt{01}}\texttt{1}$$$

并得到 $$$s = \texttt{0011100011}$$$,这很好。