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: Accepted

Solution code:
from numpy import int64, bitwise_xor

N, *A = map(int, open(0).read().split())
A = int64(A)

x = bitwise_xor.reduce(A)
A &= ~x

res = 0
while A.any():
    ma = A.max()
    msb = 1 << (int(ma).bit_length() - 1)

    A[(A & msb) > 0] ^= ma

    res ^= ma * (not res & msb)

print(x + 2 * res)

Submission status: Accepted

Solution code:
from numpy import int64, bitwise_xor

N, *A = map(int, open(0).read().split())
A = int64(A)

x = bitwise_xor.reduce(A)
A &= ~x

res = 0
while any(A):
    ma = A.max()
    msb = 1 << (int(ma).bit_length() - 1)

    A[(A & msb) > 0] ^= ma

    res ^= ma * (not res & msb)

print(x + 2 * res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np

N = int(input())
A = np.array([int(x) for x in input().split()],dtype=np.int64)

"""
F_2 上の線形代数。基本変形で簡単な基底を得る。
"""

xor = np.bitwise_xor.reduce(A)

A = np.concatenate([np.array([1<<i for i in range(60) if xor&(1<<i)],np.int64),A])

for k in range(60,-1,-1):
    bit = 1<<k
    one = (A&bit != 0)
    i = np.where(one & (A < (1<<(k+1))))[0]
    if len(i) == 0:
        continue
    i = i[0]
    x = A[i]
    A[one] ^= x
    A[i] = x

A = A[A != 0]
A.sort()
A = A[::-1]

if len(A) > 0:
	red = np.bitwise_xor.reduce(A)
else:
    red = 0
blue = red^xor
answer = red + blue
print(answer)

Submission status: Accepted

Solution code:
from numpy import *
f=bitwise_xor.reduce
N=int(input())
A=array(input().split(),int64)
X=f(A)
A=hstack((A,array([1<<i for i in range(60)if X&(1<<i)],int64)))
for k in range(60)[::-1]:
  b=1<<k
  j=A&b!=0
  i=where(j&(A<2*b))[0]
  if len(i):i=i[0];x=A[i];A[j]^=x;A[i]=x
r=f(A)
print(r+(r^X))

Submission status: Accepted

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))-3
    for j in range(N):
        if j==i:
            continue
        if A[j]//2**l%2==1:
            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: Accepted

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

osum = 0
for x in xs:
    osum = osum ^ x

for i in range(N):
    xs[i] = xs[i] & ~osum

vs = set()
for i in range(60):
    i = 59 - i
    base = -1
    for j, x in enumerate(xs):
        if j in vs:
            continue
        if (x >> i) % 2:
            vs.add(j)
            base = j
            break
    if base < 0:
        continue
    for j, x in enumerate(xs):
        if j == base:
            continue
        if (x >> i) % 2:
            xs[j] = xs[j] ^ xs[base]

ksum = 0
for x in xs:
    ksum = ksum ^ x

print(osum+ksum*2)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    xor=0
    for a in A:
        xor^=a # どう分けても確定しているbit

    A=[a&(~xor) for a in A] # 見るべき bit
    xor1=0
    for a in A:
        xor1^=a

    A.sort(reverse=1)
    now=0
    for d in range(60,-1,-1):
        for p in range(now,n):
            if((A[p]>>d)):
                for i in range(n):
                    if(i==p): continue
                    if((A[i]>>d)&1):
                        A[i]^=A[p]
                A[p],A[now]=A[now],A[p]
                now+=1
                break

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

    xor3=xor1^xor2
    print(xor+xor2+xor3)
resolve()

Submission status: Accepted

Solution code:
from numpy import *
N = int(input())
A = fromiter(map(int, input().split()), int64)
x = bitwise_xor.reduce(A)
A &= ~x
r = 0
while any(A):
    a = A.max()
    m = 1 << int(a).bit_length() - 1
    A[A&m>0] ^= a
    r ^= a * (not r & m)
