/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 625 点
問題文
長さ 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
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