Problem:


Score: 600 points

Problem Statement

We have N non-negative integers: A_1, A_2, ..., A_N.

Consider painting at least one and at most N-1 integers among them in red, and painting the rest in blue.

Let the beauty of the painting be the \mbox{XOR} of the integers painted in red, plus the \mbox{XOR} of the integers painted in blue.

Find the maximum possible beauty of the painting.

What is \mbox{XOR}?

The bitwise \mbox{XOR} x_1 \oplus x_2 \oplus \ldots \oplus x_n of n non-negative integers x_1, x_2, \ldots, x_n is defined as follows:

 When x_1 \oplus x_2 \oplus \ldots \oplus x_n is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if the number of integers among x_1, x_2, \ldots, x_n whose binary representations have 1 in the 2^k's place is odd, and 0 if that count is even. 

For example, 3 \oplus 5 = 6.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

0 \leq A_i < 2^{60}\ (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible beauty of the painting.

Sample Input 1

3
3 6 5

Sample Output 1

12

If we paint 3, 6, 5 in blue, red, blue, respectively, the beauty will be (6) + (3 \oplus 5) = 12.

There is no way to paint the integers resulting in greater beauty than 12, so the answer is 12.

Sample Input 2

4
23 36 66 65

Sample Output 2

188

Sample Input 3

20
1008288677408720767 539403903321871999 1044301017184589821 215886900497862655 504277496111605629 972104334925272829 792625803473366909 972333547668684797 467386965442856573 755861732751878143 1151846447448561405 467257771752201853 683930041385277311 432010719984459389 319104378117934975 611451291444233983 647509226592964607 251832107792119421 827811265410084479 864032478037725181

Sample Output 3

2012721721873704572

A_i and the answer may not fit into a 32-bit integer type.



Sample input:
3
3 6 5


Sample output:
12

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
alist=list(map(int,input().split()))

max_digit=60
mat=[]
sum_digit=[0]*max_digit
for a in alist:
  array=[]
  for j in range(max_digit):    
    m=a&1
    array.append(m)
    sum_digit[max_digit-1-j]+=m
    a>>=1
    
  array.reverse()
  mat.append(array)
#print(mat)
#print(sum_digit)

mat_red=[[mat[i][j] for j in range(max_digit) if sum_digit[j]%2==0 and sum_digit[j]!=0] for i in range(N)]
#print(mat_red)

pivot_set=set()
for j in range(len(mat_red[0])):
  pivot_row=-1
  for i in range(N):
    if mat_red[i][j]==1:
      if not i in pivot_set:
        pivot_row=i
        break    
  
  if pivot_row!=-1:
    for i in range(N):
      if i==pivot_row:
        continue
      if mat_red[i][j]==0:
        continue      
      for k in range(j,len(mat_red[0])):
        mat_red[i][k]^=mat_red[pivot_row][k]
        
    pivot_set.add(pivot_row)
  #print(j,pivot_row)
  #print(mat_red)
#print(mat_red)  

sum_digit_red=[0]*len(mat_red[0])
for i in range(N):
  for j in range(len(mat_red[0])):
    sum_digit_red[j]^=mat_red[i][j]
#print(sum_digit_red)

answer=0
cnt=0
for j in range(max_digit):
  if sum_digit[j]==0:
    continue
  if sum_digit[j]&1:
    answer+=2**(max_digit-1-j)
  else:
    if sum_digit_red[cnt]&1:
      answer+=2*2**(max_digit-1-j)
    cnt+=1
    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
alist=list(map(int,input().split()))

max_digit=60
mask=1<<(max_digit-1)
mat=[]
for a in alist:
  array=[]
  for _ in range(max_digit):    
    m=a&mask
    if m==0:
      array.append(0)
    else:
      array.append(1)
    a<<=1

  mat.append(array)
#print(mat)

sum_digit=[0]*max_digit
for j in range(max_digit):
  for i in range(N):  
    sum_digit[j]+=mat[i][j]
#print(sum_digit)

mat_red=[]
for i in range(N):
  array=[]
  for j in range(max_digit):
    if sum_digit[j]%2==0 and sum_digit[j]!=0:
      array.append(mat[i][j])
  mat_red.append(array)
#print(mat_red)

pivot_set=set()
for j in range(len(mat_red[0])):
  pivot_row=-1
  for i in range(N):
    if mat_red[i][j]==1:
      if pivot_row==-1 and not i in pivot_set:
        pivot_row=i
        break    
  
  if pivot_row!=-1:
    for i in range(N):
      if i==pivot_row:
        continue
      if mat_red[i][j]==0:
        continue      
      for k in range(j,len(mat_red[0])):
        mat_red[i][k]^=mat_red[pivot_row][k]
        
    pivot_set.add(pivot_row)
  #print(j,pivot_row)
  #print(mat_red)
#print(mat_red)  

sum_digit_red=[0]*len(mat_red[0])
for j in range(len(mat_red[0])):
  for i in range(N):
    sum_digit_red[j]^=mat_red[i][j]
#print(sum_digit_red)

answer=0
cnt=0
for j in range(max_digit):
  if sum_digit[j]==0:
    continue
  if sum_digit[j]%2==1:
    answer+=2**(max_digit-1-j)
  else:
    if sum_digit_red[cnt]%2==1:
      answer+=2*2**(max_digit-1-j)
    cnt+=1
    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
alist=list(map(int,input().split()))

max_digit=60
mat=[]
for a in alist:
  array=[]
  for _ in range(max_digit):    
    m=a%2
    array.append(m)
    a//=2
    
  array.reverse()
  mat.append(array)
#print(mat)

sum_digit=[0]*max_digit
for i in range(N):
  for j in range(max_digit):
    sum_digit[j]+=mat[i][j]
#print(sum_digit)

mat_red=[]
for i in range(N):
  array=[]
  for j in range(max_digit):
    if sum_digit[j]%2==0 and sum_digit[j]!=0:
      array.append(mat[i][j])
  mat_red.append(array)
#print(mat_red)

pivot_set=set()
for j in range(len(mat_red[0])):
  pivot_row=-1
  for i in range(N):
    if mat_red[i][j]==1:
      if pivot_row==-1 and not i in pivot_set:
        pivot_row=i
        break    
  
  if pivot_row!=-1:
    for i in range(N):
      if i == pivot_row:
        continue
      if mat_red[i][j]==0:
        continue      
      for k in range(j,len(mat_red[0])):
        mat_red[i][k]^=mat_red[pivot_row][k]
        
    pivot_set.add(pivot_row)
  #print(j,pivot_row)
  #print(mat_red)
#print(mat_red)  

sum_digit_red=[0]*len(mat_red[0])
for i in range(N):
  for j in range(len(mat_red[0])):
    sum_digit_red[j]^=mat_red[i][j]
#print(sum_digit_red)

answer=0
cnt=0
for j in range(max_digit):
  if sum_digit[j]==0:
    continue
  if sum_digit[j]%2==1:
    answer+=2**(max_digit-1-j)
  else:
    if sum_digit_red[cnt]%2==1:
      answer+=2*2**(max_digit-1-j)
    cnt+=1
    
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 0
for a in A:
    ans ^= a 
M = 2**60-1
b = M^ans
for i in range(N):
    A[i] &= b
A.sort(reverse=True)
for i in range(min(60,N)):
    a = A[i]
    if a == 0:
        break
    l = len(bin(a))
    for j in range(N):
        if j==i:
            continue
        if l==len(bin(A[j]%2**(l-2))):
            A[j] ^= a
        else:
            if i < j:
                break
    A.sort(reverse=True)
s = 0
for a in A:
    s ^= a
ans += 2*s
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

# 解説AC
# http://drken1215.hatenablog.com/entry/2019/09/16/213700
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

DIGIT = 60

mat = []
for a in A:
    mat.append(list(np.binary_repr(a, DIGIT)))
mat = np.array(mat, dtype=np.uint8).T

zero_rows = mat.sum(axis=1) == 0
# ビットの数が奇数の場合、どう頑張っても変わらない
odd_rows = (mat.sum(axis=1) % 2).astype(bool)
mat[odd_rows, :] = 0

# MOD 2 の方程式
# 全部 1 にしたい
mat = np.hstack((mat, np.ones((DIGIT, 1), dtype=np.uint8)))

# 掃き出し法
used_row = np.zeros(DIGIT, dtype=bool)
for col in range(N):
    pivot = (mat[:, col] & ~used_row).argmax()
    if not mat[pivot, col]:
        continue
    used_row[pivot] = True

    pivot_row = mat[pivot].copy()
    mat[mat[:, col].astype(bool)] ^= pivot_row
    mat[pivot] = pivot_row

# 矛盾するやつを除外
# 一番右だけ 1 で他が 0 の行は矛盾
ng_rows = (mat[:, :-1].sum(axis=1) == 0) & (mat[:, -1] == 1)
ok_even_rows = ~odd_rows & ~zero_rows & ~ng_rows

ans = 0
for d in range(DIGIT):
    ans += pow(2, d) * (odd_rows[~d] + ok_even_rows[~d] * 2)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#input
N = int(input())
A = list(map(int, input().split()))

#output
# Python program to find
# maximum XOR subset

# Number of bits to
# represent int
INT_BITS = 64

# Function to return
# maximum XOR subset
# in set[]
def maxSubarrayXOR(set,n):

	# Initialize index of
	# chosen elements
	index = 0

	# Traverse through all
	# bits of integer
	# starting from the most
	# significant bit (MSB)
	for i in range(INT_BITS-1,-1,-1):

		# Initialize index of
		# maximum element and
		# the maximum element
		maxInd = index
		maxEle = -9223372036854775808
		for j in range(index,n):

			# If i'th bit of set[j]
			# is set and set[j] is
			# greater than max so far.
			if ( (set[j] & (1 << i)) != 0
					and set[j] > maxEle ):

				maxEle = set[j]
				maxInd = j

		# If there was no
		# element with i'th
		# bit set, move to
		# smaller i
		if (maxEle == -9223372036854775808):
			continue

		# Put maximum element
		# with i'th bit set
		# at index 'index'
		temp = set[index]
		set[index] = set[maxInd]
		set[maxInd] = temp

		# Update maxInd and
		# increment index
		maxInd = index

		# Do XOR of set[maxIndex]
		# with all numbers having
		# i'th bit as set.
		for j in range(n):

			# XOR set[maxInd] those
			# numbers which have the
			# i'th bit set
			if (j != maxInd and
			(set[j] & (1 << i)) != 0):
				set[j] ^= set[maxInd]

		# Increment index of
		# chosen elements
		index += 1

	# Final result is
	# XOR of all elements
	res = 0
	for i in range(n):
		res ^= set[i]
	return res

B = 0
for i in range(N):
	B ^= A[i]

A2 = [a&(~B) for a in A]
d = maxSubarrayXOR(A2, N)

print(int(d) + int(B^d))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
xor_sum = 0
for i in range(N):
    xor_sum = xor_sum ^ A[i]

# define 'interesting bit'
xor_sum = bin(xor_sum)[2:]
reversed_xor_sum = xor_sum[::-1]
interest_bit = set([_ for _ in range(60)])
uninterest_bit = set([])
cnt = 0
uninterest_num = 0
for v in reversed_xor_sum:
    if v == '1':
        interest_bit.remove(cnt)
        uninterest_bit.add(cnt)
        uninterest_num += 2 ** cnt
    cnt += 1

#print('interest_bit={}'.format(interest_bit))
#print('uninterest_bit={}'.format(uninterest_bit))

# define {A_i'} in binary forms
A_ = [[0] * 60 for _ in range(N)]
for i in range(N):
    for j in range(60):
        if j in interest_bit:
            l = len(bin(A[i])) - 2
            if j <= l - 1:
                A_[i][59 - j] = int(bin(A[i])[-1 - j])

#print(A_)

# basic transformation of A_
basis_idx = []
basis_idx_set = set([])
for j in range(59, -1, -1):
    exist = None
    for i in range(N):
        if A_[i][59 - j] == 1 and i not in basis_idx_set and exist == None:
            basis_idx.append(i)
            basis_idx_set.add(i)
            exist = i
        elif A_[i][59 - j] == 1 and i not in basis_idx_set and exist != None:
            for k in range(60):
                A_[i][k] ^= A_[exist][k]
        else:
            continue
    #print('for j={}, basis_idx={}'.format(j, basis_idx))

#print('basis indices are {}'.format(basis_idx))

# maximize X'_blue (= ans)
ans = 0
for i in basis_idx:
    bin_val = ''.join(map(str, A_[i]))
    val = int(bin_val, 2)
    #print(val)
    ans = max(ans, ans ^ val)

print(ans * 2 + uninterest_num)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = list(map(int, input().split()))
xor_sum = 0
for i in range(N):
    xor_sum = xor_sum ^ A[i]

# define 'interesting bit'
xor_sum = bin(xor_sum)[2:]
reversed_xor_sum = xor_sum[::-1]
interest_bit = set([_ for _ in range(60)])
uninterest_bit = set([])
cnt = 0
uninterest_num = 0
for v in reversed_xor_sum:
    if v == '1':
        interest_bit.remove(cnt)
        uninterest_bit.add(cnt)
        uninterest_num += 2 ** cnt
    cnt += 1

#print('interest_bit={}'.format(interest_bit))
#print('uninterest_bit={}'.format(uninterest_bit))

# define {A_i'} in binary forms
A_ = [[0] * 60 for _ in range(N)]
for i in range(N):
    for j in range(60):
        if j in interest_bit:
            l = len(bin(A[i])) - 2
            if j <= l - 1:
                A_[i][59 - j] = int(bin(A[i])[-1 - j])

#print(A_)

# basic transformation of A_
basis_idx = []
for j in range(59, -1, -1):
    exist = None
    for i in range(N):
        if A_[i][59 - j] == 1 and i not in basis_idx and exist == None:
            basis_idx.append(i)
            exist = i
        elif A_[i][59 - j] == 1 and i not in basis_idx and exist != None:
            for k in range(60):
                A_[i][k] ^= A_[exist][k]
        else:
            continue
    #print('for j={}, basis_idx={}'.format(j, basis_idx))

#print('basis indices are {}'.format(basis_idx))

# maximize X'_blue (= ans)
ans = 0
for i in basis_idx:
    bin_val = ''.join(map(str, A_[i]))
    val = int(bin_val, 2)
    #print(val)
    ans = max(ans, ans ^ val)

print(ans * 2 + uninterest_num)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = list(map(int, input().split()))
xor_sum = 0
for i in range(N):
    xor_sum = xor_sum ^ A[i]

# define 'interesting bit'
xor_sum = bin(xor_sum)[2:]
reversed_xor_sum = xor_sum[::-1]
interest_bit = set([_ for _ in range(60)])
uninterest_bit = set([])
cnt = 0
uninterest_num = 0
for v in reversed_xor_sum:
    if v == '1':
        interest_bit.remove(cnt)
        uninterest_bit.add(cnt)
        uninterest_num += 2 ** cnt
    cnt += 1

#print('interest_bit={}'.format(interest_bit))
#print('uninterest_bit={}'.format(uninterest_bit))

# define {A_i'} in binary forms
A_ = np.array([[0] * 60 for _ in range(N)])
for i in range(N):
    for j in range(60):
        if j in interest_bit:
            l = len(bin(A[i])) - 2
            if j <= l - 1:
                A_[i][59 - j] = int(bin(A[i])[-1 - j])

#print(A_)

# basic transformation of A_
basis_idx = []
for j in range(59, -1, -1):
    exist = None
    for i in range(N):
        if A_[i][59 - j] == 1 and i not in basis_idx and exist == None:
            basis_idx.append(i)
            exist = i
        elif A_[i][59 - j] == 1 and i not in basis_idx and exist != None:
            A_[i] ^= A_[exist]
        else:
            continue
    #print('for j={}, basis_idx={}'.format(j, basis_idx))

#print('basis indices are {}'.format(basis_idx))

# maximize X'_blue (= ans)
ans = 0
for i in basis_idx:
    bin_val = ''.join(map(str, A_[i]))
    val = int(bin_val, 2)
    #print(val)
    ans = max(ans, ans ^ val)

print(ans * 2 + uninterest_num)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
A = list(map(int, input().split()))

def honya(n, L):
  k = 0
  E = len(L)
  for i in range(n - 1, -1, -1):
    for j in range(k, E):
      if (L[j] >> i) & 1:
        L[k], L[j] = L[j], L[k]
        break
    else:
      continue
    k += 1
    for j in range(k, E):
      if (L[j] >> i) & 1:
        L[j] ^= L[k - 1]
  return L

def nasu(n):
  return math.ceil(math.log(n + 1, 2))

A.sort(reverse = True)
M = nasu(A[0])
P = [1]
for i in range(M):
  P.append(P[-1] * 2)

D = [0] * M
for i in range(N):
  t = A[i]
  for j in range(M):
    if t & 1:
      D[j] += 1
    t >>= 1

ans = 0
for i in range(M - 1, -1, -1):
  if D[i] % 2 == 1:
    ans += P[i]
    for j in range(N):
      A[j] &= ~(1 << i)

L = honya(M, A)
t = 0
for i in range(N):
  if L[i] == 0: break
  if (t & (1 << (nasu(L[i]) - 1))) == 0:
    t ^= L[i]

for i in  range(M - 1, -1, -1):
  if (t >> i) & 1:
    ans += P[i] * 2
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
N=int(input())
A=list(map(int,input().split()))
 
XOR=0
for a in A:
    XOR^=a

for i in range(N):
    A[i] &=~XOR

USED=[0]*N

for bi in range(60,-1,-1):
    for i in range(N):
        if USED[i]==0 and A[i] & (1<<bi)!=0:
            USED[i]=1
            useind=i
            break
    else:
        continue
    
    for i in range(N):
        if i==useind:
            continue
        if A[i] & (1<<bi)!=0:
            A[i]^=A[useind]

ANS=0
for a in A:
    ANS^=a

print(2*ANS+XOR)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import math
import sys


DEBUG = False


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, A):
    allxor = 0
    for a in A:
        allxor ^= a

    B = [0] * N

    ans = 0
    bcount = 0
    for bit in range(61, -1, -1):
        mask = 1 << bit
        if allxor & mask:
            ans <<= 1
            ans |= 1
            continue

        bset = set()
        for i in range(N):
            b = B[i]
            b <<= 1
            b |= (A[i] & mask) >> bit
            B[i] = b
            bset.add(b)
        bcount += 1

        full_bit = (1 << bcount) - 1

        blist = list(bset)
        blist1 = blist[:len(blist) // 2]
        blist2 = blist[len(blist) // 2:]

        r1 = set([0])
        for b in blist1:
            for c in list(r1):
                r1.add(b ^ c)

        r2 = set([0])
        for b in blist2:
            for c in list(r2):
                r2.add(b ^ c)

        best = full_bit - 1
        for b1 in r1:
            if b1 ^ full_bit in r2:
                best = full_bit
                break

        bestb = best & 1
        ans <<= 1
        ans |= bestb

        if bestb == 0:
            for i in range(N):
                B[i] >>= 1
            bcount -= 1

    return ans + (ans ^ allxor)


def main():
    N = int(inp())
    A = [int(e) for e in inp().split()]
    print(solve(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3

import math
import sys


DEBUG = False


def inp():
    return sys.stdin.readline().rstrip()


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, A):
    allxor = 0
    for a in A:
        allxor ^= a

    B = [0] * N

    ans = 0
    bcount = 0
    for bit in range(61, -1, -1):
        mask = 1 << bit
        if allxor & mask:
            ans <<= 1
            ans |= 1
            continue

        bset = set()
        for i in range(N):
            b = B[i]
            b <<= 1
            b |= (A[i] & mask) >> bit
            B[i] = b
            bset.add(b)
        bcount += 1

        full_bit = (1 << bcount) - 1
        rset = set([0])
        for b in bset:
            for c in set(rset):
                rset.add(b ^ c)
            if full_bit in rset:
                break

        best = full_bit if full_bit in rset else full_bit - 1
        assert best in rset
        bestb = best & 1
        ans <<= 1
        ans |= bestb

        if bestb == 0:
            for i in range(N):
                B[i] >>= 1
            bcount -= 1

    return ans + (ans ^ allxor)


def main():
    N = int(inp())
    A = [int(e) for e in inp().split()]
    print(solve(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
N = int(input())
A = list(map(int,input().split()))

ans = 0
for i in range(N):
    ans ^= A[i]

for i in range(N):
    A[i] = (~ans)&A[i]
    A[i] *= -1

heapq.heapify(A)
b = []

M = -heapq.heappop(A)
while A:
    m = -heapq.heappop(A)
    if m == 0:
        break
    if len(bin(M)) == len(bin(m)):
        m ^= M
        heapq.heappush(A,-m)
    else:
        b.append(M)
        M = m
b.append(M)

b = b[::-1]
ans_ = 0
for i in range(len(b)):
    M = b[i]
    for j in range(i+1,len(b)):
        m = b[j]
        if len(bin(M))==len(bin(M&m)):
            b[j] ^= M
    ans_ ^= M

ans += ans_*2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heapreplace

n = int(input())
aaa = list(map(int, input().split()))
# print(*(f'{a:08b}' for a in aaa))

all_x = 0
for a in aaa:
    all_x ^= a
mask = ~all_x
bbb = [-(a & mask) for a in aaa if a & mask]
heapify(bbb)

ans = 0
while bbb and bbb[0] < 0:
    a = -heappop(bbb)
    l = a.bit_length()
    while bbb and (-bbb[0]).bit_length() == l:
        heapreplace(bbb, -(a ^ (-bbb[0])))
    b = 1 << (l - 1)
    if ans & b == 0:
        ans ^= a

print(2 * ans + all_x)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heapreplace

n = int(input())
aaa = list(map(int, input().split()))
# print(*(f'{a:08b}' for a in aaa))

all_x = 0
for a in aaa:
    all_x ^= a
mask = ~all_x
bbb = [-(a & mask) for a in aaa if a & mask]
heapify(bbb)

ans = 0
while bbb and bbb[0] < 0:
    a = -heappop(bbb)
    l = a.bit_length()
    while bbb and (-bbb[0]).bit_length() == l:
        x = a ^ (-bbb[0])
        if x:
            heapreplace(bbb, -x)
        else:
            heappop(bbb)
    b = 1 << (l - 1)
    if ans & b == 0:
        ans ^= a

print(2 * ans + all_x)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heapreplace

n = int(input())
aaa = list(map(int, input().split()))
# print(*(f'{a:08b}' for a in aaa))

all_x = 0
for a in aaa:
    all_x ^= a
mask = ~all_x
bbb = [-(a & mask) for a in aaa]
heapify(bbb)

red = set()
while bbb and bbb[0] < 0:
    a = -heappop(bbb)
    l = a.bit_length()
    b = 1 << (l - 1)
    while bbb and (-bbb[0]).bit_length() == l:
        heapreplace(bbb, -(a ^ (-bbb[0])))
    red = {s ^ a if s & b else s for s in red}
    red.add(a)

ans = 0
for a in red:
    ans ^= a

print(2 * ans + all_x)

Submission status: Time Limit Exceeded

Solution code:
def gauss_jordan(A, is_extended):
    """掃き出し法でジョルダン標準形を求める"""
    cnt_col = len(A[0])
    cnt_row = len(A)

    rank = 0
    for col in range(cnt_col):
        #  拡大係数行列の場合は最後の行は掃き出ししない
        if is_extended and col == cnt_col - 1:
            break

        # ピボットを探す
        pivot = -1
        for row in range(rank, cnt_row):
            if A[row][col]:
                pivot = row
                break

        #  ピボットがない場合は次の列に
        if pivot == -1:
            continue

        # 行をスワップする
        A[pivot], A[rank] = A[rank], A[pivot]

        # ピボットのある列の値がすべて0になるように掃き出す
        A_rank = A[rank]
        for row in range(cnt_row):
            if row != rank and A[row][col]:
                for col2, A_rank_col2 in enumerate(A_rank):
                      A[row][col2] ^= A_rank_col2
        rank += 1

    return A


n = int(input())
a = list(map(int, input().split()))

# 全てのxorを計算
# 全てのaを2進数に変換
max_a = max(a)
max_a = bin(max_a)[2::]
xor_sum = 0
for i in range(n):
    xor_sum ^= a[i]
xor_sum = bin(xor_sum)[2::].zfill(len(max_a))

for i in range(n):
    a[i] = bin(a[i])[2::].zfill(len(max_a))

# 行列を作る
# 興味深くないビットについては予めansに答えを足しておく
matrix = [[0] * len(max_a) for _ in range(n)]
ans = 0
for i in range(len(max_a)):
    if xor_sum[i] == "1":
        ans += 2 ** (len(max_a) - i - 1)
    else:
        for j in range(n):
            matrix[j][i] = int(a[j][i])

# ジョルダン標準形を求める
matrix = gauss_jordan(matrix, False)

# xorを取る
tmp = 0
for i in range(n):
    tmp ^= int("".join(map(str, matrix[i])), 2)

# tmpは赤玉、青玉ともに値を持つので2倍して足す
ans = ans + 2*tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gauss_jordan(A, is_extended):
    """掃き出し法でジョルダン標準形を求める"""
    cnt_col = len(A[0])
    cnt_row = len(A)

    #for row in range(cnt_row):
    #    for col in range(cnt_col):
    #        A[row][col] = A[row][col] % MOD

    rank = 0
    for col in range(cnt_col):
        #  拡大係数行列の場合は最後の行は掃き出ししない
        if is_extended and col == cnt_col - 1:
            break

        # ピボットを探す
        pivot = -1
        for row in range(rank, cnt_row):
            if A[row][col]:
                pivot = row
                break

        #  ピボットがない場合は次の列に
        if pivot == -1:
            continue

        # 行をスワップする
        A[pivot], A[rank] = A[rank], A[pivot]

        # ピボットのある列の値がすべて0になるように掃き出す
        for row in range(cnt_row):
            if row != rank and A[row][col]:
                for col2 in range(cnt_col):
                      A[row][col2] ^= A[rank][col2]
        rank += 1

    return A


n = int(input())
a = list(map(int, input().split()))

# 全てのxorを計算
# 全てのaを2進数に変換
max_a = max(a)
max_a = bin(max_a)[2::]
xor_sum = 0
for i in range(n):
    xor_sum ^= a[i]

xor_sum = bin(xor_sum)[2::].zfill(len(max_a))
for i in range(n):
    a[i] = bin(a[i])[2::].zfill(len(max_a))

# 行列を作る
# 興味深くないビットについては予めansに答えを足しておく
matrix = [[0] * len(max_a) for _ in range(n)]
ans = 0
for i in range(len(max_a)):
    if xor_sum[i] == "1":
        ans += 2 ** (len(max_a) - i - 1)
    else:
        for j in range(n):
            matrix[j][i] = int(a[j][i])

# ジョルダン標準形を求める
matrix = gauss_jordan(matrix, False)

# xorを取る
tmp = 0
for i in range(n):
    tmp ^= int("".join(map(str, matrix[i])), 2)

# tmpは赤玉、青玉ともに値を持つので2倍して足す
ans = ans + 2*tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gauss_jordan(A, MOD, is_extended):
    """掃き出し法でジョルダン標準形を求める(mod p)"""
    
    cnt_col = len(A[0])
    cnt_row = len(A)

    for row in range(cnt_row):
        for col in range(cnt_col):
            A[row][col] = A[row][col] % MOD

    rank = 0
    for col in range(cnt_col):
        #  拡大係数行列の場合は最後の行は掃き出ししない
        if is_extended and col == cnt_col - 1:
            break

        # ピボットを探す
        pivot = -1
        for row in range(rank, cnt_row):
            if A[row][col] != 0:
                pivot = row
                break

        #  ピボットがない場合は次の列に
        if pivot == -1:
            continue

        # 行をスワップする
        A[pivot], A[rank] = A[rank], A[pivot]

        # ピボットの値を1にする
        inv = pow(A[rank][col], MOD - 2, MOD)
        for col2 in range(cnt_col):
            A[rank][col2] = (A[rank][col2] * inv) % MOD


        # ピボットのある列の値がすべて0になるように掃き出す
        for row in range(cnt_row):
            if row != rank and A[row][col] > 0:
                fac = A[row][col]
                for col2 in range(cnt_col):
                    A[row][col2] -= (A[rank][col2] * fac) % MOD
                    if A[row][col2] < 0:
                        A[row][col2] += MOD
        rank += 1

    return A


n = int(input())
a = list(map(int, input().split()))

# 全てのaを2進数に変換
max_a = max(a)
max_a = bin(max_a)[2::]
for i in range(n):
    a[i] = bin(a[i])[2::].zfill(len(max_a))

# 行列を作る
# 興味深くないビットについては予めansに答えを足しておく
ans = 0
matrix = [[0] * len(max_a) for _ in range(n)]
for i in range(len(max_a)):
    cnt = 0
    for j in range(n):
        if a[j][i] == "1":
            cnt += 1
    if cnt % 2 == 1:
        ans += 2 ** (len(max_a) - i - 1)
    else:
        for j in range(n):
            matrix[j][i] = int(a[j][i])

# ジョルダン標準形を求める
matrix = gauss_jordan(matrix, 2, False)

# xorを取る
tmp = 0
for i in range(n):
    tmp ^= int("".join(map(str, matrix[i])), 2)

# tmpは赤玉、青玉ともに値を持つので2倍して足す
ans = ans + 2*tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gauss_jordan(A, MOD, is_extended):
    """掃き出し法でジョルダン標準形を求める(mod p)"""
    
    cnt_col = len(A[0])
    cnt_row = len(A)

    for row in range(cnt_row):
        for col in range(cnt_col):
            A[row][col] = A[row][col] % MOD

    rank = 0
    for col in range(cnt_col):
        #  拡大係数行列の場合は最後の行は掃き出ししない
        if is_extended and col == cnt_col - 1:
            break

        # ピボットを探す
        pivot = -1
        for row in range(rank, cnt_row):
            if A[row][col] != 0:
                pivot = row
                break

        #  ピボットがない場合は次の列に
        if pivot == -1:
            continue

        # 行をスワップする
        A[pivot], A[rank] = A[rank], A[pivot]

        # ピボットの値を1にする
        inv = pow(A[rank][col], MOD - 2, MOD)
        for col2 in range(cnt_col):
            A[rank][col2] = (A[rank][col2] * inv) % MOD


        # ピボットのある列の値がすべて0になるように掃き出す
        for row in range(cnt_row):
            if row != rank and A[row][col] > 0:
                fac = A[row][col]
                for col2 in range(cnt_col):
                    A[row][col2] -= (A[rank][col2] * fac) % MOD
                    if A[row][col2] < 0:
                        A[row][col2] += MOD
        rank += 1

    return A


n = int(input())
a = list(map(int, input().split()))

# 全てのaを2進数に変換
max_a = max(a)
max_a = bin(max_a)[2::]
for i in range(n):
    a[i] = bin(a[i])[2::].zfill(len(max_a))

# 行列を作る
# 興味深くないビットについては予めansに答えを足しておく
ans = 0
matrix = [[] for i in range(n)]
for i in range(len(max_a)):
    cnt = 0
    for j in range(n):
        if a[j][i] == "1":
            cnt += 1
    if cnt % 2 == 1:
        ans += 2 ** (len(max_a) - i - 1)
        for j in range(n):
            matrix[j].append(0)
    else:
        for j in range(n):
            matrix[j].append(int(a[j][i]))

# ジョルダン標準形を求める
matrix = gauss_jordan(matrix, 2, False)

# 興味深いビットに対してxorを取る
tmp = 0
for i in range(n):
    tmp ^= int("".join(map(str, matrix[i])), 2)

# tmpは赤玉、青玉ともに値を持つので2倍して足す
ans = ans + 2*tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

def F2_GaussJordan(A, is_extended = False):
    rank = 0
    for col in range(len(A[0])):
        if (is_extended and col == len(A[0])-1):
            break
        pivot = -1
        for row in range(rank,len(A)):
            if A[row][col]:
                pivot = row
                break
        if pivot == -1: 
            continue
        A[pivot],A[rank] = A[rank],A[pivot]
        for row in range(rank+1,len(A)):
            if A[row][col]:
                A[row] = [A[row][j]^A[rank][j] for j in range(len(A[0]))]
        rank += 1
    return A

N = I()
A = III()

xor = 0
for i in range(N):
    xor ^= A[i]

max_digit = len(format(max(A), 'b'))

use_digit = []
ans = 0
for j in range(max_digit)[::-1]:
    if xor>>j & 1:
        ans += 2**j
    else:
        use_digit.append(j)

a = [[0]*len(use_digit) for _ in range(N)]
k = 0
for k,j in enumerate(use_digit):
    for i in range(N):
        if A[i]>>j & 1:
            a[i][k] = 1

g = F2_GaussJordan(a,False)

s = 0
for i in range(N):
    s = max(s,s^sum([g[i][j]*2**use_digit[j] for j in range(len(use_digit))]))
ans += 2*s

print(ans)