103496: [Atcoder]ABC349 G - Palindrome Construction
Description
Score: $625$ points
Problem Statement
A sequence of positive integers $T=(T_1,T_2,\dots,T_M)$ of length $M$ is a palindrome if and only if $T_i=T_{M-i+1}$ for each $i=1,2,\dots,M$.
You are given a sequence of non-negative integers $A = (A_1,A_2,\dots,A_N)$ of length $N$. Determine if there is a sequence of positive integers $S=(S_1,S_2,\dots,S_N)$ of length $N$ that satisfies the following condition, and if it exists, find the lexicographically smallest such sequence.
- For each $i=1,2,\dots,N$, both of the following hold:
- The sequence $(S_{i-A_i},S_{i-A_i+1},\dots,S_{i+A_i})$ is a palindrome.
- If $2 \leq i-A_i$ and $i+A_i \leq N-1$, the sequence $(S_{i-A_i-1},S_{i-A_i},\dots,S_{i+A_i+1})$ is not a palindrome.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq A_i \leq \min\{i-1,N-i\}$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\dots$ $A_N$
Output
If there is no sequence $S$ that satisfies the condition, print No
.
If there is a sequence $S$ that satisfies the condition, let $S'$ be the lexicographically smallest such sequence and print it in the following format:
Yes $S'_1$ $S'_2$ $\dots$ $S'_N$
Sample Input 1
7 0 0 2 0 2 0 0
Sample Output 1
Yes 1 1 2 1 1 1 2
$S = (1,1,2,1,1,1,2)$ satisfies the condition:
- $i=1$: $(A_1)=(1)$ is a palindrome.
- $i=2$: $(A_2)=(1)$ is a palindrome, but $(A_1,A_2,A_3)=(1,1,2)$ is not.
- $i=3$: $(A_1,A_2,\dots,A_5)=(1,1,2,1,1)$ is a palindrome.
- $i=4$: $(A_4)=(1)$ is a palindrome, but $(A_3,A_4,A_5)=(2,1,1)$ is not.
- $i=5$: $(A_3,A_4,\dots,A_7)=(2,1,1,1,2)$ is a palindrome.
- $i=6$: $(A_6)=(1)$ is a palindrome, but $(A_5,A_6,A_7)=(1,1,2)$ is not.
- $i=7$: $(A_7)=(2)$ is a palindrome.
There are other sequences like $S=(2,2,1,2,2,2,1)$ that satisfy the condition, but print the lexicographically smallest one, which is $(1,1,2,1,1,1,2)$.
Sample Input 2
7 0 1 2 3 2 1 0
Sample Output 2
Yes 1 1 1 1 1 1 1
Sample Input 3
7 0 1 2 0 2 1 0
Sample Output 3
No
Input
Output
问题描述
一个长度为 $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})$ 不是回文序列。
限制条件
- $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