← 返回题目列表

AtCoder · apc001_g

G. 彩色门

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

分数: 2000 点

问题陈述

有一座桥连接河流的左岸和右岸。 有 2 N 门放置在这座桥上的不同位置,涂有一些颜色。 门的颜色由整数表示 1 通过 N。 对于每个 k (1 \leq k \leq N),正好有两扇涂有颜色的门 k.

Snuke决定从左岸过桥到右岸。 他会继续向右走,但这样做时会发生以下事件:

  • 此刻 Snuke 触摸了一扇涂有彩色的门 k (1 \leq k \leq N),他传送到另一扇涂有颜色的门的右侧 k.

可以证明他最终会到达正确的银行。

对于每个 i (1 \leq i \leq 2 N - 1),之间的部分 i-th 和 (i + 1)左数第门将被称为“部分” i。 过桥后,Snuke记录了自己是否走过了Section i,对于每个 i (1 \leq i \leq 2 N - 1)。 该记录以字符串形式提供给您 s 长度 2 N - 1。 对于每个 i (1 \leq i \leq 2 N - 1),如果 Snuke 走过部分 i, i- 第一个字符 s is 1;否则, i- 第一个字符是 0.

图:样本输入 3 的门的可能布置

确定是否存在与记录一致的门排列。如果存在,构建一个这样的安排。

约束

  • 1 \leq N \leq 10^5
  • |s| = 2 N - 1
  • s 包括 0 和 1.

输入

输入由标准输入按以下格式给出:

N
s

输出

如果没有与记录一致的门排列,则打印 No。 如果存在这样的安排,则打印 Yes 在第一行,然后在第二行打印一个这样的排列,格式如下:

c_1 c_2 ... c_{2 N}

在这里,对于每个 i (1 \leq i \leq 2 N), c_i 是颜色 i左起第 3 扇门。


示例输入 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