Equal XOR (Codeforces 1944B)
Tags: Others, bitmasks

You are given an array $$$a$$$ of length $$$2n$$$, consisting of each integer from $$$1$$$ to $$$n$$$ exactly twice.You are also given an integer $$$k$$$ ($$$1 \leq k \leq \lfloor \frac{n}{2} \rfloor $$$).You need to find two arrays $$$l$$$ and $$$r$$$ each of length $$$\mathbf{2k}$$$ such that:   $$$l$$$ is a subset$$$^\dagger$$$ of $$$[a_1, a_2, \ldots a_n]$$$  $$$r$$$ is a subset of $$$[a_{n+1}, a_{n+2}, \ldots a_{2n}]$$$  bitwise 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}$$$ 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.$$$^\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]$$$.

Input: 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.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 $$$).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$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^4$$$.

Output: For each test case, output two lines. On the first line of output, output $$$2k$$$ integers $$$l_1, l_2, \ldots, l_{2k}$$$.On the second line of output, output $$$2k$$$ integers $$$r_1, r_2, \ldots r_{2k}$$$.If there are multiple solutions, you may output any one of them.

Note: 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$$$.In the second test case, $$$6 \oplus 4 = 1 \oplus 3 = 2$$$.

Sample Inputs:
4
2 1
1 2 2 1
6 1
6 4 2 1 2 3 1 6 3 5 5 4
4 1
1 2 3 4 1 2 3 4
6 2
5 1 3 3 5 1 2 6 4 6 4 2

Sample Outputs:
2 1
2 1
6 4
1 3
1 2
1 2
5 1 3 3
6 4 2 4

Solution (Python):
def xx(l):
    h = sorted(l)
    occ1 = []
    x = []
    t = False
    for i in range(len(h) - 1):
        if h[i] == h[i + 1]:
            occ1.append(h[i])
            occ1.append(h[i])
            t = True
        else:
            if not t:
                x.append(h[i])
            t = False
    if not t:
        x.append(h[-1])
    return (x, occ1)
for _ in range(int(input())):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    l = a[:n]
    (e, occ) = xx(l)
    l1 = a[n:2 * n]
    (e2, occ2) = xx(l1)
    if len(e) == 0:
        result = ' '.join(map(str, occ[:2 * k]))
        result2 = ' '.join(map(str, occ2[:2 * k]))
        print(result)
        print(result2)
    elif len(e) >= 2 * k:
        result = ' '.join(map(str, e[:2 * k]))
        print(result)
        print(result)
    else:
        if len(occ) >= 2 * k:
            result1 = ' '.join(map(str, occ[:2 * k]))
        else:
            result1 = ' '.join(map(str, occ[:] + e[:2 * k - len(occ)]))
        if len(occ2) >= 2 * k:
            result2 = ' '.join(map(str, occ2[:2 * k]))
        else:
            result2 = ' '.join(map(str, occ2[:] + e2[:2 * k - len(occ2)]))
        print(result1)
        print(result2)

Solution (Python):
def find_duplicates(arr):
    duplicates = []
    seen = set()
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

def commons(list1, list2):
    set1 = set(list1)
    common_elements = []
    for item in list2:
        if item in set1:
            common_elements.append(item)
    return common_elements

def convert_to_string_with_spaces(arr):
    try:
        return ' '.join(map(str, arr))
    except Exception as e:
        print('Error:', e)
        return None

def swapnil(n, k, a):
    l1 = a[:n]
    l2 = a[n:]
    x = find_duplicates(l1)
    y = find_duplicates(l2)
    lf = []
    rf = []
    g = min(len(x), k)
    for i in range(g):
        lf.append(x[i])
        lf.append(x[i])
        rf.append(y[i])
        rf.append(y[i])
    k = 2 * k - len(lf)
    q = commons(l1, l2)
    for i in range(k):
        lf.append(q[i])
        rf.append(q[i])
    print(convert_to_string_with_spaces(lf))
    print(convert_to_string_with_spaces(rf))
t = int(input())
for i in range(t):
    (n, k) = list(map(int, input().split()))
    a = list(map(int, input().split()))
    swapnil(n, k, a)

Solution (Python):
def get_subsets_with_same_xor(a_array, b_array, even_number):
    a_numbers = []
    b_numbers = []
    for i in a_array:
        if i not in b_array:
            a_numbers += [i, i]
    for i in b_array:
        if i not in a_array:
            b_numbers += [i, i]
    a_numbers += list(a_array & b_array)
    b_numbers += list(a_array & b_array)
    print(' '.join(list(map(str, a_numbers[:even_number]))))
    print(' '.join(list(map(str, b_numbers[:even_number]))))
tests = int(input())
for _ in range(tests):
    (n, k) = list(map(int, input().split()))
    a_array = list(map(int, input().split()))
    get_subsets_with_same_xor(set(a_array[:n]), set(a_array[n:]), 2 * k)