codeforces-scrape

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

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$.