F - 不完全順列 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 7 点

問題文

長さ 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 である。

制約

  • 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,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

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

Score : 7 points

Warning

Do not make any mention of this problem until October 2, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given a string S of length N consisting of 0 and 1, find a sequence of length N, P=(P_1, P_2, \dots, P_N), that satisfies all of the following conditions. If no such sequence exists, print -1.

  • P is a permutation of (1,2,\dots,N).
  • The following holds for every 1 \le i \le N.
    • P_i=i if the i-th character of S is 1;
    • P_i \neq i if the i-th character of S is 0.

Constraints

  • 1 \le N \le 10^5
  • S consists of 0 and 1.

Input

Input is given from Standard Input in the following format:

N
S

Output

If there is no sequence P that satisfies the conditions, print -1.
If such a sequence P exists, print its elements as integers, with spaces in between.

Sample Input 1

5
10101

Sample Output 1

1 4 3 2 5

The first, third, and fifth characters of S are 1, so we must have P_1=1,P_3=3,P_5=5.
The second and fourth characters of S are 0, so we must have P_2 \neq 2, P_4 \neq 4.
In this case, the only sequence P that satisfies the requirements is (1,4,3,2,5).

Sample Input 2

4
1110

Sample Output 2

-1

If there is no sequence P that satisfies the conditions, print -1.

Sample Input 3

12
001110110010

Sample Output 3

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

There are also other valid outputs, such as:

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