codeforces-scrape

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

2254E.md (2311B)


      1 Source: https://codeforces.com/problemset/problem/2254/E
      2 
      3 E. Chronostasis
      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 Yousef has a hidden array $a$ of length $n$ consisting entirely of strictly positive integers.
     22 
     23 An operation was performed exactly once to create an array $b$:
     24 
     25 * Set $b_1 = a_1$.
     26 * For every $i$ from $2$ to $n$, set $b_i = a_i - a_{i-1}$.
     27 * After this, the elements of $b$ were completely shuffled.
     28 
     29 You are given the shuffled array $b$. Reconstruct the lexicographically smallest original array $a$. If it's impossible for any arrangement of $b$ to produce an array $a$ of strictly positive integers, output $-1$.
     30 
     31 Input
     32 
     33 The first line of input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     34 
     35 The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the array.
     36 
     37 The second line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ ($-10^9 \le b_i \le 10^9$) — the elements of the shuffled array $b$.
     38 
     39 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, output $n$ strictly positive integers $a_1, a_2, \dots, a_n$ ($a_i \ge 1$) — the lexicographically smallest original array $a$. If it's impossible to create a valid array $a$, output $-1$ instead.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 8
     51 
     52 1
     53 
     54 5
     55 
     56 4
     57 
     58 -5 2 1 1
     59 
     60 6
     61 
     62 -3 4 2 -1 1 0
     63 
     64 6
     65 
     66 -2 -2 4 1 0 1
     67 
     68 7
     69 
     70 0 0 -2 3 0 -1 2
     71 
     72 8
     73 
     74 -1 -1 -1 -1 5 0 0 1
     75 
     76 5
     77 
     78 1000000000 500000000 750000000 100000000 900000000
     79 
     80 10
     81 
     82 1000000000 -1000000000 500000000 -500000000 1 1 -1 -1 2 -2
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 5
     89 
     90 -1
     91 
     92 1 1 3 2 6 3
     93 
     94 1 1 2 6 4 2
     95 
     96 2 1 1 1 1 4 2
     97 
     98 1 1 1 6 5 4 3 2
     99 
    100 100000000 600000000 1350000000 2250000000 3250000000
    101 
    102 -1
    103 ```
    104 
    105 Note
    106 
    107 In the first test case, the only valid array is $a = [5]$.
    108 
    109 In the second test case, there is no valid arrangement of the elements of $b$ that reconstructs an array $a$ consisting entirely of strictly positive integers. Therefore, the answer is $-1$.
    110 
    111 In the third test case, one valid arrangement reconstructs the array $a=[1,1,3,2,6,3]$. The resulting sequence of differences $[1, 0, 2, -1, 4, -3]$ is a permutation of the given array $b$, and among all valid reconstructions, this array is lexicographically smallest.