AT_abc349_g [ABC349G] Palindrome Construction

题目描述

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

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

• 对于每个 $i=1,2,\dots,N$，都满足以下两点：
  • 序列 $(S_{i-A_i},S_{i-A_i+1},\dots,S_{i+A_i})$ 是回文的。
  • 如果 $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})$ 不是回文的。

输入格式

输入通过标准输入给出，格式如下：

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

如果不存在满足条件的 $S$，输出 No。

如果存在，输出 Yes，以及字典序最小的满足条件的 $S'=(S'_1,S'_2,\dots,S'_N)$，格式如下：

Yes $S'_1$ $S'_2$ $\dots$ $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\leq N\leq 2\times 10^5$
• $0\leq A_i\leq \min\{i-1,N-i\}$
• 输入均为整数

样例解释 1

可以确认 $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)$。

由 ChatGPT 4.1 翻译