2254D.md (2670B)
1 Source: https://codeforces.com/problemset/problem/2254/D 2 3 D. Silhouette 4 5 time limit per test 6 7 2.5 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 secret array $a$ of $n$ strictly positive integers. 22 23 For each element $a_i$, its shadow $b_i$ is the sum of all elements in $a$ that are strictly smaller than $a_i$. Formally: 24 25 $$b_i = \sum_{\substack{1 \le j \le n\\ a_j \lt a_i}} a_j$$ 26 27 You are given the shadow array $b$. Your task is to reconstruct the lexicographically smallest valid array $a$ consisting of strictly positive integers that satisfies the above condition. If no such array exists, output $-1$. 28 29 Input 30 31 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 32 33 The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the array. 34 35 The second line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i \le 2 \cdot 10^{14}$) — the shadow array. 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each test case, output $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{18}$) — the lexicographically smallest valid array $a$ that satisfies the condition. If no valid array exists, output $-1$ instead. 42 43 Example 44 45 Input 46 47 ``` 48 8 49 50 1 51 52 0 53 54 5 55 56 0 4 0 4 14 57 58 3 59 60 4 0 0 61 62 3 63 64 0 0 0 65 66 3 67 68 0 1 1 69 70 4 71 72 1 1 1 1 73 74 7 75 76 0 4 4 4 4 4 9 77 78 5 79 80 0 0 0 3 3 81 ``` 82 83 Output 84 85 ``` 86 1 87 88 2 5 2 5 6 89 90 3 2 2 91 92 1 1 1 93 94 1 2 2 95 96 -1 97 98 -1 99 100 1 1 1 2 2 101 ``` 102 103 Note 104 105 In the first test case, the answer is $a = [1]$. Since there is only one element, there are no strictly smaller elements, so its shadow is $0$. Thus $a=[1]$ is valid. It is also lexicographically smallest, because the only allowed values are positive integers, and $1$ is the smallest possible. 106 107 In the second test case, the answer is $a = [2,5,2,5,6]$: 108 109 * For each $2$, there is no smaller element in the array, so the shadow is $0$. 110 * For each $5$, the strictly smaller elements are the two $2$'s, so the shadow is $2+2=4$. 111 * For $6$, the strictly smaller elements are two $2$'s and two $5$'s, so the shadow is $2+2+5+5=14$. 112 113 Therefore the shadow array is exactly $b = [0,4,0,4,14]$. 114 115 In the third test case, the shadow array for $a = [3, 2, 2]$ is calculated as follows: 116 117 * For $a_1 = 3$, the strictly smaller elements in the array are the two $2$s. Their sum is $2 + 2 = 4$. So, $b_1 = 4$. 118 * For $a_2 = 2$, there are no strictly smaller elements in the array. So, $b_2 = 0$. 119 * For $a_3 = 2$, there are no strictly smaller elements in the array. So, $b_3 = 0$. 120 121 The resulting shadow array is $b = [4, 0, 0]$, which matches the input.