Hard Cut

题意翻译

给定一个 `01` 字符串 $s$。 你需要对其进行划分，使得最终把每一段当做二进制数加起来后得到的数是 $2$ 的幂。 有解输出任意一组解，无解输出 `-1`。 ### 输入格式 第一行输入一个整数 $t(1\leq t\leq10^5)$ 表示数据组数。接下来对于每组数据： 输入一行一个 `01` 字符串 $s(1\leq |s|,\sum |s|\leq10^6)$。 ### 输出格式 对于每组数据： 如果无解，输出 `-1`。 否则，首先输出一行一个整数 $k$ 表示划分的子段数。 接下来输出 $k$ 行，第 $i$ 行两个整数 $l_i,r_i(1\leq l_i\leq r_i\leq n)$ 表示你划分出的子段。 你划分的子段应该两两不相交，且包含 $s$ 中的每个字符。 ### 样例解释 对于第二组数据，样例将 $\texttt{"01101"}$ 划分成了 $\texttt{"011","0","1"}$。 因为 $(011)_2+(0)_2+(1)_2=3+0+1=4=2^2$，因此满足要求。

题目描述

You are given a binary string $ s $ . You have to cut it into any number of non-intersecting substrings, so that the sum of binary integers denoted by these substrings is a power of 2. Each element of $ s $ should be in exactly one substring.

输入输出格式

输入格式

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. Each test case contains a binary string $ s $ ( $ 1 \le |s| \le 10^6 $ ). It is guaranteed that the sum of $ |s| $ over all test cases does not exceed $ 10^6 $ .

输出格式

For each test case output the answer to the problem as follows: - If the answer does not exist, output $ -1 $ . - If the answer exists, firstly output an integer $ k $ — the number of substrings in the answer. After that output $ k $ non-intersecting substrings, for $ i $ -th substring output two integers $ l_i, r_i $ ( $ 1 \le l_i, r_i \le |s| $ ) — the description of $ i $ -th substring. If there are multiple valid solutions, you can output any of them.

输入输出样例

输入样例 #1

4
00000
01101
0111011001011
000111100111110

输出样例 #1

-1

3
1 3
4 4
5 5

8
1 2
3 3
4 4
5 6
7 7
8 10
11 12
13 13

5
1 5
6 7
8 11
12 14
15 15

说明

In the first test case it is impossible to cut the string into substrings, so that the sum is a power of 2. In the second test case such cut is valid: - $ 011_2 = 3_{10} $ , - $ 0_2 = 0_{10} $ , - $ 1_2 = 1_{10} $ . $ 3 + 0 + 1 = 4 $ , $ 4 $ is a power of 2.

**题目大意**：

给定一个由`0`和`1`组成的字符串`s`。需要对`s`进行划分，使得每个划分出来的子段作为二进制数相加的和是2的幂。如果存在这样的划分，则输出任意一组解；如果不存在，则输出`-1`。

**输入格式**：

第一行输入一个整数`t`（$1 \leq t \leq 10^5$），表示数据组数。接下来对于每组数据：

- 输入一行一个`01`字符串`s`（$1 \leq |s|, \sum |s| \leq 10^6$）。

**输出格式**：

对于每组数据：

- 如果无解，输出`-1`。
- 否则，首先输出一行一个整数`k`表示划分的子段数。
- 接下来输出`k`行，每行两个整数$l_i, r_i$（$1 \leq l_i \leq r_i \leq n$）表示划分出的子段。
- 划分的子段应两两不相交，并且包含`s`中的每个字符。

**样例解释**：

对于第二组数据，样例将`"01101"`划分成了`"011"`, `"0"`, `"1"`。
因为$(011)_2 + (0)_2 + (1)_2 = 3 + 0 + 1 = 4 = 2^2$，所以满足要求。**题目大意**： 给定一个由`0`和`1`组成的字符串`s`。需要对`s`进行划分，使得每个划分出来的子段作为二进制数相加的和是2的幂。如果存在这样的划分，则输出任意一组解；如果不存在，则输出`-1`。 **输入格式**： 第一行输入一个整数`t`（$1 \leq t \leq 10^5$），表示数据组数。接下来对于每组数据： - 输入一行一个`01`字符串`s`（$1 \leq |s|, \sum |s| \leq 10^6$）。 **输出格式**： 对于每组数据： - 如果无解，输出`-1`。 - 否则，首先输出一行一个整数`k`表示划分的子段数。 - 接下来输出`k`行，每行两个整数$l_i, r_i$（$1 \leq l_i \leq r_i \leq n$）表示划分出的子段。 - 划分的子段应两两不相交，并且包含`s`中的每个字符。 **样例解释**： 对于第二组数据，样例将`"01101"`划分成了`"011"`, `"0"`, `"1"`。 因为$(011)_2 + (0)_2 + (1)_2 = 3 + 0 + 1 = 4 = 2^2$，所以满足要求。