XMAX is a pretty straight forward problem and I am sure my algorithm is right. But I am getting a NZEC which I am not able to reproduce on my machine. Can any one throw some light ?
Is it because my I/O is slow or my algo is slow. I noticed that there are no successful submissions in Python, but wanted to give it a try.
def main():
n = int(input())
a = [0]*n
for i in range(n):
a[i] = int(input())
a = sorted(a, reverse=True)
print_array(a, 'After sorted')
b = 63 # 2**63 > 10**18
while 2**b & a[0] == 0:
b -= 1
# print(b)
# gauss jordan elimination
i = 0 # row
while b >= 0 and i < n:
# go row by row
if 2**b & a[i] != 0:
# eliminate this bit from all numbers below and above
for j in range(n):
if j != i and a[j] & 2**b != 0:
a[j] = a[j] ^ a[i]
print_array(a, 'after b={}, i={}'.format(b, i))
b -= 1 # move on to next bit
i += 1 # move on to next row
# see if you can pivot
else:
for j in range(i+1, n):
if 2**b & a[j] != 0:
# swap these two
a[i], a[j] = a[j], a[i]
break
else: # no such number with 1 at this bit
# move on to next bit on the same row
b -= 1
# print numbers
print_array(a, 'After Gauss')
ans = 0
for j in range(n):
ans = ans ^ a[j]
# print('Ans: {}'.format(ans))
print(ans)
def print_array(a, s):
# print(s)
# for i, n in enumerate(a):
# print('{}: {:08b}'.format(i, n, n))
pass
if __name__ == '__main__':
main()
