分数: 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