← 返回题目列表

AtCoder · abc349_g

G. 回文构造

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

分数: 625 点

问题陈述

正整数序列 T=(T_1,T_2,\dots,T_M) 长度 M 是 回文 当且仅当 T_i=T_{M-i+1} 对于每个 i=1,2,\dots,M.

给你一个非负整数序列 A = (A_1,A_2,\dots,A_N) 长度 N。判断是否存在正整数序列 S=(S_1,S_2,\dots,S_N) 长度 N 满足以下条件,如果存在,找到字典顺序最小的这样的序列。

  • 对于每个 i=1,2,\dots,N,以下两者均成立:
    • 序列 (S_{i-A_i},S_{i-A_i+1},\dots,S_{i+A_i}) 是一个回文。
    • If 2 \leq i-A_i 和 i+A_i \leq N-1,序列 (S_{i-A_i-1},S_{i-A_i},\dots,S_{i+A_i+1}) 不是回文。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq A_i \leq \min\{i-1,N-i\}
  • 所有输入值均为整数。

输入

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

N
A_1 A_2 \dots A_N

输出

如果没有序列 S 满足条件,打印 No.

如果有一个序列 S 满足条件,让 S' 是按字典顺序最小的此类序列,并按以下格式打印:

Yes
S'_1 S'_2 \dots S'_N

示例输入 1

7
0 0 2 0 2 0 0

示例输出 1

Yes
1 1 2 1 1 1 2

S = (1,1,2,1,1,1,2) 满足条件:

  • i=1: (A_1)=(1) 是一个回文。
  • i=2: (A_2)=(1) 是一个回文数,但是 (A_1,A_2,A_3)=(1,1,2) 不是。
  • i=3: (A_1,A_2,\dots,A_5)=(1,1,2,1,1) 是一个回文。
  • i=4: (A_4)=(1) 是一个回文数,但是 (A_3,A_4,A_5)=(2,1,1) 不是。
  • i=5: (A_3,A_4,\dots,A_7)=(2,1,1,1,2) 是一个回文。
  • i=6: (A_6)=(1) 是一个回文数,但是 (A_5,A_6,A_7)=(1,1,2) 不是。
  • i=7: (A_7)=(2) 是一个回文。

还有其他序列,例如 S=(2,2,1,2,2,2,1) 满足条件,但打印字典顺序最小的一个,即 (1,1,2,1,1,1,2).


示例输入 2

7
0 1 2 3 2 1 0

示例输出 2

Yes
1 1 1 1 1 1 1

示例输入 3

7
0 1 2 0 2 1 0

示例输出 3

No