Equal Binary Subsequences

题意翻译

给你一个长为 $2n$ 的01串 $s$ ，你需要将其分成两个相等的子序列。 在此之前你需要执行以下操作一次： - 选一个 $s$ 的子序列（可能为空），然后将其向右循环移位一位。 具体来说，你可以选择一个下标序列 $b_1,b_2,\dots,b_m$ 满足 $1\le b_1<b_2<\dots<b_m\le 2n$ ，然后同时执行 $s_{b_1}=s_{b_m},s_{b_2}=s_{b_1},\dots,s_{b_m}=s_{b_{m-1}}$ 。 你能在执行以上操作一次后把 $s$ 分成两个相等的子序列吗？ #### Hint 把 $s$ 分成两个相等的子序列 $s^p$ 和 $s^q$ 是指找到两个下标序列 $p_1,p_2,\dots,p_n$ 和 $q_1,q_2,\dots,q_n$ ，使得从 $1$ 到 $2n$ 的每个整数都恰好在 $p$ 和 $q$ 中出现共一次，然后令 $s^p=s_{p_1}s_{p_2}\dots s_{p_n}$ ， $s^q=s_{q_1}s_{q_2}\dots s_{q_n}$ ，满足 $s^p=s^q$ 。 #### 输入格式 每一个测试点有多个测试数据。第一行一个正整数 $t$ 表示测试数据组数。对于每组数据： 第一行一个正整数 $n$ ，表示01串 $s$ 的长度为 $2n$ 。 第二行一个长为 $2n$ 的01串 $s$ 。 #### 输出格式 对于每组数据： 如果无解，输出一行 $-1$ 。 否则： - 第一行输出一个整数 $m$ $(0\le m\le 2n)$ ，接着升序输出 $m$ 个下标 $b_1,b_2,\dots,b_m$ 。 - 第二行升序输出 $n$ 个下标 $p_1,p_2,\dots,p_n$ (见Hint) 。 如果有多解，输出任意一个。 $s$ 的下标从1开始。 #### 输入输出样例 ##### 样例输入 ``` 4 2 1010 3 100010 2 1111 2 1110 ``` ##### 样例输出 ``` 0 1 2 2 3 5 1 2 5 3 2 3 4 1 4 -1 ``` ##### 样例解释 在第二个测试数据中，$b[]=\{3,5\}$ 。初始时 $s_3=0,s_5=1$ 。进行操作时，我们同时令 $s_3=1,s_5=0$ 。然后 $s$ 变成了 $101000$ 。现在我们选择 $p[]=\{1,2,5\}$ ，那么 $s^p=100$ ；自然 $q[]=\{3,4,6\}$ ，于是 $s^q=100$ 。$s^p=s^q$ 。 #### 数据范围 $1\le t\le 10^5,1\le n\le 10^5$ 。 保证同一测试点中所有数据的 $n$ 的和不超过 $10^5$ 。

题目描述

Everool has a binary string $ s $ of length $ 2n $ . Note that a binary string is a string consisting of only characters $ 0 $ and $ 1 $ . He wants to partition $ s $ into two disjoint equal subsequences. He needs your help to do it. You are allowed to do the following operation exactly once. - You can choose any subsequence (possibly empty) of $ s $ and rotate it right by one position. In other words, you can select a sequence of indices $ b_1, b_2, \ldots, b_m $ , where $ 1 \le b_1 < b_2 < \ldots < b_m \le 2n $ . After that you simultaneously set $ $s_{b_1} := s_{b_m}, $ $ $ $ s_{b_2} := s_{b_1}, $ $ $ $ \ldots, $ $ $ $ s_{b_m} := s_{b_{m-1}}. $ $ </p><p>Can you partition $ s $ into two <span class="tex-font-style-bf">disjoint equal</span> subsequences after performing the allowed operation <span class="tex-font-style-bf">exactly</span> once?</p><p>A partition of $ s $ into two disjoint equal subsequences $ s^p $ and $ s^q $ is two <span class="tex-font-style-bf">increasing</span> arrays of indices $ p\_1, p\_2, \\ldots, p\_n $ and $ q\_1, q\_2, \\ldots, q\_n $ , such that each integer from $ 1 $ to $ 2n $ is encountered in either $ p $ or $ q $ exactly once, $ s^p = s\_{p\_1} s\_{p\_2} \\ldots s\_{p\_n} $ , $ s^q = s\_{q\_1} s\_{q\_2} \\ldots s\_{q\_n} $ , and $ s^p = s^q $ .</p><p>If it is not possible to partition after performing any kind of operation, report $ -1 $ . </p><p>If it is possible to do the operation and partition $ s $ into two disjoint subsequences $ s^p $ and $ s^q $ , such that $ s^p = s^q $ , print elements of $ b $ and indices of $ s^p $ , i. e. the values $ p\_1, p\_2, \\ldots, p\_n$.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^5 $ ). Description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ), where $ 2n $ is the length of the binary string. The second line of each test case contains the binary string $ s $ of length $ 2n $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, follow the following output format. If there is no solution, print $ -1 $ . Otherwise, - In the first line, print an integer $ m $ ( $ 0 \leq m \leq 2n $ ), followed by $ m $ distinct indices $ b_1 $ , $ b_2 $ , ..., $ b_m $ (in increasing order). - In the second line, print $ n $ distinct indices $ p_1 $ , $ p_2 $ , ..., $ p_n $ (in increasing order). If there are multiple solutions, print any.

