← 返回题目列表

Codeforces · 1736/D

D. 相等的二进制子序列

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

Everool 有一个长度为 $$$2n$$$ 的二进制字符串 $$$s$$$。请注意,二进制字符串是仅由字符 $$$0$$$ 和 $$$1$$$ 组成的字符串。他想将 $$$s$$$ 划分为两个不相交的相等子序列。他需要你的帮助才能做到这一点。

您只能执行以下操作一次。

- 您可以选择 $$$s$$$ 的任何子序列(可能为空)并将其向右旋转一位。

换句话说,您可以选择索引序列 $$$b_1, b_2, \ldots, b_m$$$,其中 $$$1 \le b_1 < b_2 < \ldots < b_m \le 2n$$$。之后,您同时设置 $$$$$$s_{b_1} := s_{b_m},$$$$$$ $$$$$$s_{b_2} := s_{b_1},$$$$$$ $$$$$$\ldots,$$$$$$ $$$$$$s_{b_m} := s_{b_{m-1}}.$$$$$$

在执行一次允许的操作后,您能否将 $$$s$$$ 划分为两个不相交的相等子序列?

将 $$$s$$$ 划分为两个不相交的相等子序列 $$$s^p$$$ 和 $$$s^q$$$ 是两个索引递增数组 $$$p_1, p_2, \ldots, p_n$$$ 和 $$$q_1, q_2, \ldots, q_n$$$,这样从 $$$1$$$ 到 $$$1$$$ 的每个整数$$$2n$$$ 在 $$$p$$$ 或 $$$q$$$ 中只出现一次,$$$s^p = s_{p_1} s_{p_2} \ldots s_{p_n}$$$、$$$s^q = s_{q_1} s_{q_2} \ldots s_{q_n}$$$ 和 $$$s^p = s^q$$$。

如果执行任何类型的操作后都无法分区,则报告 $$$-1$$$。

如果可以进行操作并将 $$$s$$$ 划分为两个不相交的子序列 $$$s^p$$$ 和 $$$s^q$$$,使得 $$$s^p = s^q$$$,则打印 $$$b$$$ 的元素和 $$$s^p$$$ 的索引,i。 e.值 $$$p_1、p_2、\ldots、p_n$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$),其中 $$$2n$$$ 是二进制字符串的长度。

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

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

输出

对于每个测试用例,请遵循以下输出格式。

如果无解,则打印$$$-1$$$。

否则,

- 在第一行中,打印一个整数 $$$m$$$ ($$$0 \leq m \leq 2n$$$),后跟 $$$m$$$ 不同索引 $$$b_1$$$、$$$b_2$$$、...、$$$b_m$$$(按升序排列)。
- 在第二行中,打印 $$$n$$$ 不同索引 $$$p_1$$$, $$$p_2$$$, ..., $$$p_n$$$ (按升序排列)。

如果有多个解决方案,请打印其中一个。

示例

输入 #1

4
2
1010
3
100010
2
1111
2
1110

输出 #1

0
1 2
2 3 5
1 2 5
3 2 3 4
1 4
-1

注意

在第一个测试用例中,$$$b$$$ 为空。所以字符串 $$$s$$$ 没有改变。现在$$$s^p = s_1 s_2 = \mathtt{10}$$$,$$$s^q = s_3s_4 = \mathtt{10}$$$。

在第二个测试用例中,$$$b=[3,5]$$$。最初是$$$s_3=\mathtt{0}$$$,$$$s_5=\mathtt{1}$$$。在执行操作时,我们同时设置$$$s_3=\mathtt{1}$$$和$$$s_5=\mathtt{0}$$$。

因此,执行操作时 $$$s$$$ 会更新为 101000。

现在,如果我们在 $$$s^p$$$ 中的索引 $$$[1,2,5]$$$ 处获取字符,我们会得到 $$$s_1=\mathtt{100}$$$。索引 $$$[3,4,6]$$$ 处的字符也在 $$$s^q$$$ 中。因此$$$s^q=100$$$。我们就完成了$$$s^p=s^q$$$。

在第四个测试用例中,可以证明在执行任何操作后都不可能对字符串进行分区。