Korney Korneevich and XOR (easy version) (Codeforces 1582F1)
Tags: Greedy, bitmasks

This is an easier version of the problem with smaller constraints.Korney Korneevich dag up an array $$$a$$$ of length $$$n$$$. Korney Korneevich has recently read about the operation bitwise XOR, so he wished to experiment with it. For this purpose, he decided to find all integers $$$x \ge 0$$$ such that there exists an increasing subsequence of the array $$$a$$$, in which the bitwise XOR of numbers is equal to $$$x$$$.It didn't take a long time for Korney Korneevich to find all such $$$x$$$, and he wants to check his result. That's why he asked you to solve this problem!A sequence $$$s$$$ is a subsequence of a sequence $$$b$$$ if $$$s$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) elements.A sequence $$$s_1, s_2, \ldots , s_m$$$ is called increasing if $$$s_1 < s_2 < \ldots < s_m$$$.

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 500$$$) — the elements of the array $$$a$$$.

Output: In the first line print a single integer $$$k$$$ — the number of found $$$x$$$ values.In the second line print $$$k$$$ integers in increasing order $$$x_1, x_2, \ldots x_k$$$ ($$$0 \le x_1 < \ldots < x_k$$$) — found $$$x$$$ values.

Note: In the first test case:  To get value $$$x = 0$$$ it is possible to choose and empty subsequence  To get value $$$x = 2$$$ it is possible to choose a subsequence $$$[2]$$$  To get value $$$x = 4$$$ it is possible to choose a subsequence $$$[4]$$$  To get value $$$x = 6$$$ it is possible to choose a subsequence $$$[2, 4]$$$ 

Sample Inputs:
4
4 2 2 4

8
1 0 1 7 12 5 3 2

Sample Outputs:
4
0 2 4 6

12
0 1 2 3 4 5 6 7 10 11 12 13

Solution (Python):
def korney(a):
    inf = float('inf')
    xors_by_a = {0: [0]}
    a_by_xor = {0: 0}
    used_a = [0]
    recent = set()
    for ai in a:
        if len(a_by_xor.keys()) == 512:
            break
        if ai in recent:
            continue
        else:
            recent.add(ai)
        changed = False
        for aj in used_a:
            if aj >= ai:
                break
            for existing_xor in xors_by_a[aj]:
                new_xor = ai ^ existing_xor
                if a_by_xor.get(new_xor, inf) > ai:
                    a_by_xor[new_xor] = ai
                    changed = True
        if changed:
            xors_by_a = recreate_xors_by_a(a_by_xor)
            used_a = sorted(xors_by_a.keys())
            recent = set()
    print(len(a_by_xor.keys()))
    print(' '.join(map(str, sorted(a_by_xor.keys()))))

def recreate_xors_by_a(a_by_xor):
    xors_by_a = {}
    for (xor_value, a) in a_by_xor.items():
        if a in xors_by_a:
            xors_by_a[a] += [xor_value]
        else:
            xors_by_a[a] = [xor_value]
    return xors_by_a
n = int(input())
a = list(map(int, input().split(' ')))
korney(a)

Solution (Python):
def korney(a):
    inf = float('inf')
    xors_by_a = {0: [0]}
    a_by_xor = {0: 0}
    min_a = 0
    used_a = [0]
    recent = set()
    for ai in a:
        if len(a_by_xor.keys()) == 512:
            break
        if ai in recent:
            continue
        else:
            recent.add(ai)
        if ai < min_a:
            continue
        changed = False
        for aj in used_a:
            if aj >= ai:
                break
            for existing_xor in xors_by_a[aj]:
                new_xor = ai ^ existing_xor
                if a_by_xor.get(new_xor, inf) > ai:
                    a_by_xor[new_xor] = ai
                    changed = True
        if changed:
            (xors_by_a, min_a) = recreate_xors_by_a(a_by_xor)
            used_a = sorted(xors_by_a.keys())
            recent = set()
    print(len(a_by_xor.keys()))
    print(' '.join(map(str, sorted(a_by_xor.keys()))))

def recreate_xors_by_a(a_by_xor):
    xors_by_a = {}
    counts = [0 for i in range(10)]
    for (xor_value, a) in a_by_xor.items():
        if a in xors_by_a:
            xors_by_a[a] += [xor_value]
        else:
            xors_by_a[a] = [xor_value]
        for i in range(10):
            if xor_value <= 2 ** i:
                counts[i] += 1
            else:
                break
    min_a = 0
    for i in range(10):
        if counts[i] == 2 ** i:
            min_a = 2 ** i
        else:
            break
    return (xors_by_a, min_a)
n = int(input())
a = list(map(int, input().split(' ')))
korney(a)

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
pos = {0: 0}
to_skip = set()
for ai in a:
    if ai in to_skip:
        continue
    changed = False
    for (k, v) in list(pos.items()):
        if v < ai:
            nou = k ^ ai
            if nou not in pos or ai < pos[nou]:
                pos[nou] = ai
                changed = True
    if not changed:
        to_skip.add(ai)
    else:
        to_skip = set()
print(len(pos))
print(' '.join((str(v) for v in sorted(pos))))