1944B.md (2558B)
1 Source: https://codeforces.com/problemset/problem/1944/B 2 3 B. Equal XOR 4 5 time limit per test 6 7 1 second 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 an array $a$ of length $2n$, consisting of each integer from $1$ to $n$ exactly twice. 22 23 You are also given an integer $k$ ($1 \leq k \leq \lfloor \frac{n}{2} \rfloor $). 24 25 You need to find two arrays $l$ and $r$ each of length $\mathbf{2k}$ such that: 26 27 * $l$ is a subset$^\dagger$ of $[a_1, a_2, \ldots a_n]$ 28 * $r$ is a subset of $[a_{n+1}, a_{n+2}, \ldots a_{2n}]$ 29 * [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of elements of $l$ is equal to the bitwise XOR of elements of $r$; in other words, $l_1 \oplus l_2 \oplus \ldots \oplus l_{2k} = r_1 \oplus r_2 \oplus \ldots \oplus r_{2k}$ 30 31 It can be proved that at least one pair of $l$ and $r$ always exists. If there are multiple solutions, you may output any one of them. 32 33 $^\dagger$ A sequence $x$ is a subset of a sequence $y$ if $x$ can be obtained by deleting several (possibly none or all) elements of $y$ and rearranging the elements in any order. For example, $[3,1,2,1]$, $[1, 2, 3]$, $[1, 1]$ and $[3, 2]$ are subsets of $[1, 1, 2, 3]$ but $[4]$ and $[2, 2]$ are not subsets of $[1, 1, 2, 3]$. 34 35 Input 36 37 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 5000$) — the number of test cases. The description of the test cases follows. 38 39 The first line of each test case contains $2$ integers $n$ and $k$ ($2 \le n \le 5 \cdot 10^4$, $1 \leq k \leq \lfloor \frac{n}{2} \rfloor $). 40 41 The second line contains $2n$ integers $a_1, a_2, \ldots, a_{2n}$ ($1 \le a_i \le n$). It is guaranteed that every integer from $1$ to $n$ occurs exactly twice in $a$. 42 43 It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^4$. 44 45 Output 46 47 For each test case, output two lines. 48 49 On the first line of output, output $2k$ integers $l_1, l_2, \ldots, l_{2k}$. 50 51 On the second line of output, output $2k$ integers $r_1, r_2, \ldots r_{2k}$. 52 53 If there are multiple solutions, you may output any one of them. 54 55 Example 56 57 Input 58 59 ``` 60 4 61 62 2 1 63 64 1 2 2 1 65 66 6 1 67 68 6 4 2 1 2 3 1 6 3 5 5 4 69 70 4 1 71 72 1 2 3 4 1 2 3 4 73 74 6 2 75 76 5 1 3 3 5 1 2 6 4 6 4 2 77 ``` 78 79 Output 80 81 ``` 82 2 1 83 2 1 84 6 4 85 1 3 86 1 2 87 1 2 88 5 1 3 3 89 6 4 2 4 90 ``` 91 92 Note 93 94 In the first test case, we choose $l=[2,1]$ and $r=[2,1]$. $[2, 1]$ is a subset of $[a_1, a_2]$ and $[2, 1]$ is a subset of $[a_3, a_4]$, and $2 \oplus 1 = 2 \oplus 1 = 3$. 95 96 In the second test case, $6 \oplus 4 = 1 \oplus 3 = 2$.