#P13502. [ABC349G] Palindrome Construction

    ID: 12686 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-Manacher普通并查集顶点着色mex 计算序列构造时间戳避免清空数组

[ABC349G] Palindrome Construction

AT_abc349_g [ABC349G] Palindrome Construction

题目描述

我们称长度为 MM 的正整数序列 T=(T1,T2,…,TM)T=(T_1,T_2,\dots,T_M) 是回文的,当且仅当对于每个 i=1,2,…,Mi=1,2,\dots,M,都有 Ti=TM−i+1T_i=T_{M-i+1}。

给定一个长度为 NN 的非负整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\dots,A_N)。请判断是否存在一个满足下述条件的长度为 NN 的正整数序列 S=(S1,S2,…,SN)S=(S_1,S_2,\dots,S_N),如果存在,请输出所有满足条件的序列中字典序最小的一个。

  • 对于每个 i=1,2,…,Ni=1,2,\dots,N,都满足以下两点:
    • 序列 (Si−Ai,Si−Ai+1,…,Si+Ai)(S_{i-A_i},S_{i-A_i+1},\dots,S_{i+A_i}) 是回文的。
    • 如果 2≤i−Ai2\leq i-A_i 且 i+Ai≤N−1i+A_i\leq N-1,则序列 (Si−Ai−1,Si−Ai,…,Si+Ai+1)(S_{i-A_i-1},S_{i-A_i},\dots,S_{i+A_i+1}) 不是回文的。

输入格式

输入通过标准输入给出,格式如下:

NN A1A_1 A2A_2 …\dots ANA_N

输出格式

如果不存在满足条件的 SS,输出 No。

如果存在,输出 Yes,以及字典序最小的满足条件的 S′=(S1′,S2′,…,SN′)S'=(S'_1,S'_2,\dots,S'_N),格式如下:

Yes S1′S'_1 S2′S'_2 …\dots SN′S'_N

输入输出样例 #1

输入 #1

7
0 0 2 0 2 0 0

输出 #1

Yes
1 1 2 1 1 1 2

输入输出样例 #2

输入 #2

7
0 1 2 3 2 1 0

输出 #2

Yes
1 1 1 1 1 1 1

输入输出样例 #3

输入 #3

7
0 1 2 0 2 1 0

输出 #3

No

说明/提示

限制条件

  • 1≤N≤2×1051\leq N\leq 2\times 10^5
  • 0≤Ai≤min⁡{i−1,N−i}0\leq A_i\leq \min\{i-1,N-i\}
  • 输入均为整数

样例解释 1

可以确认 S=(1,1,2,1,1,1,2)S=(1,1,2,1,1,1,2) 满足条件。

  • i=1i=1:(A1)=(1)(A_1)=(1) 是回文。
  • i=2i=2:(A2)=(1)(A_2)=(1) 是回文,且 (A1,A2,A3)=(1,1,2)(A_1,A_2,A_3)=(1,1,2) 不是回文。
  • i=3i=3:(A1,A2,…,A5)=(1,1,2,1,1)(A_1,A_2,\dots,A_5)=(1,1,2,1,1) 是回文。
  • i=4i=4:(A4)=(1)(A_4)=(1) 是回文,且 (A3,A4,A5)=(2,1,1)(A_3,A_4,A_5)=(2,1,1) 不是回文。
  • i=5i=5:(A3,A4,…,A7)=(2,1,1,1,2)(A_3,A_4,\dots,A_7)=(2,1,1,1,2) 是回文。
  • i=6i=6:(A6)=(1)(A_6)=(1) 是回文,且 (A5,A6,A7)=(1,1,2)(A_5,A_6,A_7)=(1,1,2) 不是回文。
  • i=7i=7:(A7)=(2)(A_7)=(2) 是回文。

除此之外,S=(2,2,1,2,2,2,1)S=(2,2,1,2,2,2,1) 等也满足条件,但字典序最小的是 (1,1,2,1,1,1,2)(1,1,2,1,1,1,2)。