print(x+r+r)

Submission status: Accepted

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

p = [0] * 62

def insert(x):
    for i in range(60, -1, -1):
        if x >> i & 1:
            if not p[i]:
                p[i] = x
                break
            x ^= p[i]

all = 0 
for x in a:
    all ^= x

for i in range(61):
    if all >> i & 1:
        for j in range(n):
            if a[j] >> i & 1:
                a[j] -= (1<<i)

for x in a:
    insert(x)
ans = 0
for i in range(60, -1, -1):
    if (p[i] ^ ans) > ans:
        ans = p[i] ^ ans
print(ans + (ans ^ all))

Submission status: Accepted

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

sums = 0
for x in a:
    sums ^= x

blu = set()
remain = set(range(n))

for i in range(61)[::-1]:
    if (sums >> i) & 1 == 0:
        di = -1
        for j in remain:
            if (a[j] >> i) & 1 == 1:
                di = j
                break
        if di != -1:
            blu.add(di)
            remain.remove(di)
            for j in range(n):
                if j != di and (a[j] >> i) & 1 == 1:
                    a[j] = a[j] ^ a[di]
bsum = 0
for i in blu:
    bsum = bsum ^ a[i]
print(bsum + (sums ^ bsum))

Submission status: Accepted

Solution code:
import sys
from functools import reduce
from operator import xor
readline = sys.stdin.readline

def rev(x, k):
    res = 0
    for cnt in range(k):
        res = (res<<1) + (1&(x>>cnt))
    return res
        
class GE():
    #mod2　なら　Aは1重リストで渡して, max(bit_length) をMに渡してあげた方が速い
    def __init__(self, A, mod, M = 0):
        self.N = len(A)
        if M:
            self.M = M
        else:
            self.M = len(A[0])
        self.mod = mod
        self.A = A[:]
        self.uptri = None
        self.A2 = None
        self.pivot = []
        self.R = None
    def ut(self):
        if self.mod != 2:
            if self.uptri is not None:
                return self.uptri
            self.uptri = self.A[:]
            c = 0
            for i in range(self.N):
                if i + c >= self.M:
                    break
                while self.uptri[i][i+c] == 0:
                    for j in range(i+1, self.N):
                        if self.uptri[j][i+c]:
                            self.uptri[i], self.uptri[j] = self.uptri[j], self.uptri[i]
                            break
                    else:
                        c += 1
                        if i + c == self.M:
                            break
                else:
                    self.pivot.append((i, i+c))
                    t = pow(self.uptri[i][i+c], self.mod - 2, self.mod)
                    for j in range(i+1, self.N):
                        tj = t * self.uptri[j][i+c]
                        self.uptri[j][i+c:] = [(aj - tj*ai) % self.mod for ai, aj in zip(self.uptri[i][i+c:], self.uptri[j][i+c:])]
                    continue
                break
            for pi, pj in self.pivot[::-1]:
                t = pow(self.uptri[pi][pj], self.mod-2, self.mod)
                self.uptri[pi][pj:] = [(ai * t) % self.mod for ai in self.uptri[pi][pj:]]
                for i in range(pi-1, -1, -1):
                    ti = self.uptri[i][pj]
                    self.uptri[i][pj:] = [(ai - api*ti) % self.mod for ai, api in zip(self.uptri[i][pj:], self.uptri[pi][pj:])]
            
            return self.uptri
        else:
            if self.A2 is not None:
                return self.A2
            self.A2 = self.A[:]
            c = 0
            for i in range(self.N):
                if i + c >= self.M:
                    break
                while not self.A2[i] & 2**(i+c):
                    for j in range(i+1, self.N):
                        if self.A2[j] & 2**(i+c):
                            self.A2[i], self.A2[j] = self.A2[j], self.A2[i]
                            break
                    else:
                        c += 1
                        if i + c == self.M:
                            break
                else:
                    self.pivot.append((i, i+c))
                    for j in range(i+1, self.N):
                        if self.A2[j] & 2**(i+c):
                            self.A2[j] ^= self.A2[i]
                    continue
                break
            for pi, pj in self.pivot[::-1]:
                for i in range(pi-1, -1, -1):
                    if 2**pj & self.A2[i]:
                        self.A2[i] ^= self.A2[pi]
            
            return self.A2
            
                
    def rank(self):
        if self.R is not None:
            return self.R
        self.ut()
        self.R = len(self.pivot)
        return self.R
    
    def solve(self):
        self.ut()

