261 . 小風愛迴文
TopCoder
Tags
Description
小風拿到了一個正整數序列 $s_1, s_2, \ldots, s_n$，他很興奮地算出對每個正整數 $i$，以第 $i$ 項為結尾的最長迴文子區間的長度為 $c_i$，但是他現在卻丟失了原來的序列，身為小風的好朋友，請你幫幫他找出一組序列滿足條件吧。
Input Format
輸入第一行只有一個正整數 $n$，代表序列的長度。
輸入第二行有 $n$ 個正整數 $c_1,\ c_2, \ldots,\ c_n$，代表以第 $i$ 項為結尾的最長迴文子區間長度。
- $2 \leq n \leq 2 \times 10^ 5$
Output Format
對於每一組輸入，請輸出一行包含 $n$ 個正整數 $s_1, s_2, \ldots, s_n$ 滿足題目條件，其中 $s_i$ 需滿足 $1 \leq s_i \leq 10^ 9$。輸入保證至少存在一組序列滿足題目條件。
若存在多組滿足條件的序列，請輸出任意一組。
Sample Input 1
3
1 1 2
1 1 2
Sample Output 1
1 2 2
Sample Input 2
5
1 1 3 3 5
1 1 3 3 5
Sample Output 2
1 2 1 2 1
Hints
如果一個區間$s_l, s_{l + 1}, \ldots, s_r$ 滿足對所有 $l \leq i \leq r$ 都有 $s_i = s_{l + r - i}$，那麼這個區間就被稱為迴文子區間。
請注意你可以用的不同數字一共有 $10^ 9$ 個。
Problem Source
IOICamp 2020 Day4 pE
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~49 | 無額外限制 | 100 |