输入输出样例

输入样例 #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

说明

In the first test case, $ b $ is empty. So string $ s $ is not changed. Now $ s^p = s_1 s_2 = \mathtt{10} $ , and $ s^q = s_3s_4 = \mathtt{10} $ . In the second test case, $ b=[3,5] $ . Initially $ s_3=\mathtt{0} $ , and $ s_5=\mathtt{1} $ . On performing the operation, we simultaneously set $ s_3=\mathtt{1} $ , and $ s_5=\mathtt{0} $ . So $ s $ is updated to 101000 on performing the operation. Now if we take characters at indices $ [1,2,5] $ in $ s^p $ , we get $ s_1=\mathtt{100} $ . Also characters at indices $ [3,4,6] $ are in $ s^q $ . Thus $ s^q=100 $ . We are done as $ s^p=s^q $ . In fourth test case, it can be proved that it is not possible to partition the string after performing any operation.

题意翻译

给你一个长为 $2n$ 的01串 $s$ ，你需要将其分成两个相等的子序列。 在此之前你需要执行以下操作一次： - 选一个 $s$ 的子序列（可能为空），然后将其向右循环移位一位。 具体来说，你可以选择一个下标序列 $b_1,b_2,\dots,b_m$ 满足 $1\le b_1<b_2<\dots<b_m\le 2n$ ，然后同时执行 $s_{b_1}=s_{b_m},s_{b_2}=s_{b_1},\dots,s_{b_m}=s_{b_{m-1}}$ 。 你能在执行以上操作一次后把 $s$ 分成两个相等的子序列吗？ #### Hint 把 $s$ 分成两个相等的子序列 $s^p$ 和 $s^q$ 是指找到两个下标序列 $p_1,p_2,\dots,p_n$ 和 $q_1,q_2,\dots,q_n$ ，使得从 $1$ 到 $2n$ 的每个整数都恰好在 $p$ 和 $q$ 中出现共一次，然后令 $s^p=s_{p_1}s_{p_2}\dots s_{p_n}$ ， $s^q=s_{q_1}s_{q_2}\dots s_{q_n}$ ，满足 $s^p=s^q$ 。 #### 输入格式 每一个测试点有多个测试数据。第一行一个正整数 $t$ 表示测试数据组数。对于每组数据： 第一行一个正整数 $n$ ，表示01串 $s$ 的长度为 $2n$ 。 第二行一个长为 $2n$ 的01串 $s$ 。 #### 输出格式 对于每组数据： 如果无解，输出一行 $-1$ 。 否则： - 第一行输出一个整数 $m$ $(0\le m\le 2n)$ ，接着升序输出 $m$ 个下标 $b_1,b_2,\dots,b_m$ 。 - 第二行升序输出 $n$ 个下标 $p_1,p_2,\dots,p_n$ (见Hint) 。 如果有多解，输出任意一个。 $s$ 的下标从1开始。 #### 输入输出样例 ##### 样例输入 ``` 4 2 1010 3 100010 2 1111 2 1110 ``` ##### 样例输出 ``` 0 1 2 2 3 5 1 2 5 3 2 3 4 1 4 -1 ``` ##### 样例解释 在第二个测试数据中，$b[]=\{3,5\}$ 。初始时 $s_3=0,s_5=1$ 。进行操作时，我们同时令 $s_3=1,s_5=0$ 。然后 $s$ 变成了 $101000$ 。现在我们选择 $p[]=\{1,2,5\}$ ，那么 $s^p=100$ ；自然 $q[]=\{3,4,6\}$ ，于是 $s^q=100$ 。$s^p=s^q$ 。 #### 数据范围 $1\le t\le 10^5,1\le n\le 10^5$ 。 保证同一测试点中所有数据的 $n$ 的和不超过 $10^5$ 。