codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```