1141C.md (1440B)
1 Source: https://codeforces.com/problemset/problem/1141/C 2 3 C. Polycarp Restores Permutation 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 An array of integers $p_1, p_2, \dots, p_n$ is called a permutation if it contains each number from $1$ to $n$ exactly once. For example, the following arrays are permutations: $[3, 1, 2]$, $[1]$, $[1, 2, 3, 4, 5]$ and $[4, 3, 1, 2]$. The following arrays are not permutations: $[2]$, $[1, 1]$, $[2, 3, 4]$. 22 23 Polycarp invented a really cool permutation $p_1, p_2, \dots, p_n$ of length $n$. It is very disappointing, but he forgot this permutation. He only remembers the array $q_1, q_2, \dots, q_{n-1}$ of length $n-1$, where $q_i=p_{i+1}-p_i$. 24 25 Given $n$ and $q=q_1, q_2, \dots, q_{n-1}$, help Polycarp restore the invented permutation. 26 27 Input 28 29 The first line contains the integer $n$ ($2 \le n \le 2\cdot10^5$) — the length of the permutation to restore. The second line contains $n-1$ integers $q_1, q_2, \dots, q_{n-1}$ ($-n \lt q_i \lt n$). 30 31 Output 32 33 Print the integer -1 if there is no such permutation of length $n$ which corresponds to the given array $q$. Otherwise, if it exists, print $p_1, p_2, \dots, p_n$. Print any such permutation if there are many of them. 34 35 Examples 36 37 Input 38 39 ``` 40 3 41 -2 1 42 ``` 43 44 Output 45 46 ``` 47 3 1 2 48 ``` 49 50 Input 51 52 ``` 53 5 54 1 1 1 1 55 ``` 56 57 Output 58 59 ``` 60 1 2 3 4 5 61 ``` 62 63 Input 64 65 ``` 66 4 67 -1 2 2 68 ``` 69 70 Output 71 72 ``` 73 -1 74 ```