P3677 [CERC2016] Key Knocking

Goran is recovering from knee surgery and is experimenting with smart card encryption keys for storage. In this problem, a key is a binary sequence of length $3n$, where $n$ is a positive integer. The bits of the sequence are numbered from left to right as $1$ to $3n$. The weight of a key is defined as the number of positions where adjacent bits differ, plus $1$. For example, the weight of "000" is $1$, and the weight of "011010100" is $7$. He finds that he can send small current pulses to modify the circuits of the smart card, thereby modifying the key. Specifically, he can repeatedly perform the following operation: choose any two adjacent bits and flip them both. For example, he can change "000" to "110" in one operation. Given a key of length $3n$, perform at most $n$ operations to transform it into a key with weight at least $2n$. You may assume that a valid solution always exists.

One line containing a binary string representing the initial key. Its length is exactly $3n$, where $1 \le n \le 100000$.

The first line contains an integer $m$ denoting the number of operations, with $0 \le m \le n$. The second line contains $m$ positive integers $a_1, a_2, \ldots, a_m$ ($1 \le a_i < 3n$), in order indicating that in the $i$-th operation you flip bits at positions $a_i$ and $a_i + 1$. If the initial key already has weight at least $2n$, you may output a single line containing the integer $0$.

Translated by ChatGPT 5