N = int(readline())
A = list(map(int, readline().split()))
M = reduce(xor, A)
ans = M
k = max(A).bit_length()
T = GE([rev(a&(~M), k) for a in A], 2, 60)
print(ans + 2*(reduce(xor, [rev(x, k) for x in T.ut()])))

Submission status: Accepted

Solution code:
# coding: utf-8
import numpy as np


def solve(*args: str) -> str:
    n = int(args[0])
    A = np.array(args[1].split(), dtype=np.int64)

    n_bit = len(np.binary_repr(max(A)))

    xor = np.bitwise_xor.reduce(A)
    A &= ~xor

    for b in reversed(range(n_bit)):
        b_set = A & 1 << b != 0
        msb_args = np.where(b_set & (A < 1 << b+1))[0]
        if len(msb_args):
            b_set[msb_args[0]] = False
            A[b_set] ^= A[msb_args[0]]

    ret = 2*np.bitwise_xor.reduce(A) + xor

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())), dtype = np.int64)
a = np.bitwise_xor.reduce(A)
for i in range(60):
    bit = 1<<i
    if bit & a:
        A^=(A&bit)
for k in range(60, -1, -1):
    bit = 1<<k
    one = (A&bit != 0)
    i = np.where(one & (A < (1<<(k+1))))[0]
    if len(i) == 0:
        continue
    i = i[0]
    x = A[i]
    A[one]^=x
    A[i] = x
b = np.bitwise_xor.reduce(A)
a^=b
print(a+b)

Submission status: Accepted

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

bad = 0
for n in nums: bad ^= n

BASIS_LENGTH = 61

def reduce(num):
    total = 0
    power = 0
    for i in range(BASIS_LENGTH):
        if bad & (1 << i): continue
        total += ((num & (1 << i)) >> i) * pow(2, power)
        power += 1
    return total
    
def expand(num):
    total = 0
    power = 0
    for i in range(BASIS_LENGTH):
        if bad & (1 << i):
            continue
        total += ((num & (1 << power)) >> power) * pow(2, i)
        power += 1
    return total

BASIS = [0 for i in range(BASIS_LENGTH)]
numsPrime = [reduce(n) for n in nums]

f = lambda x : max(range(BASIS_LENGTH), key=lambda n: (x & (1 << n), n))

def insertVector(x):
    for i in range(BASIS_LENGTH -1, -1, -1):
        if x & (1 << i) == 0: continue
        if BASIS[i] == 0: BASIS[i] = x; return
        x ^= BASIS[i]
        
for x in numsPrime:
    insertVector(x)

def getSum():
    total = 0
    for el in reversed(BASIS):
        if el == 0: continue
        if el ^ total > total:
            total = el ^ total
    return total

print(2*expand(getSum()) + bad)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
def print_ans(N, input_line):
    """Test Case
    >>> print_ans(3, "3 6 5")
    12
    >>> print_ans(4, "23 36 66 65")
    188
    >>> print_ans(20, "1008288677408720767 539403903321871999 1044301017184589821 215886900497862655 504277496111605629 972104334925272829 792625803473366909 972333547668684797 467386965442856573 755861732751878143 1151846447448561405 467257771752201853 683930041385277311 432010719984459389 319104378117934975 611451291444233983 647509226592964607 251832107792119421 827811265410084479 864032478037725181")
    2012721721873704572
    """
    ar = np.array(input_line.split(), 'int64')
    X = np.bitwise_xor.reduce(ar)
    ar = np.hstack((ar, np.array([ 1 << i for i in range(60) if X&(1 << i)],'int64')))
    for k in range(60)[::-1]:
        b = 1 << k
        j = ar&b != 0
        i = np.where(j&(ar<2 * b))[0]
        if len(i):
            i = i[0]
            x = ar[i]
            ar[j] ^=x
            ar[i] = x
    r = np.bitwise_xor.reduce(ar)
    print(r+(r^X))

