The Harmonization of XOR (Codeforces 1787E)
Tags: Greedy, bitmasks

You are given an array of exactly $$$n$$$ numbers $$$[1,2,3,\ldots,n]$$$ along with integers $$$k$$$ and $$$x$$$.Partition the array in exactly $$$k$$$ non-empty disjoint subsequences such that the bitwise XOR of all numbers in each subsequence is $$$x$$$, and each number is in exactly one subsequence. Notice that there are no constraints on the length of each subsequence.A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) elements.For example, for $$$n = 15$$$, $$$k = 6$$$, $$$x = 7$$$, the following scheme is valid:   $$$[6,10,11]$$$, $$$6 \oplus 10 \oplus 11 = 7$$$,  $$$[5,12,14]$$$, $$$5 \oplus 12 \oplus 14 = 7$$$,  $$$[3,9,13]$$$, $$$3 \oplus 9 \oplus 13 = 7$$$,  $$$[1,2,4]$$$, $$$1 \oplus 2 \oplus 4 = 7$$$,  $$$[8,15]$$$, $$$8 \oplus 15 = 7$$$,  $$$[7]$$$, $$$7 = 7$$$,  where $$$\oplus$$$ represents the bitwise XOR operation.The following scheme is invalid, since $$$8$$$, $$$15$$$ do not appear:   $$$[6,10,11]$$$, $$$6 \oplus 10 \oplus 11 = 7$$$,  $$$[5,12,14]$$$, $$$5 \oplus 12 \oplus 14 = 7$$$,  $$$[3,9,13]$$$, $$$3 \oplus 9 \oplus 13 = 7$$$,  $$$[1,2,4]$$$, $$$1 \oplus 2 \oplus 4 = 7$$$,  $$$[7]$$$, $$$7 = 7$$$. The following scheme is invalid, since $$$3$$$ appears twice, and $$$1$$$, $$$2$$$ do not appear:   $$$[6,10,11]$$$, $$$6 \oplus 10 \oplus 11 = 7$$$,  $$$[5,12,14]$$$, $$$5 \oplus 12 \oplus 14 = 7$$$,  $$$[3,9,13]$$$, $$$3 \oplus 9 \oplus 13 = 7$$$,  $$$[3,4]$$$, $$$3 \oplus 4 = 7$$$,  $$$[8,15]$$$, $$$8 \oplus 15 = 7$$$,  $$$[7]$$$, $$$7 = 7$$$. 

Input: Each test contains multiple test cases. The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The first and the only line of each test case contains three integers $$$n$$$, $$$k$$$, $$$x$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$; $$$1\le x \le 10^9$$$) — the length of the array, the number of subsequences and the required XOR.It's guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, if it is possible to partition the sequence, print "YES" in the first line. In the $$$i$$$-th of the following $$$k$$$ lines first print the length $$$s_i$$$ of the $$$i$$$-th subsequence, then print $$$s_i$$$ integers, representing the elements in the $$$i$$$-th subsequence. If there are multiple answers, print any. Note that you can print a subsequence in any order.If it is not possible to partition the sequence, print "NO".

Note: In the first test case, we construct the following $$$6$$$ subsequences:   $$$[6,10,11]$$$, $$$6 \oplus 10 \oplus 11 = 7$$$,  $$$[5,12,14]$$$, $$$5 \oplus 12 \oplus 14 = 7$$$,  $$$[3,9,13]$$$, $$$3 \oplus 9 \oplus 13 = 7$$$,  $$$[1,2,4]$$$, $$$1 \oplus 2 \oplus 4 = 7$$$,  $$$[8,15]$$$, $$$8 \oplus 15 = 7$$$,  $$$[7]$$$, $$$7 = 7$$$. In the second test case, we construct the following $$$4$$$ subsequences:   $$$[1,4]$$$, $$$1 \oplus 4 = 5$$$,  $$$[2,7]$$$, $$$2 \oplus 7 = 5$$$,  $$$[3,6]$$$, $$$3 \oplus 6 = 5$$$,  $$$[5,8,9,10,11]$$$, $$$5 \oplus 8 \oplus 9 \oplus 10 \oplus 11 = 5$$$. The following solution is considered correct in this test case as well:   $$$[1,4]$$$, $$$1 \oplus 4 = 5$$$,  $$$[2,7]$$$, $$$2 \oplus 7 = 5$$$,  $$$[5]$$$, $$$5 = 5$$$,  $$$[3,6,8,9,10,11]$$$, $$$3 \oplus 6 \oplus 8 \oplus 9 \oplus 10 \oplus 11 = 5$$$. 

