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.