P16795 [蓝桥杯 2026 国 B] 奇偶校验排列

某个校验系统需要把 $1, 2, \dots, n$ 这 $n$ 个编号各使用一次，排成一个长度为 $n$ 的序列 $p_1, p_2, \dots, p_n$。这样的序列称为一个排列。 系统会根据排列中相邻两个编号的差值奇偶性生成一个长度为 $n-1$ 的校验串。对于每个 $1 \le i < n$，第 $i$ 位校验字符 $c_i$ 按如下规则确定： * 如果 $|p_i - p_{i+1}|$ 为偶数，则 $c_i$ 为 $0$； * 如果 $|p_i - p_{i+1}|$ 为奇数，则 $c_i$ 为 $1$。 现在给定一个长度为 $n-1$ 的目标校验串 $S$。你需要构造一个排列，使它生成的校验串 $c_1 c_2 \dots c_{n-1}$ 恰好等于 $S$。 如果存在多个满足要求的排列，请输出字典序最小的一个。对于两个不同排列 $a_1, a_2, \dots, a_n$ 与 $b_1, b_2, \dots, b_n$，若存在位置 $k$，使得前 $k-1$ 个数都相同且 $a_k < b_k$，则称排列 $a$ 的字典序小于排列 $b$。 如果不存在满足要求的排列，请输出 $-1$。

第一行包含一个整数 $n$，表示编号数量。 第二行包含一个长度为 $n-1$ 的字符串 $S$，表示目标校验串，字符串仅由字符 $0$ 和 $1$ 组成。

如果不存在满足要求的排列，输出一行一个整数 $-1$。 否则输出一行 $n$ 个整数，表示字典序最小的合法排列。相邻两个整数之间用一个空格分隔。

### 【样例说明 1】 该排列对应的相邻差值依次为： * $|1-2|=1$，为奇数，对应 $1$； * $|2-4|=2$，为偶数，对应 $0$； * $|4-3|=1$，为奇数，对应 $1$； * $|3-5|=2$，为偶数，对应 $0$。 因此生成的校验串为 $1010$。在所有合法排列中，$1 \ 2 \ 4 \ 3 \ 5$ 的字典序最小。 ### 【样例说明 2】 目标校验串的每一位都是 $0$，因此任意相邻两个编号的差值都必须为偶数，也就是它们奇偶性相同。这样所有位置上的编号都必须具有相同奇偶性，但 $1$ 到 $6$ 中既有奇数也有偶数，所以无解。 ### 【样例说明 3】 输出排列生成的校验串依次为 $0$、$1$、$0$、$1$、$1$、$0$、$1$，与目标校验串 $0101101$ 相同。 ### 【评测用例规模与约定】 对于 $30\%$ 的评测用例，$2 \le n \le 8$。 对于 $60\%$ 的评测用例，$2 \le n \le 5000$。 对于所有评测用例，$2 \le n \le 2 \times 10^5$，且 $S$ 的长度为 $n-1$。