if __name__ == '__main__':
    N = int(input().rstrip())
    input_line = input().rstrip()
    print_ans(N, input_line)

Submission status: Accepted

Solution code:
import os
import os
import sys
from functools import reduce
from operator import xor

import numpy as np

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

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

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
A = np.array(A, dtype=np.int64)


def dump(arr):
    for a in arr:
        print(np.binary_repr(a, 60))
    print()


# 解説AC
# 立ってるビットが奇数ならどう分けても結果は同じ
odds = reduce(xor, A)
ans = odds

# 奇数のやつは無視
A &= ~odds

# 行標準形にする
# https://qiita.com/vain0x/items/015ff6d49853e5d9d403#f---xor-sum-3
rank = 0
for d in reversed(range(60)):
    # 下からd桁目が立ってる最初のindex
    bits1 = (A >> d & 1).astype(bool)
    pos = bits1[rank:].argmax() + rank
    if not bits1[pos]:
        continue  # 全部ゼロ
    if pos < rank:
        continue  # rank より下に 1 がない。どう頑張っても変えられない。(?)

    # 基準にする行
    pivot_row = A[pos]
    # 基準以外を全部ゼロにする
    A[bits1] ^= pivot_row
    A[pos] = pivot_row
    # 基準行を一番上に持ってくる
    A[pos], A[rank] = A[rank], A[pos]
    rank += 1

ans += reduce(xor, A) * 2
print(ans)

Submission status: Accepted

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

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

for i in range(n):
    A[i] &= ~not_important

A.sort(reverse=True)
rank = 0
for digit in range(60, -1, -1):
    check_bit = 1 << digit

    for i in range(rank, n):
        if A[i] & check_bit:
            A[rank], A[i] = A[i], A[rank]
            break
    else:
        continue

    for i in range(n):
        if i == rank: continue
        if A[i] & check_bit:
            A[i] ^= A[rank]

    rank += 1

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

print(ans*2 + not_important)

Submission status: Accepted

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

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

for i in range(n):
    A[i] &= ~not_important

A.sort()
rank = 0
for digit in range(60, -1, -1):
    check_bit = 1 << digit

    for i in range(rank, n):
        if A[i] & check_bit:
            A[rank], A[i] = A[i], A[rank]
            break
    else:
        continue

    for i in range(n):
        if i == rank: continue
        if A[i] & check_bit:
            A[i] ^= A[rank]

    rank += 1

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

print(ans*2 + not_important)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, atan2, degrees
from operator import mul
from functools import reduce
sys.setrecursionlimit(10**8)

INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = LI()
total_xor = 0
for i in range(n):
    total_xor ^= A[i]


for i in range(n):
    A[i] &= ~total_xor


r = 0
for i in range(60, -1, -1):
    for j in range(r, n):
        if (A[j] >> i) & 1:
            A[r], A[j] = A[j], A[r]
            break
    else:
        continue
    for j in range(n):
        if j == r:
            continue
        if (A[j] >> i) & 1:
            A[j] ^= A[r]
    r += 1


ret = 0
for i in range(n):
    ret ^= A[i]


print(ret * 2 + total_xor)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.append(0)
for i in range(n):
    a[n] ^= a[i]
    #全ての排他的論理和を求める。→興味があるのは、2進数で1が偶数個立ってる列。
    #ここでa[n]に奇数個しか1がないもの
for i in range(n):
    a[i] &= ~a[n]