Sample Inputs:
7
15 6 7
11 4 5
5 3 2
4 1 4
6 1 7
11 5 5
11 6 5

Sample Outputs:
YES
3 6 10 11
3 5 12 14
3 3 9 13
3 1 2 4
2 8 15
1 7
YES
2 1 4
2 2 7
2 3 6
5 5 8 9 10 11
NO
YES
4 1 2 3 4
YES
6 1 2 3 4 5 6
NO
NO

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, k, x) = readInts()
    used = [0] * (n + 1)
    t = x if k % 2 else 0
    curr = 0
    for i in range(n):
        curr ^= i + 1
    if curr != t:
        print('NO')
        return
    cnt = j = 0
    ans = []
    for i in range(1, n + 1):
        if used[i]:
            continue
        t = i ^ x
        if t > n:
            pass
        elif used[t]:
            pass
        else:
            used[t] = used[i] = 1
            ans.append([i, t]) if t else ans.append([i])
            cnt += 1
        if cnt == k:
            for j in range(1, n + 1):
                if not used[j]:
                    ans[-1].append(j)
            print('YES')
            for each in ans:
                print(*[len(each)] + each)
            return
    print('NO')
    return
for _ in range(int(input())):
    solve()

Solution (Python):
import itertools
import math
import sys
import functools
import operator
In = lambda : map(int, input().split())
bi = lambda a, b: range(a, b + 1)
ck = functools.cmp_to_key
ac = itertools.accumulate
rep = itertools.repeat

def lxor(l):
    return list(ac(l, operator.xor, initial=0))[-1]

def ok(l, x):
    return lxor(l) == x

def solve():
    (n, k, x) = In()
    if lxor(rep(x, k)) != lxor(bi(1, n)):
        print('NO')
        return
    s = set(bi(1, n))
    (ke, bk) = ([], [])
    while len(s):
        a = s.pop()
        b = a ^ x
        if b == 0 or b not in s:
            if b == 0:
                ke.append([a])
            else:
                bk.append(a)
        else:
            s.remove(b)
            ke.append([a, b])
    if len(ke) < k:
        print('NO')
        return
    while len(ke) >= k:
        for i in ke[-1]:
            bk.append(i)
        del ke[-1]
    print('YES')
    for i in ke:
        print(len(i), *i)
    if len(bk):
        print(len(bk), *bk)

def main():
    if len(sys.argv) >= 2 and sys.argv[1] == 'LOCAL':
        sys.stdin = open('in', 'r')
    (tt,) = In()
    while tt:
        solve()
        tt -= 1
main()

Solution (Python):
import itertools
import math
import sys
import functools
import operator
In = lambda : map(int, sys.stdin.readline().split())
bi = lambda a, b: range(a, b + 1)
ck = functools.cmp_to_key
ac = itertools.accumulate
rep = itertools.repeat

def lxor(l):
    return list(ac(l, operator.xor, initial=0))[-1]

def ok(l, x):
    return lxor(l) == x

def solve():
    (n, k, x) = In()
    if lxor(rep(x, k)) != lxor(bi(1, n)):
        print('NO')
        return
    s = set(bi(1, n))
    (ke, bk) = ([], [])
    while len(s):
        a = s.pop()
        b = a ^ x
        if b == 0 or b not in s:
            if b == 0:
                ke.append([a])
            else:
                bk.append(a)
        else:
            s.remove(b)
            ke.append([a, b])
    if len(ke) < k:
        print('NO')
        return
    while len(ke) >= k:
        for i in ke[-1]:
            bk.append(i)
        del ke[-1]
    print('YES')
    for i in ke:
        print(len(i), *i)
    if len(bk):
        print(len(bk), *bk)

def main():
    if len(sys.argv) >= 2 and sys.argv[1] == 'LOCAL':
        sys.stdin = open('in', 'r')
    (tt,) = In()
    while tt:
        solve()
        tt -= 1
main()