AT_past202109_f 不完全順列

[problemUrl]: https://atcoder.jp/contests/past202109-open/tasks/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` のみからなる。 ### Sample Explanation 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) $ のみです。 ### Sample Explanation 2 条件を満たす数列 $ P $ が存在しない場合、 `-1` と出力してください。 ### Sample Explanation 3 他にも、以下のような出力も正答と扱われます。 ``` 2 1 3 4 5 9 7 8 10 12 11 6 ```