P16795 [Lanqiao Cup 2026 National B] Parity-Check Permutation

A certain checking system needs to use each of the numbers $1, 2, \dots, n$ exactly once and arrange them into a sequence of length $n$, $p_1, p_2, \dots, p_n$. Such a sequence is called a permutation. The system generates a check string of length $n-1$ based on the parity of the absolute differences between adjacent numbers in the permutation. For each $1 \le i < n$, the $i$-th check character $c_i$ is determined by the following rules: * If $|p_i - p_{i+1}|$ is even, then $c_i$ is $0$. * If $|p_i - p_{i+1}|$ is odd, then $c_i$ is $1$. Now you are given a target check string $S$ of length $n-1$. You need to construct a permutation such that the generated check string $c_1 c_2 \dots c_{n-1}$ is exactly equal to $S$. If there are multiple valid permutations, output the lexicographically smallest one. For two different permutations $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$, if there exists a position $k$ such that the first $k-1$ numbers are the same and $a_k < b_k$, then permutation $a$ is lexicographically smaller than permutation $b$. If no such permutation exists, output $-1$.

The first line contains an integer $n$, representing the number of labels. The second line contains a string $S$ of length $n-1$, representing the target check string. The string consists only of characters $0$ and $1$.

If no valid permutation exists, output a single integer $-1$ on one line. Otherwise, output $n$ integers on one line, representing the lexicographically smallest valid permutation. Adjacent integers should be separated by one space.

### Sample Explanation 1 The adjacent differences of this permutation are, in order: * $|1-2|=1$, which is odd, corresponding to $1$. * $|2-4|=2$, which is even, corresponding to $0$. * $|4-3|=1$, which is odd, corresponding to $1$. * $|3-5|=2$, which is even, corresponding to $0$. Therefore, the generated check string is $1010$. Among all valid permutations, $1 \ 2 \ 4 \ 3 \ 5$ is lexicographically the smallest. ### Sample Explanation 2 Every character of the target check string is $0$, so every adjacent difference must be even, meaning the two numbers must have the same parity. Then all numbers in all positions must have the same parity, but among $1$ to $6$ there are both odd and even numbers, so there is no solution. ### Sample Explanation 3 The check string generated by the output permutation is, in order, $0$, $1$, $0$, $1$, $1$, $0$, $1$, which is the same as the target check string $0101101$. ### Constraints and Notes for Testdata For $30\%$ of the testdata, $2 \le n \le 8$. For $60\%$ of the testdata, $2 \le n \le 5000$. For all testdata, $2 \le n \le 2 \times 10^5$, and the length of $S$ is $n-1$. Translated by ChatGPT 5