1630A.md (1889B)
1 Source: https://codeforces.com/problemset/problem/1630/A 2 3 A. And Matching 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 a set of $n$ ($n$ is always a power of $2$) elements containing all integers $0, 1, 2, \ldots, n-1$ exactly once. 22 23 Find $\frac{n}{2}$ pairs of elements such that: 24 25 * Each element in the set is in exactly one pair. 26 * The sum over all pairs of the [bitwise AND](https://en.wikipedia.org/wiki/Bitwise_operation#AND) of its elements must be exactly equal to $k$. Formally, if $a_i$ and $b_i$ are the elements of the $i$-th pair, then the following must hold: $$\sum_{i=1}^{n/2}{a_i \& b_i} = k,$$ where $\&$ denotes the bitwise AND operation. 27 28 If there are many solutions, print any of them, if there is no solution, print $-1$ instead. 29 30 Input 31 32 The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 400$) — the number of test cases. Description of the test cases follows. 33 34 Each test case consists of a single line with two integers $n$ and $k$ ($4 \leq n \leq 2^{16}$, $n$ is a power of $2$, $0 \leq k \leq n-1$). 35 36 The sum of $n$ over all test cases does not exceed $2^{16}$. All test cases in each individual input will be pairwise different. 37 38 Output 39 40 For each test case, if there is no solution, print a single line with the integer $-1$. 41 42 Otherwise, print $\frac{n}{2}$ lines, the $i$-th of them must contain $a_i$ and $b_i$, the elements in the $i$-th pair. 43 44 If there are many solutions, print any of them. Print the pairs and the elements in the pairs in any order. 45 46 Example 47 48 Input 49 50 ``` 51 4 52 53 4 0 54 55 4 1 56 57 4 2 58 59 4 3 60 ``` 61 62 Output 63 64 ``` 65 0 3 66 1 2 67 0 2 68 1 3 69 0 1 70 2 3 71 -1 72 ``` 73 74 Note 75 76 In the first test, $(0\&3)+(1\&2) = 0$. 77 78 In the second test, $(0\&2)+(1\&3) = 1$. 79 80 In the third test, $(0\&1)+(2\&3) = 2$. 81 82 In the fourth test, there is no solution.