2023A.md (2922B)
1 Source: https://codeforces.com/problemset/problem/2023/A 2 3 A. Concatenation of Arrays 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 $n$ arrays $a_1$, $\ldots$, $a_n$. The length of each array is two. Thus, $a_i = [a_{i, 1}, a_{i, 2}]$. You need to concatenate the arrays into a single array of length $2n$ such that the number of inversions$^{\dagger}$ in the resulting array is minimized. Note that you do not need to count the actual number of inversions. 22 23 More formally, you need to choose a permutation$^{\ddagger}$ $p$ of length $n$, so that the array $b = [a_{p_1,1}, a_{p_1,2}, a_{p_2, 1}, a_{p_2, 2}, \ldots, a_{p_n,1}, a_{p_n,2}]$ contains as few inversions as possible. 24 25 $^{\dagger}$The number of inversions in an array $c$ is the number of pairs of indices $i$ and $j$ such that $i \lt j$ and $c_i \gt c_j$. 26 27 $^{\ddagger}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array). 28 29 Input 30 31 Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows. 32 33 The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of arrays. 34 35 Each of the following $n$ lines contains two integers $a_{i,1}$ and $a_{i,2}$ ($1 \le a_{i,j} \le 10^9$) — the elements of the $i$-th array. 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 38 39 Output 40 41 For each test case, output $2n$ integers — the elements of the array you obtained. If there are multiple solutions, output any of them. 42 43 Example 44 45 Input 46 47 ``` 48 4 49 50 2 51 52 1 4 53 54 2 3 55 56 3 57 58 3 2 59 60 4 3 61 62 2 1 63 64 5 65 66 5 10 67 68 2 3 69 70 9 6 71 72 4 1 73 74 8 7 75 76 1 77 78 10 20 79 ``` 80 81 Output 82 83 ``` 84 2 3 1 4 85 2 1 3 2 4 3 86 4 1 2 3 5 10 8 7 9 6 87 10 20 88 ``` 89 90 Note 91 92 In the first test case, we concatenated the arrays in the order $2, 1$. Let's consider the inversions in the resulting array $b = [2, 3, 1, 4]$: 93 94 * $i = 1$, $j = 3$, since $b_1 = 2 \gt 1 = b_3$; 95 * $i = 2$, $j = 3$, since $b_2 = 3 \gt 1 = b_3$. 96 97 Thus, the number of inversions is $2$. It can be proven that this is the minimum possible number of inversions. 98 99 In the second test case, we concatenated the arrays in the order $3, 1, 2$. Let's consider the inversions in the resulting array $b = [2, 1, 3, 2, 4, 3]$: 100 101 * $i = 1$, $j = 2$, since $b_1 = 2 \gt 1 = b_2$; 102 * $i = 3$, $j = 4$, since $b_3 = 3 \gt 2 = b_4$; 103 * $i = 5$, $j = 6$, since $b_5 = 4 \gt 3 = b_6$. 104 105 Thus, the number of inversions is $3$. It can be proven that this is the minimum possible number of inversions. 106 107 In the third test case, we concatenated the arrays in the order $4, 2, 1, 5, 3$.