Even-Odd XOR (Codeforces 1722G)
Tags: Greedy, bitmasks

Given an integer $$$n$$$, find any array $$$a$$$ of $$$n$$$ distinct nonnegative integers less than $$$2^{31}$$$ such that the bitwise XOR of the elements on odd indices equals the bitwise XOR of the elements on even indices.

Input: The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 629$$$) — the number of test cases.Then $$$t$$$ lines follow, each containing a single integer $$$n$$$ $$$(3 \leq n \leq 2\cdot10^5)$$$ — the length of the array.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output: For each test case, output one line containing $$$n$$$ distinct integers that satisfy the conditions.If there are multiple answers, you can output any of them.

Note: In the first test case the XOR on odd indices is $$$4 \oplus 1 \oplus 0 \oplus 7 = 2$$$ and the XOR on even indices is $$$2 \oplus 5 \oplus 6 \oplus 3= 2$$$.

Sample Inputs:
7
8
3
4
5
6
7
9

Sample Outputs:
4 2 1 5 0 6 7 3
2 1 3
2 1 3 0
2 0 4 5 3
4 1 2 12 3 8
1 2 3 4 5 6 7
8 2 3 7 4 0 5 6 9

Solution (Python):
import collections
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 gcd(a, b):
    if b == 0:
        x = 1
        y = 0
        return (x, y, a)
    (x, y, g) = gcd(b, a % b)
    return (y, x - a // b * y, g)
mod = 1000000007

def solve():
    n = ii()
    als = [[], [0], [0, 5, 1, 8, 2, 10, 3, 13, 4, 14], [2, 1, 3], [2, 1, 3, 0], [2, 0, 4, 5, 3], [4, 1, 2, 12, 3, 8], [1, 2, 3, 4, 5, 6, 7]]
    x = n % 8 if n % 8 != 2 else 10
    return ' '.join(map(str, als[n % 8] + [16 + i for i in range(n - x)]))

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

Solution (Python):
import collections
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 gcd(a, b):
    if b == 0:
        x = 1
        y = 0
        return (x, y, a)
    (x, y, g) = gcd(b, a % b)
    return (y, x - a // b * y, g)
mod = 1000000007

def solve():
    n = ii()
    als = [[], [0], [0, 5, 1, 8, 2, 10, 3, 13, 4, 14], [2, 1, 3], [2, 1, 3, 0], [2, 0, 4, 5, 3], [4, 1, 2, 12, 3, 8], [1, 2, 3, 4, 5, 6, 7]]
    return ' '.join(map(str, als[n % 8] + [16 + i for i in range(n - (n % 8 + 8 * (n % 8 == 2)))]))

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

Solution (Python):
def f(n):
    if n == 3:
        return [1, 3, 2]
    if n // 2 % 2 == 1:
        return [1, 4, 2, 8, 3, 12] + f(n - 6)
    k = n // 2
    h1 = [x << 4 for x in range(1, k + 1)]
    h2 = [(x << 4) + 1 for x in range(1, k + 1)]
    res = []
    for i in range(k):
        res.append(h1[i])
        res.append(h2[i])
    if n % 2 == 1:
        res.append(0)
    return res
t = int(input())
for i in range(t):
    n = int(input())
    res = f(n)
    print(' '.join(map(str, res)))