← 返回题目列表

AtCoder · past202109_f

F. 不完全排列

中文机器翻译题面 查看原题

分数: 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.

约束

  • 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