分数: 7 点
警告
2021 年 10 月 2 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。
问题陈述
给定一个字符串 S 长度 N 组成 0 和 1,找到长度的序列 N, P=(P_1, P_2, \dots, P_N),满足以下所有条件。如果不存在这样的序列,则打印 -1.
- P 是一个排列 (1,2,\dots,N).
- 以下内容适用于每个 1 \le i \le N.
- P_i=i 如果 i- 第一个字符 S is
1; - P_i \neq i 如果 i- 第一个字符 S is
0.
- P_i=i 如果 i- 第一个字符 S is
约束
- 1 \le N \le 10^5
- S 包括
0和1.
输入
输入由标准输入按以下格式给出:
N S
输出
如果没有序列 P 满足条件,打印 -1.
如果这样的序列 P 存在,将其元素打印为整数,中间有空格。
示例输入 1
5 10101
示例输出 1
1 4 3 2 5
第一个、第三个和第五个字符 S 是 1,所以我们必须有 P_1=1,P_3=3,P_5=5.
第二个和第四个字符 S 是 0,所以我们必须有 P_2 \neq 2, P_4 \neq 4.
在这种情况下,唯一的序列
满足要求的 P 是 (1,4,3,2,5).
示例输入 2
4 1110
示例输出 2
-1
如果没有序列 P 满足条件,打印 -1.
示例输入 3
12 001110110010
示例输出 3
12 6 3 4 5 1 7 8 2 9 11 10
还有其他有效输出,例如:
2 1 3 4 5 9 7 8 10 12 11 6