Codeforces Round 860 (Div. 2) |
---|
Finished |
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$$$.
You have to rearrange the elements of the array $$$a$$$ so that the following condition is satisfied:
$$$$$$\max\limits_{1 \le l \le r \le n} \lvert a_l + a_{l+1} + \ldots + a_r \rvert < \max(a_1, a_2, \ldots, a_n) - \min(a_1, a_2, \ldots, a_n),$$$$$$ where $$$|x|$$$ denotes the absolute value of $$$x$$$.
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.
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$$$.
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.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 300\,000$$$) — the length of the array $$$a$$$.
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$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$300\,000$$$.
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.
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}$$$).
If there are several possible answers, you can output any of them.
7 4 3 4 -2 -5 5 2 2 2 -3 -3 8 -3 -3 1 1 1 1 1 1 3 0 1 -1 7 -3 4 3 4 -4 -4 0 1 0 7 -18 13 -18 -17 12 15 13
Yes -5 -2 3 4 Yes -3 2 -3 2 2 Yes 1 1 1 -3 1 1 1 -3 Yes -1 0 1 Yes 4 -4 4 -4 0 3 -3 No Yes 13 12 -18 15 -18 13 -17
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$$$.
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$$$.
In the fourth test example, any rearrangement of the array $$$a$$$ will be suitable as an answer, including $$$[-1, 0, 1]$$$.
Name |
---|