[Solution] Hard Cut Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Hard Cut Codeforces Solution | Codeforces Problem Solution 2022

H. Hard Cut

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡$t$ (1≤𝑡≤105$1\le t\le {10}^5$). Description of the test cases follows.

Solution Click Below:-  CLICK HERE

Each test case contains a binary string 𝑠$s$ (1≤|𝑠|≤106$1\le |s|\le {10}^6$).

It is guaranteed that the sum of |𝑠|$|s|$ over all test cases does not exceed 106${10}^6$.

Output

For each test case output the answer to the problem as follows:

• If the answer does not exist, output −1$-1$.

Another String Minimization Problem Codeforces Solution

Making Towers Codeforces Solution

Qpwoeirut And The City Codeforces Solution

Chopping Carrots (Easy Version) Codeforces Solution

Chopping Carrots (Hard Version) Codeforces Solution

• 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≤𝑙𝑖,𝑟𝑖≤|𝑠|$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.