1857C.md (1950B)
1 Source: https://codeforces.com/problemset/problem/1857/C 2 3 C. Assembly via Minimums 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 Sasha has an array $a$ of $n$ integers. He got bored and for all $i$, $j$ ($i \lt j$), he wrote down the minimum value of $a_i$ and $a_j$. He obtained a new array $b$ of size $\frac{n\cdot (n-1)}{2}$. 22 23 For example, if $a=$ [$2,3,5,1$], he would write [$\min(2, 3), \min(2, 5), \min(2, 1), \min(3, 5), \min(3, 1), min(5, 1)$] $=$ [$2, 2, 1, 3, 1, 1$]. 24 25 Then, he randomly shuffled all the elements of the array $b$. 26 27 Unfortunately, he forgot the array $a$, and your task is to restore any possible array $a$ from which the array $b$ could have been obtained. 28 29 The elements of array $a$ should be in the range $[-10^9,10^9]$. 30 31 Input 32 33 The first line contains a single integer $t$ ($1\le t\le 200$) — the number of test cases. 34 35 The first line of each test case contains a single integer $n$ ($2\le n\le 10^3$) — the length of array $a$. 36 37 The second line of each test case contains $\frac{n\cdot (n-1)}{2}$ integers $b_1,b_2,\dots,b_{\frac{n\cdot (n-1)}{2}}$ ($−10^9\le b_i\le 10^9$) — the elements of array $b$. 38 39 It is guaranteed that the sum of $n$ over all tests does not exceed $10^3$ and for each array $b$ in the test, there exists an original array. 40 41 Output 42 43 For each test case, output any possible array $a$ of length $n$. 44 45 Example 46 47 Input 48 49 ``` 50 5 51 52 3 53 54 1 3 1 55 56 2 57 58 10 59 60 4 61 62 7 5 3 5 3 3 63 64 5 65 66 2 2 2 2 2 2 2 2 2 2 67 68 5 69 70 3 0 0 -2 0 -2 0 0 -2 -2 71 ``` 72 73 Output 74 75 ``` 76 1 3 3 77 10 10 78 7 5 3 12 79 2 2 2 2 2 80 0 -2 0 3 5 81 ``` 82 83 Note 84 85 In the first sample, Sasha chose the array $[1,3,3]$, then the array $b$ will look like $[\min(a_1,a_2)=1, \min(a_1,a_3)=1, \min(a_2,a_3)=3]$, after shuffling its elements, the array can look like $[1,3,1]$. 86 87 In the second sample, there is only one pair, so the array $[10,10]$ is suitable. Another suitable array could be $[15,10]$.