r = 0
for i in range(60, -1, -1):
    for j in range(r, n):
        if (a[j] >> i) & 1:
            a[r], a[j] = a[j], a[r]
            break
    else:
        continue
        
    for j in range(n):
        if j == r:
            continue
        if (a[j]>>i) & 1:
            a[j] ^= a[r]
    r+=1
s = 0
for i in range(r):
    s ^= a[i]
    
print(s*2 + a[n])

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
 
s = 0
for i in range(N) :
    s ^= A[i]
    
for i in range(N) :
    A[i] &= ~s
 
r = 0
for i in range(60, -1, -1) :
    for j in range(r, N) :
        if (A[j] >> i) & 1 :
            A[r], A[j] = A[j], A[r]
            break
    else :
        continue
    
    for j in range(N) :
        if j == r :
            continue
        if (A[j] >> i) & 1 :
            A[j] ^= A[r]
    
    r += 1
    
ret = 0
for i in range(r) :
    ret ^= A[i]
    
print(ret * 2 + s)

Submission status: Accepted

Solution code:
from operator import xor
from functools import reduce

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

sums = reduce(xor, a)

blu = set()
remain = set(range(n))

for i in range(61)[::-1]:
    if (sums >> i) & 1 == 0:
        di = -1
        for j in remain:
            if (a[j] >> i) & 1 == 1:
                di = j
                break
        if di != -1:
            blu.add(di)
            remain.remove(di)
            for j in range(n):
                if j != di and (a[j] >> i) & 1 == 1:
                    a[j] = a[j] ^ a[di]
bsum = 0
for i in blu:
    bsum = bsum ^ a[i]
print(bsum + (sums ^ bsum))

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())), dtype = np.int64)

xor = np.bitwise_xor.reduce(A)

# 1の個数が奇数個の桁は定数
odd_digit = [1<<i for i in range(60) if xor&(1<<i)]

# 1の個数が奇数個の桁は無視する
for i in odd_digit:
    A = A & (~i)

for i in range(60, - 1 , - 1):
    one_digit = (A & (1<<i) != 0)
    pivot_flag = np.where(one_digit &  (A < (1<<(i + 1))))[0]
    if len(pivot_flag) == 0:
        continue
    p = pivot_flag[0]
    pivot = A[p]
    A[one_digit] ^= pivot
    A[p] = pivot
    
res = sum(odd_digit) + 2*(np.bitwise_xor.reduce(A))
print(res)

Submission status: Accepted

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 a in A:
	B ^= a

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

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

Submission status: Accepted

Solution code:
def GaussJordan_mod2(A):
    row=len(A)
    col=len(bin(max(A))[2::])
    rank=0
    for c in reversed(range(col)):
        pivot=-1
        for r in range(rank,row):
            if A[r]&(1<<c):
                pivot=r
                break
        if pivot==-1:
            continue
        A[pivot],A[rank]=A[rank],A[pivot]
        A_rank=A[rank]
        for r in range(row):
            if r!=rank and A[r]&(1<<c):
                A[r]^=A[rank]
        rank+=1
    return A

n=int(input())
A=list(map(int, input().split()))
d=len(bin(max(A)))-2
ans=0
xor_sum=0
for i in range(n):
    xor_sum^=A[i]
for i in range(d):
    bit=xor_sum&(1<<i)
    if bit:
        ans+=bit
        for i in range(n):
            A[i]-=bit&A[i]
J=GaussJordan_mod2(A)
xor=0
for i in range(n):
    xor^=J[i]
print(ans+2*xor)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]

s = 0
for i in range(N) :
    s ^= A[i]
    
for i in range(N) :
    A[i] &= ~s

r = 0
for i in range(60, -1, -1) :
    for j in range(r, N) :
        if (A[j] >> i) & 1 :
            A[r], A[j] = A[j], A[r]
            break
    else :
        continue
    
    for j in range(N) :
        if j == r :
            continue
        if (A[j] >> i) & 1 :
            A[j] ^= A[r]
    
    r += 1
    
