Submission #1214493

#TimeUsernameProblemLanguageResultExecution timeMemory
1214493Ahmed_SolymanXOR Sum (info1cup17_xorsum)Pypy 3
0 / 100
139 ms48808 KiB
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%)

=======
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...