And Matching (Codeforces 1631C)
Tags: Others, bitmasks

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.Find $$$\frac{n}{2}$$$ pairs of elements such that:  Each element in the set is in exactly one pair.  The sum over all pairs of the bitwise 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. If there are many solutions, print any of them, if there is no solution, print $$$-1$$$ instead.

Input: 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.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$$$).The sum of $$$n$$$ over all test cases does not exceed $$$2^{16}$$$. All test cases in each individual input will be pairwise different.

Output: For each test case, if there is no solution, print a single line with the integer $$$-1$$$.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. If there are many solutions, print any of them. Print the pairs and the elements in the pairs in any order.

Note: In the first test, $$$(0\&3)+(1\&2) = 0$$$.In the second test, $$$(0\&2)+(1\&3) = 1$$$.In the third test, $$$(0\&1)+(2\&3) = 2$$$.In the fourth test, there is no solution.

Sample Inputs:
4
4 0
4 1
4 2
4 3

Sample Outputs:
0 3
1 2
0 2
1 3
0 1
2 3
-1

Solution (Python):
import bisect
import collections
import math
import random
import sys
p2D = lambda x: print(*x, sep='\n')

def II():
    return int(sys.stdin.buffer.readline())

def MI():
    return map(int, sys.stdin.buffer.readline().split())

def LI():
    return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
    return [LI() for _ in range(rows_number)]

def BI():
    return sys.stdin.buffer.readline().rstrip()

def SI():
    return sys.stdin.buffer.readline().rstrip().decode()

def li():
    return [int(i) for i in input().split()]

def lli(rows):
    return [li() for _ in range(rows)]

def si():
    return input()

def ii():
    return int(input())

def ins():
    return input().split()

def drank(d, processing, da, rank):
    tmp = 10 ** 9
    if len(d[da]) == 1:
        return 1
    for di in d[da]:
        if processing[di - 1] == 0:
            processing[di - 1] = 1
            tmp = min(tmp, drank(d, processing, di, rank))
            processing[di - 1] = 0
    rank[da - 1] = tmp + 1
    return tmp + 1

def binary_search(n, a):
    l = len(a)
    low = 0
    high = l - 1
    while high >= low:
        mid = (high + low) // 2
        if a[mid] == n:
            return mid
        elif a[mid] > n:
            high = mid - 1
        else:
            low = mid + 1
    return -1

def solve():
    (n, k) = li()
    if (n, k) == (4, 3):
        return -1
    if k == n - 1:
        pairs = [str(n - 1) + ' ' + str(n - 2), '1 3', '0 ' + str(n - 4)]
        taken = [1, 3]
    else:
        pairs = [str(n - 1) + ' ' + str(k)]
        taken = [k, n - 1 - k]
        if k != 0:
            pairs.append('0 ' + str(n - 1 - k))
    for i in range(1, n // 2):
        if i not in taken:
            pairs.append(str(i) + ' ' + str(n - 1 - i))
    return '\n'.join(pairs)

def main():
    for _ in range(ii()):
        sys.stdout.write(str(solve()) + '\n')
if __name__ == '__main__':
    main()

Solution (Python):
def solve(n, k):
    n = n - 1
    pairs = [(i, n - i) for i in range(n // 2 + 1)]
    if k == 0:
        pass
    elif k == n:
        if n == 3:
            return '-1'
        pairs[0] = (n - 1, n)
        pairs[1] = (1, 3)
        pairs[3] = (n - 3, 0)
    elif k <= n // 2:
        pairs[k] = (k, n)
        pairs[0] = (n - k, 0)
    else:
        pairs[n - k] = (k, n)
        pairs[0] = (n - k, 0)
    return '\n'.join([' '.join([str(k) for k in pair]) for pair in pairs])
T = int(input())
for _ in range(T):
    (n, k) = [int(x) for x in input().split()]
    print(solve(n, k))

Solution (Python):
test_cases = int(input())
for _ in range(test_cases):
    a = list(map(int, input().split()))
    n = a[0]
    k = a[1]
    if n == 4 and k == 3:
        print(-1)
    elif k == 0:
        for i in range(0, n // 2):
            print(f'{i} {n - i - 1}')
    elif k < n - 1:
        print(f'{n - 1} {k}')
        print(f'{n - k - 1} 0')
        for i in range(1, n // 2):
            if i != k and i != n - k - 1:
                print(f'{i} {n - i - 1}')
    elif k == n - 1:
        print(f'{n - 1} {n - 2}')
        print(f'0 2')
        print(f'1 {n - 3}')
        for i in range(3, n // 2):
            print(f'{i} {n - i - 1}')