ret = 0
for i in range(r) :
    ret ^= A[i]
    
print(ret * 2 + s)

Submission status: Accepted

Solution code:
'''
Created on 2019/09/23

@author: oiwaiman
'''


import numpy as np

n = int(input())
aaa = np.fromiter(list(map(int, input().split())), np.int64)

all_x = np.bitwise_xor.reduce(aaa)

mask = ~all_x
bbb = aaa & mask

ans = 0
while True:
    a = bbb.max()
    if a == 0:
        break
    b = 1<<(int(a).bit_length() -1)
    bbb[bbb & b > 0] ^= a
    if ans & b == 0:
        ans ^= a


print (ans*2 + all_x)

Submission status: Accepted

Solution code:
n = int(input())
as_list = input().split(" ")
a_list = [ int(astr) for astr in as_list ]

x = 0

for a in a_list:
    x ^= a
for i in range(n):
    a_list[i] &= ~x
pos = 0

for b in range(59,-1,-1):

    for i in range(pos,n):
        a = a_list[i]
        if a & (1 << b):
            if i > pos:
                
                # i番目とpos番目を入れ替える
                a_list[i] = a_list[pos]
                a_list[pos] = a

            for j in range(n):
                if j == pos:
                    continue
                if a_list[j] & (1 << b):
                    a_list[j] ^= a
            pos += 1
            break
    
y = 0

for a in a_list:
    y ^= a

print(x + 2 * y)

Submission status: Accepted

Solution code:
#!/usr/bin/python3.6
n = int(input())
a = [int(item) for item in input().split()]
aor = 0
axor = 0
for item in a:
    aor |= item
    axor ^= item

rank = 0
ans = 0
for bit in range(61):
    if axor & 1 << (60 - bit):
        ans += 1 << (60 - bit)
        continue
    found_in_bit = False
    for i in range(rank, n):
        if a[i] & 1 << (60 - bit):
            if not found_in_bit:
                a[rank], a[i] = a[i], a[rank]
                # delete bit in upper
                for j in range(rank):
                    if a[j] & 1 << (60 - bit):
                        a[j] ^= a[rank]
                found_in_bit = True
                rank += 1
            else:
                a[i] ^= a[rank-1]
        else:
            continue

ret = 0
for item in a:
    ret ^= item & ~axor
ans += ret * 2
print(ans)

Submission status: Accepted

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: Accepted

Solution code:
#!/usr/bin/python3

import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


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

    while len(A) < 61:
        A.append(0)
    M = len(A)

    row = 0
    ans = 0
    for bi in range(61, -1, -1):
        b = 1 << bi
        if b & allxor:
            ans |= b
            continue

        if not (A[row] & b):
            j = -1
            for i in range(row + 1, M):
                if A[i] & b:
                    j = i
                    break
            if j == -1:
                continue

            A[row], A[j] = A[j], A[row]

        assert A[row] & b
        if not (ans & b):
            ans ^= A[row]

        for i in range(row + 1, M):
            if A[i] & b:
                A[i] ^= A[row]
            assert not (A[i] & b)

        row += 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: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    xor=0
    max_digit=0
    for a in A:
        xor^=a
        max_digit=max(max_digit,a.bit_length())
    # xorのうち、bitが立っていない部分だけでスクリーニング
    for i in range(n): A[i]&=(~xor)
    # このAに対してsweeping
    r=0 # Aのrank
    for d in reversed(range(max_digit)): # digit
        for i in range(r,n):
            if A[i]&(1<<d): # 候補のiをfixする
                for j in range(i+1,n): # sweep(確定してる奴は掃き出さなくてよい)
                    if A[j]&(1<<d): A[j]^=A[i]
                A[i],A[r]=A[r],A[i] # swap
                r+=1
                break
    # sweepしたAに対し、最上位bitから確定させていく
    x=0
    for i in range(r):
        d=A[i].bit_length()
        if not x&(1<<(d-1)):
            x^=A[i]
    print(xor+2*x)
resolve()