Submission #1214493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214493		Ahmed_Solyman	XOR Sum (info1cup17_xorsum)	Pypy 3	0 / 100	139 ms	48808 KiB

xorsum

def compute_pairwise_sum_xor(V):
    from collections import Counter

    res = 0
    for x in V:
        res ^= (2 * x)  # XOR of V[i] + V[i]

    # Now compute XOR of all V[i] + V[j] for i < j
    MAX_BIT = 25  # 2^21 > 2e6, but extra bits for safety

    for bit in range(MAX_BIT):
        mask = (1 << (bit + 1)) - 1
        cnt = [0] * (1 << (bit + 1))
        for x in V:
            cnt[x & mask] += 1

        total = 0
        for x in V:
            x_mod = x & mask
            for y_mod in range(len(cnt)):
                if (x_mod + y_mod) >> bit & 1:
                    total += cnt[y_mod]

        # Remove pairs where i == j and double count
        for x in V:
            if ((x + x) >> bit) & 1:
                total -= 1

        total //= 2
        if total % 2 == 1:
            res ^= (1 << bit)

    return res

Compilation message (stdout)

Compiling 'xorsum.py'...

=======
  adding: __main__.pyc (deflated 30%)

=======

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 38
• Subtask 5: 0 / 23