Flipping Binary String

The operation looks annoying because choosing index $i$ leaves $s_i$ alone and flips everything else. The trick is to stop simulating. The order of operations does not matter: each position only cares how many times it gets flipped.

Assume we perform exactly $k$ operations, choosing a set $T$ of $k$ distinct indices.

For a position $p$:

• If $p \in T$, then during its own operation it is not flipped, but during the other $k-1$ operations it is flipped. So it is flipped $k-1$ times.
• If $p \notin T$, then every operation flips it. So it is flipped $k$ times.

Only parity matters, because flipping twice cancels out.

Now split by parity of $k$.

If $k$ is even:

• Chosen positions are flipped $k-1$, an odd number of times, so they must start as 1 to become 0.
• Unchosen positions are flipped $k$, an even number of times, so they must already be 0.

Therefore, when $k$ is even, the chosen set is forced: it must be exactly all positions where $s_i = 1$. This works exactly when the number of ones is even.

If $k$ is odd:

• Chosen positions are flipped $k-1$, an even number of times, so they must already be 0.
• Unchosen positions are flipped $k$, an odd number of times, so they must start as 1.

Therefore, when $k$ is odd, the chosen set is also forced: it must be exactly all positions where $s_i = 0$. This works exactly when the number of zeros is odd.

So the entire problem collapses to two possible constructions:

1. If the number of 1s is even, choose every 1 position.
2. Otherwise, if the number of 0s is odd, choose every 0 position.
3. Otherwise, output $-1$.

There is no hidden third option. Once $k$'s parity is fixed, every index is forced by its starting bit. If both candidate parities fail, the string is cooked.

Edge cases:

• Already all zero: the number of ones is $0$, which is even, so output $0$ operations.
• $n=1$: 0 needs $0$ operations, while 1 is impossible.
• If both constructions are possible, either is fine. Choosing all ones first is shorter often enough, but minimization is irrelevant.

The algorithm just scans the string, stores positions of zeros and ones, then prints one of the two valid lists.

Complexity is $O(n)$ per test case, with $O(n)$ extra memory for the answer indices.