codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```