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\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 翻译