Colorful Doors
题意翻译
有 $N$ 对传送门将一条路径划分为 $2N+1$ 段。
你从路径最左端开始一直向右走。当你从左侧到达一个传送门时,你会被立刻传送到和此传送门配对的传送门右侧。可以证明,不管传送门如何配对,你总是能到达路径尽头。
现在给定一个 $01$ 串表示每一段路是否被你经过过,请你构造出一种合法的配对方案或是指出这个 $01$ 串是错误的。
显然你一定会经过第一段和最后一段,所以输入的 $01$ 串只有 $2N-1$ 位。
$N \le 10^5$
题目描述
[problemUrl]: https://atcoder.jp/contests/apc001/tasks/apc001_g
左岸と右岸を繋ぐ橋があります。 橋の上の相異なる $ 2\ N $ 箇所には、それぞれある色のドアが置かれています。 各ドアの色は $ 1 $ から $ N $ までの整数で表されます。 各 $ k $ ($ 1\ \leq\ k\ \leq\ N $) について、色 $ k $ のドアはちょうど $ 2 $ 個存在します。
すぬけ君は、左岸から右岸へ橋を渡ることにしました。 すぬけ君は常に右へ向かって歩き続けますが、その間に次の現象が起こります。
- すぬけ君が色 $ k $ ($ 1\ \leq\ k\ \leq\ N $) のドアに触れた瞬間、すぬけ君は色 $ k $ の他方のドアのすぐ右へワープする。
すぬけ君はいずれ右岸に辿り着くことが示せます。
各 $ i $ ($ 1\ \leq\ i\ \leq\ 2\ N\ -\ 1 $) について、左から $ i $ 番目および $ i\ +\ 1 $ 番目のドアに挟まれた区間を、区間 $ i $ と呼ぶことにします。 橋を渡り終えたすぬけ君は、各 $ i $ ($ 1\ \leq\ i\ \leq\ 2\ N\ -\ 1 $) について、区間 $ i $ を歩いたか否かを記録しました。 この記録が、長さ $ 2\ N\ -\ 1 $ の文字列 $ s $ として与えられます。 各 $ i $ ($ 1\ \leq\ i\ \leq\ 2\ N\ -\ 1 $) について、すぬけ君が区間 $ i $ を歩いたならば、$ s $ の $ i $ 文字目は `1` であり、そうでないならば、$ s $ の $ i $ 文字目は `0` です。
![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT_apc001_g/382d80e27f27c219051337ea977a9f0803e973e4.png)図: 入力例 3 に対応するドアの配置の例
記録に矛盾しないようなドアの配置が存在するか判定し、存在するならばひとつ構成してください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ s $
输出格式
記録に矛盾しないようなドアの配置が存在しないならば、`No` を出力せよ。 存在するならば、$ 1 $ 行目に `Yes` を出力し、$ 2 $ 行目にドアの配置をひとつ次のフォーマットで出力せよ。 ただし、各 $ i $ ($ 1\ \leq\ i\ \leq\ 2\ N $) について、$ c_i $ は左から $ i $ 番目のドアの色である。
> $ c_1 $ $ c_2 $ $ ... $ $ c_{2\ N} $
输入输出样例
输入样例 #1
2
010
输出样例 #1
Yes
1 1 2 2
输入样例 #2
2
001
输出样例 #2
No
输入样例 #3
3
10110
输出样例 #3
Yes
1 3 2 1 2 3
输入样例 #4
3
10101
输出样例 #4
No
输入样例 #5
6
00111011100
输出样例 #5
Yes
1 6 1 2 3 4 4 2 3 5 6 5
说明
### 制約
- $ 1\ \leq\ N\ \leq\ 10^5 $
- $ |s|\ =\ 2\ N\ -\ 1 $
- $ s $ は `0` と `1` のみからなる。
### Sample Explanation 3
以下の図は問題文中のものと同様です。 !\[\](https://img.atcoder.jp/cookie/970b981380ffad7745008433034c0885.png)