1512D.md (1669B)
1 Source: https://codeforces.com/problemset/problem/1512/D 2 3 D. Corrupted Array 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 a number $n$ and an array $b_1, b_2, \ldots, b_{n+2}$, obtained according to the following algorithm: 22 23 * some array $a_1, a_2, \ldots, a_n$ was guessed; 24 * array $a$ was written to array $b$, i.e. $b_i = a_i$ ($1 \le i \le n$); 25 * The $(n+1)$-th element of the array $b$ is the sum of the numbers in the array $a$, i.e. $b_{n+1} = a_1+a_2+\ldots+a_n$; 26 * The $(n+2)$-th element of the array $b$ was written some number $x$ ($1 \le x \le 10^9$), i.e. $b_{n+2} = x$; The 27 * array $b$ was shuffled. 28 29 For example, the array $b=[2, 3, 7, 12 ,2]$ it could be obtained in the following ways: 30 31 * $a=[2, 2, 3]$ and $x=12$; 32 * $a=[3, 2, 7]$ and $x=2$. 33 34 For the given array $b$, find any array $a$ that could have been guessed initially. 35 36 Input 37 38 The first line contains a single integer $t$ ($1 \le t \le 10^4$). Then $t$ test cases follow. 39 40 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$). 41 42 The second row of each test case contains $n+2$ integers $b_1, b_2, \ldots, b_{n+2}$ ($1 \le b_i \le 10^9$). 43 44 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 45 46 Output 47 48 For each test case, output: 49 50 * "-1", if the array $b$ could not be obtained from any array $a$; 51 * $n$ integers $a_1, a_2, \ldots, a_n$, otherwise. 52 53 If there are several arrays of $a$, you can output any. 54 55 Example 56 57 Input 58 59 ``` 60 4 61 3 62 2 3 7 12 2 63 4 64 9 1 7 1 6 5 65 5 66 18 2 2 3 2 9 2 67 3 68 2 6 9 2 1 69 ``` 70 71 Output 72 73 ``` 74 2 3 7 75 -1 76 2 2 2 3 9 77 1 2 6 78 ```