1798D.md (2949B)
1 Source: https://codeforces.com/problemset/problem/1798/D 2 3 D. Shocking Arrangement 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 You are given an array $a_1, a_2, \ldots, a_n$ consisting of integers such that $a_1 + a_2 + \ldots + a_n = 0$. 22 23 You have to rearrange the elements of the array $a$ so that the following condition is satisfied: 24 25 $$\max\limits_{1 \le l \le r \le n} \lvert a_l + a_{l+1} + \ldots + a_r \rvert \lt \max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n),$$ where $|x|$ denotes the absolute value of $x$. 26 27 More formally, determine if there exists a permutation $p_1, p_2, \ldots, p_n$ that for the array $a_{p_1}, a_{p_2}, \ldots, a_{p_n}$, the condition above is satisfied, and find the corresponding array. 28 29 Recall that the array $p_1, p_2, \ldots, p_n$ is called a permutation if for each integer $x$ from $1$ to $n$ there is exactly one $i$ from $1$ to $n$ such that $p_i = x$. 30 31 Input 32 33 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 50\,000$). The description of the test cases follows. 34 35 The first line of each test case contains a single integer $n$ ($1 \le n \le 300\,000$) — the length of the array $a$. 36 37 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — elements of the array $a$. It is guaranteed that the sum of the array $a$ is zero, in other words: $a_1 + a_2 + \ldots + a_n = 0$. 38 39 It is guaranteed that the sum of $n$ over all test cases does not exceed $300\,000$. 40 41 Output 42 43 For each test case, if it is impossible to rearrange the elements of the array $a$ in the required way, print "No" in a single line. 44 45 If possible, print "Yes" in the first line, and then in a separate line $n$ numbers — elements $a_1, a_2, \ldots, a_n$ rearranged in a valid order ($a_{p_1}, a_{p_2}, \ldots, a_{p_n}$). 46 47 If there are several possible answers, you can output any of them. 48 49 Example 50 51 Input 52 53 ``` 54 7 55 4 56 3 4 -2 -5 57 5 58 2 2 2 -3 -3 59 8 60 -3 -3 1 1 1 1 1 1 61 3 62 0 1 -1 63 7 64 -3 4 3 4 -4 -4 0 65 1 66 0 67 7 68 -18 13 -18 -17 12 15 13 69 ``` 70 71 Output 72 73 ``` 74 Yes 75 -5 -2 3 4 76 Yes 77 -3 2 -3 2 2 78 Yes 79 1 1 1 -3 1 1 1 -3 80 Yes 81 -1 0 1 82 Yes 83 4 -4 4 -4 0 3 -3 84 No 85 Yes 86 13 12 -18 15 -18 13 -17 87 ``` 88 89 Note 90 91 In the first test case $\max(a_1, \ldots, a_n) - \min(a_1, \ldots, a_n) = 9$. Therefore, the elements can be rearranged as $[-5, -2, 3, 4]$. It is easy to see that for such an arrangement $\lvert a_l + \ldots + a_r \rvert$ is always not greater than $7$, and therefore less than $9$. 92 93 In the second test case you can rearrange the elements of the array as $[-3, 2, -3, 2, 2]$. Then the maximum modulus of the sum will be reached on the subarray $[-3, 2, -3]$, and will be equal to $\lvert -3 + 2 + -3 \rvert = \lvert -4 \rvert = 4$, which is less than $5$. 94 95 In the fourth test example, any rearrangement of the array $a$ will be suitable as an answer, including $[-1, 0, 1]$.