AT_past202109_f.不完全順列

给定一个长度为 $N$、仅由 0 和 1 组成的字符串 $S$，请你求出一个满足以下所有条件的长度为 $N$ 的数列 $P=(P_1,P_2,\dots,P_N)$。如果不存在这样的数列，请输出 -1。

• 数列 $P$ 是 $1,2,\dots,N$ 的一个排列，即 $P$ 是 $1,2,\dots,N$ 的一个重排。
• 对于所有 $1\le i\le N$，都满足以下条件：
  • 如果 $S$ 的第 $i$ 个字符为 1，则 $P_i=i$。
  • 如果 $S$ 的第 $i$ 个字符为 0，则 $P_i\neq i$。

输入从标准输入中给出，格式如下：

$N$ $S$

如果不存在满足条件的数列 $P$，请输出 -1。
如果存在，输出数列 $P$ 的每一项，整数之间用空格分隔。

注意

本题在 2021/10/02 18:00 JST 之前禁止讨论。如果有相关讨论，可能会被要求赔偿。考试结束后可以公开总分和认证等级，但请不要透露解了哪些题等信息。

约束条件

• $1\le N\le 10^5$
• $S$ 仅由 0 和 1 组成。

样例解释 1

$S$ 的第 $1,3,5$ 个字符为 1，因此 $P_1=1,P_3=3,P_5=5$ 必须成立。$S$ 的第 $2,4$ 个字符为 0，因此 $P_2\neq 2,P_4\neq 4$ 必须成立。在本输入下，唯一满足条件的数列 $P$ 是 $(1,4,3,2,5)$。

样例解释 2

如果不存在满足条件的数列 $P$，请输出 -1。

样例解释 3

此外，以下输出也是正确答案之一。

2 1 3 4 5 9 7 8 10 12 11 6

由 ChatGPT 4.1 翻译