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:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor, sqrt
from copy import deepcopy
from collections import Counter, deque
import heapq
from functools import reduce
sys.setrecursionlimit(200000)
# local only
# if not __debug__:
#     fin = open('in_1.txt', 'r')
#     sys.stdin = fin
# local only
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def fi(): return float(input())
def mfi(): return map(float, input().rstrip().split())
def lmfi(): return list(map(float, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(*args, sep=" ", end="\n"): print("debug:", *args, file=sys.stderr, sep=sep, end=end) if not __debug__ else None
def exit(*arg): print(*arg); sys.exit()
# template

from collections import Sequence
import math

class Bitset(Sequence):
    """A very simple bitset implementation for Python.

    Note that, like with normal numbers, the leftmost
    index is the MSB, and like normal sequences, that
    is 0.

    Usage:
        >>> b = Bitset(5)
        >>> b
        Bitset(101)
        >>> b[:]
        [True, False, True]
        >>> b[0] = False
        >>> b
        Bitset(001)
        >>> b << 1
        Bitset(010)
        >>> b >> 1
        Bitset(000)
        >>> b & 1
        Bitset(001)
        >>> b | 2
        Bitset(011)
        >>> b ^ 6
        Bitset(111)
        >>> ~b
        Bitset(110)
    """

    value = 0
    length = 0

    @classmethod
    def from_sequence(cls, seq):
        """Iterates over the sequence to produce a new Bitset.

        As in integers, the 0 position represents the LSB.
        """
        n = 0
        for index, value in enumerate(reversed(seq)):
            n += 2**index * bool(int(value))
        b = Bitset(n)
        return b

    def __init__(self, value=0, length=0):
        """Creates a Bitset with the given integer value."""
        self.value = value
        try:
            self.length = length or math.floor(math.log(value, 2)) + 1
        except Exception:
            self.length = 0

    def __and__(self, other):
        b = Bitset(self.value & int(other))
        b.length = max((self.length, b.length))
        return b

    def __or__(self, other):
        b = Bitset(self.value | int(other))
        b.length = max((self.length, b.length))
        return b

    def __invert__(self):
        b = Bitset(~self.value)
        b.length = max((self.length, b.length))
        return b

    def __xor__(self, value):
        b = Bitset(self.value ^ int(value))
        b.length = max((self.length, b.length))
        return b

    def __lshift__(self, value):
        b = Bitset(self.value << int(value))
        b.length = max((self.length, b.length))
        return b

    def __rshift__(self, value):
        b = Bitset(self.value >> int(value))
        b.length = max((self.length, b.length))
        return b

    def __eq__(self, other):
        try:
            return self.value == other.value
        except Exception:
            return self.value == other

    def __int__(self):
        return self.value

    def __str__(self):
        s = ""
        for i in self[:]:
            s += "1" if i else "0"
        return s

    def __repr__(self):
        return "Bitset(%s)" % str(self)

    def __getitem__(self, s):
        """Gets the specified position.

        Like normal integers, 0 represents the MSB.
        """
        try:
            start, stop, step = s.indices(len(self))
            results = []
            for position in range(start, stop, step):
                pos = len(self) - position - 1
                results.append(bool(self.value & (1 << pos)))
            return results
        except:
            pos = len(self) - s - 1
            return bool(self.value & (1 << pos))

    def __setitem__(self, s, value):
        """Sets the specified position/s to value.

        Like normal integers, 0 represents the MSB.
        """
        try:
            start, stop, step = s.indices(len(self))
            for position in range(start, stop, step):
                pos = len(self) - position - 1
                if value:
                    self.value |= (1 << pos)
                else:
                    self.value &= ~(1 << pos)
            maximum_position = max((start + 1, stop, len(self)))
            self.length = maximum_position
        except:
            pos = len(self) - s - 1
            if value:
                self.value |= (1 << pos)
            else:
                self.value &= ~(1 << pos)
            if len(self) < pos:
                self.length = pos
        return self

    def __iter__(self):
        """Iterates over the values in the bitset."""
        for i in self[:]:
            yield i

    def __len__(self):
        """Returns the length of the bitset."""
        return self.length

def GaussJordan(A):
    rank = 0
    top = [-1] * len(A)
    for col in range(len(A[0])):
        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(len(A)):
            if row != rank and A[row][col]:
                A[row] ^= A[rank]
        top[rank] = col
        rank += 1
    return (rank, top)

def main():
    N = ii()
    A = lmi()
    s = 0
    for i in A:
        s = s ^ i
    s = Bitset(s, 64)
    BitMatrix = []
    for i in range(N):
        BitMatrix.append(Bitset(A[i], 64) & ~s)  # sで立っているbitはあらかじめ消しておく
    rank, top = GaussJordan(BitMatrix)
    ans = Bitset(0, 64)
    for bit in BitMatrix:
        ans ^= bit

    print(int(ans) + int(ans ^ s))


if __name__ == '__main__':
    if not __debug__:
        import doctest
        doctest.testmod()
    main()

Submission status: Time Limit Exceeded

Solution code:
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 = sorted([a for a in A if a != 0])
b = []

while A:
    M = A[-1]
    for i in range(len(A)-1,-1,-1):
        if len(bin(M))==len(bin(A[i])):
            A[i] ^= M
        else:
            break
    A = sorted([a for a in A if a != 0])
    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:
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 = [a for a in A if a != 0]
b = []

while A:
    M = max(A)
    for i in range(len(A)-1,-1,-1):
        if len(bin(M))==len(bin(A[i])):
            A[i] ^= M
        else:
            break
    A = sorted([a for a in A if a != 0])
    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:
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 = [a for a in A if a != 0]
b = []

for i in range(60):
    if len(A) == 0:
        break
    M = max(A)
    A_ = []
    for i in range(len(A)):
        if len(bin(M))==len(bin(A[i])):
            A[i] ^= M
        if A[i] != 0:
            A_.append(A[i])
    b.append(M)
    A = A_

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:
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 = [a for a in A if a != 0]
b = []

while A:
    M = max(A)
    for i in range(len(A)):
        if len(bin(M))==len(bin(A[i])):
            A[i] ^= M
    A = [a for a in A if a != 0]
    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:
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 = [-a for a in A]
heapq.heapify(A)

b = []
while len(A)>1:
    M = -heapq.heappop(A)
    if M == 0:
        break
    while True:
        m = -heapq.heappop(A)
        if len(bin(M))==len(bin(m)):
            m ^= M
            heapq.heappush(A,-m)
        else:
            heapq.heappush(A,-m)
            break
    b.append(M)
if A and A[0] != 0:
    b.append(A[0])

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 *
N = int(input())
A = [int(a) for a in input().split()]
x, t, s, i, h = 0, 0, 0, 59, []
for a in A:
    t ^= a
for a in A:
    heappush(h, -(a&~t))
while h:
    a = -heappop(h)
    while i >= 0 and (a >> i) & 1 == 0:
        i -= 1
        x = 0
    if i < 0: break
    if x:
        heappush(h, -(a^x))
    else:
        x = a
        s = max(s, s^x)
print(s+(t^s))

Submission status: Time Limit Exceeded

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

ans = 0
#even = []
for i in range(60):
	cnt = 0
	for x in a:
		if (x>>i) & 1:
			cnt += 1
	if cnt%2 == 1:
		ans += (1<<i)
		for j in range(n):
			if (a[j]>>i) & 1:
				a[j] -= (1<<i)
#print(ans, even)

yet = 0
for r in range(59, -1, -1):
	stood = False
	for c in range(yet, n):
		if (a[c]>>r) & 1:
			if not stood:
				stood = True
				a[yet], a[c] = a[c], a[yet]
				yet += 1
	if stood:
		for c in range(n):
			if c == yet-1 or (a[c]>>r) & 1 == 0:
				continue
			#print(c)
			a[c] ^= a[yet-1]

tmp = 0
res = 0
for c in range(n):
	tmp ^= a[c]
	res = max(res, tmp) 

print(ans + (res<<1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
全体のxor=S
赤のxor=xとすれば
求値は x+(S^x)の最大値
きつい

上の桁から見て，
Sのi桁目が0の時，その桁が1のものを奇数ずつ割り振りたい．
Sのi桁目が1の時，どんな分け方しても関係ない

上の桁から埋めたいというのはxを最大化したいというのと似ている．
Sのi桁目が1のぶんは先に計算しておく,かつ，各A[i]のその桁を0にしておけば，xを最大化したいという問題に帰着するか

xorの最大化，難しい．基底ベクトルに分解して，上の桁から足していく？
"""
def main():
    mod=10**9+7
    
    N=I()
    A=LI()
    
    S=0
    for i in range(N):
        S=S^A[i]
    
    M=61
    delete=[0]*M#消す桁
    
    ans=0
    for i in range(M):
        if (S>>i) & 1:
            delete[i]=1
            ans+=1<<i
            for j in range(N):
                if (A[j]>>i)&1:
                    A[j]-=1<<i
    
    #基底ベクトルを入れていく                
    vec=[]
    
    #二進数の桁数
    def dig_b(x):
        cnt=0
        while x!=0:
            x=x//2
            cnt+=1
        return cnt
    
    for i in range(N):
        now=A[i]
        d=dig_b(now)
        
        if vec==[]:
            vec.append((now,d))
        else:
            for v in vec:#各基底ベクトルと比較
                if v[1]==d:#今見てる数字と，基底ベクトルの最上位の桁数が同じなら潰せる
                    now=now^v[0]
                    d=dig_b(now)
            if now!=0:#0以外なら基底になる
                vec.append((now,d))
                vec.sort(reverse=True) #基底は大きい順に走査したいので
                
    temp=0
    for v in vec:
        temp2=temp^v[0]
        temp=max(temp,temp2)
        
    ans+=temp*2
    print(ans)
                    
                
        
    
                    
    
                    

        


main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
res = 0
for x in A:
    res ^= x

for i in range(60):
    if (res >> i) & 1:
        for j in range(N):
            if A[j] >> i & 1:
                A[j] ^= 1 << i
start_point = 0
for i in range(60, -1, -1):
    X = 1 << i
    for j in range(start_point, N):
        if A[j] >> i & 1:
            A[start_point], A[j] = A[j], A[start_point]
            for k in range(N):
                if A[k] >> i & 1 and k!=start_point:
                    A[k] ^= A[start_point]
            start_point += 1
            break
plus=0
for x in A:
    plus ^=x
print(res+plus*2)

Submission status: Accepted

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

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

B=[~suma&me for me in A]
B.sort(reverse=True)

cnt=0
for i in range(59,-1,-1):
    B.sort(reverse=True)
    if B[cnt]&(1<<i)>0:
        #print(i,"!")
        for q in range(cnt):
            if B[q]&(1<<i)>0:
                B[q]^=B[cnt]
        for q in range(cnt+1,n):
            if B[q]&(1<<i)>0:
                B[q]^=B[cnt]
            else:
                break          
        cnt+=1

ans=0
B.sort(reverse=True)
for i in range(n):
    ans^=B[i]

print(ans*2+suma)

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/abc141/tasks/abc141_f

=====答えを見た=====

奇数の桁は取り除いて0にしておく
後は適当に掃きだす

"""

from sys import stdin

N = int(stdin.readline())

A = list(map(int , stdin.readline().split() ))

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

for i in range(60,-1,-1):

    ni = 2**i
    if ni & allxor > 0:
        ans += ni
        for j in range(N):
            if ni & A[j] > 0:
                A[j] ^= ni

able = [True] * N
for i in range(60,-1,-1):

    ni = 2**i
    ind = None
    for j in range(N):
        if able[j] and A[j] & ni > 0:
            ind = j
            able[j] = False
            break

    if ind != None:
        for j in range(N):
            if A[j] & ni > 0 and ind != j:
                A[j] ^= A[ind]
#print (A)
pl = 0
for i in range(N):
    pl ^= A[i]
print (ans + pl * 2)

Submission status: Accepted

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

s = 0
for a_i in a:
    s ^= a_i
# print(s)

c = [(~s) & a_i for a_i in a]
base = []
for c_i in c:
    for base_j in base:
        c_i = min(c_i, c_i ^ base_j)
    if c_i != 0:
        for j in range(len(base)):
            base[j] = min(base[j], base[j] ^ c_i)
        base.append(c_i)
        base.sort(reverse=True)

# print(base)
t = 0
for base_j in base:
    t ^= base_j
# print(t)
ans = s + t * 2
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))
x = 0
for a in A:
  x ^= a
now = 0
for i in range(59, -1, -1):
  if x>>i & 1:
    continue
  for j in range(now, n):
    if A[j]>>i & 1:
      A[now], A[j] = A[j], A[now]
      for k in range(n):
        if k != now and A[k]>>i & 1:
          A[k] ^= A[now]
      now += 1
      break
b = 0
for a in A:
  b ^= a
ans = b + (x^b)
print(ans)

Submission status: Accepted

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

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

def gauss_jordan(bs):
    rank = 0
    pivot_cols = []
    for col in reversed(range(61)):
        pivot = -1
        for i,row in enumerate(bs[rank:]):
            if row&(1<<col):
                pivot = rank+i
                break
        if pivot < 0: continue
        pivot_cols.append(col)
        bs[pivot],bs[rank] = bs[rank],bs[pivot]
        for i,row in enumerate(bs):
            if i != rank and row&(1<<col):
                bs[i] ^= bs[rank]
        rank += 1
    return (pivot_cols,bs)

pivot_cols,bs = gauss_jordan(A)
x = 0
for j in reversed(range(61)):
    nx = x|(1<<j)
    b = nx
    for i,c in enumerate(pivot_cols):
        if b&(1<<c):
            b ^= bs[i]
    if (b&nx) == 0:
        x = nx
ans += x*2
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from operator import xor
import numpy as np

def main():
    N = int(input())
    A = np.array(input().split(), np.int64)
    # とりあえず全部XORする
    A_xor_all = np.bitwise_xor.reduce(A)

    # 参考
    # https://betrue12.hateblo.jp/entry/2019/11/22/012255

    # * 全部XORして1になるビットは、どう塗り分けても片方は0, もう片方が1になる
    #   つまり、このビットはどうグループ分けしても和は1になるので、このビットは考察対象から外す
    # * 全部XORして0になるビットは、このビットが1になっている要素の個数を赤と青それぞれで奇数個にしてあげれば、
    #   XOR(赤グループ) + XOR(青グループ)を最大化できる。

    # そこで、Aの各要素を、全部XORして1になるビットを無視した(0にした)数値に変換したもの（A'）を作る
    # A'の要素を2グループに分け、各グループのXORの和が最大になるようにする。
    # ただし、各ビットにおいて、ビットが1になっているA'要素の個数は必ず偶数になっていることから、
    # どうグループ分けしたとしても、必ず「XOR(A'の赤グループ) = XOR(A'の青グループ)」となる。
    # XORを最大化するように要素を選択したときのグループをX'とすると、答えは、以下の通りとなる
    # [A全部のXOR結果] + 2 * [X'のXOR結果]

    # A'を作成
    # 1になっているビットを無視したいので、A全体のXOR結果を反転してANDをとる
    mask = ~A_xor_all
    A_dash = A & mask

    # X'を求める方法
    #   A'の要素の位置を入れ替えたり、
    #   ある要素を、その要素と別の要素とのXOR結果に置き換えたりする操作を繰り返し、
    #   A'の行標準形Rを求めると、
    #   Rの全要素のXOR結果が、X'となる

    # 行標準形: 行列の左下の方が0になるような形（連立方程式を解くときに作るようなやつ）
    #          また、i行目において、一番左にある1がn列目だとすると、n列目全体において、i行目以外では全て0になっている
    # 例
    #   1 0 ? 0 ? ? ?
    #   0 1 ? 0 ? ? ?
    #   0 0 0 1 ? ? ?
    #   0 0 0 0 0 0 0
    
    # 行標準形の作り方
    #  1. 最大値を見つける (=a1とする)
    #  2. a1において一番左にある1がn1列目だとすると、他の行でn1列目が1になっていたら、a1とXORする
    #  3. a1以外の最大値を見つける (=a2とする)
    #  4. a2において一番左にある1がn2列目だとすると、他の行でn2列目が1になっていたら、a2とXORする
    #     (a1も、n2列目が1になっている場合はa2とXORする)
    #  5. a1, a2以外の最大値を見つける (=a3とする)
    #  6. a3において一番左にある1がn3列目だとすると、他の行でn3列目が1になっていたら、a3とXORする
    #     (a1, a2も、n3列目が1になっている場合はa3とXORする)
    #  ....


    # 例: A = [12, 9, 7, 2] = [1100, 1001, 0111, 0010] の場合
    # XOR(A) = 0000, A' = A = [12, 9, 7, 2] = 
    # [1100
    #  1001
    #  0111
    #  0010]

    # 2行目 ^= 1行目
    # [1100
    #  0101
    #  0111
    #  0010]

    # 2行目と3行目を交換
    # [1100
    #  0111
    #  0101
    #  0010]

    # 3行目 ^= 2行目, 1行目^=2行目
    # [1011
    #  0111
    #  0010
    #  0010]

    # 4行目 ^= 3行目, 2行目 ^= 3行目, 1行目 ^= 3行目
    # [1001
    #  0101
    #  0010
    #  0000] = R

    # RのXOR結果がX'のXOR結果と一致する理由
    #   1. A'の要素の位置を入れ替えても、XORの最大化には影響しない。
    #   2. A'のある要素を、その要素と別の要素とのXOR結果に置き換えたときのXORの最大値が
    #      元のA'のXORの最大値と同じである (=XORの最大化には影響しない)
    #   3. RからXORを最大化するように要素を選択しようとするなら、
    #      Rの要素を全選択すればよい

    # 理由2について詳しく書く。

    # 例えば、要素数が3の集合Aがある場合、そのべき集合S(A)は以下の通りとなる。
    # A = {a1, a2, a3}
    # S(A) = {0, a1, a2, a3, a1^a2, a2^a3, a3^a1, a1^a2^a3}

    # a1 ^= a2 とし、これをb1とおく。また、この集合をBとすると、
    # B = {a1^a2, a2, a3} = {b1, a2, a3}
    # Bのべき集合S(B)は、
    # S(B) = {0, b1, a2, a3, b1^a2, a2^a3, a3^b1, b1^a2^a3}
    #      = {0, (a1^a2), a2, a3, (a1^a2)^a2, a2^a3, a3^(a1^a2), (a1^a2)^a2^a3}
    #      = {0, a1^a2, a2, a3, a1, a2^a3, a3^a1^a2, a1^a3}
    #      = S(A)
    # となり、Aのべき集合と一致する。
    # A'のべき集合の中に、XORを最大化する集合があるはずなので、
    # RからXORを最大化する集合を見つければよい。
    # また、Rについては、上位のビットから順に、そのビットが1になっている数が1個しかないように
    # 要素を変換していっているため、Rのべき集合からXORが最大のものを選びたい場合、
    # 全部選択すれば、XORしても上位のビットは全部1になるので、XORが最大化される。

    # 戦略通り、まずRを作って最後に全部XORするでも良いが、
    # 今までの最大値の場所を覚えてないといけないなど、面倒な部分があるため、
    # A'のXORの最大値の求め方を以下のように変形する。

    #  0. ans = 0とする

    #  1. 最大値を見つける (=a1とする)
    #  2. a1において一番左にある1がn1列目だとすると、n1列目が1になっている全ての行について（a1の行も含む）、
    #     a1とXORする**   -> a1の行は自身とXORをとるので0になる
    #  3. ans ^= a1とする

    #  4. 最大値を見つける (=a2とする)   <- 先ほど、a1を0にしたので、a1以外の最大値が見つかる
    #  5. a2において一番左にある1がn2列目だとすると、n2列目が1になっている全ての行について（a2の行も含む）
    #     a2とXORする**   -> a2の行は自身とXORをとるので0になる
    #  6. ans (= a1) のn2列目が1でない場合は、ans ^= a2とする
    #     -> 元の手順では、a1のn2列目が1になっている場合はa2とXORをとっていた。
    #        しかし、最終的に答えを求めるとき、全要素をXORするので、
    #        答え = (a1^a2) ^ a2 ^ ... = a1 ^ ...
    #        となり、答えからa2が消える。

    #  7. 最大値を見つける (=a3とする)   <- 先ほど、a2を0にしたので、a1, a2以外の最大値が見つかる
    #  8. a3において一番左にある1がn2列目だとすると、n3列目が1になっている全ての行について（a3の行も含む）
    #     a3とXORする**   -> a3の行は自身とXORをとるので0になる
    #  9. ans のn3列目が1でない場合は、ans ^= a3とする
    #     -> 元の手順では、a1, a2のn3列目が1になっている場合はa3とXORをとっていた。
    #        しかし、最終的に答えを求めるとき、全要素をXORするので、

    #        * a2をXORした場合: ans = a1^a2 となっているはず
    #          -> a1^a2のn3列目が1になっている場合、どちらかをa3とXORをとっているので、
    #             答え = ((a1^a2) ^ a3)^a3 ^ ... = (a1^a2) ^ ...
    #             となり、ansにa3をXORしなくて良い
    #          -> a1^a2のn3列目が0になっている場合、a1,a2の両方にa3をXORしたか、どちらにもXORしなかったか、
    #             答え = ((a1^a3) ^ (a2^a3))^a3 ^ ... もしくは  (a1^a2)^a3^ ...
    #             となり、a3が1個残るので、ans にa3をXORする必要がある。

    #        * a2をXORした場合: ans = a1 となっているはず
    #          手順6と同じ状況になるので、手順6と同様の理由で、ansのn3列目が1でなければa3をXORする

    #  ...


    # これを実装すると、以下の通りとなる
    ans = 0
    while True:
        _max = A_dash.max()                 # 最大値を見つける
        # print("max={}".format(_max))
        # 最大値が0なら、全部調べつくしたか、XOR操作によって全部0になったかのどっちか
        # どちらにしろこれ以上操作は不要なので終了
        if _max == 0:
            break
        # 最大値において一番左にある1が何列目にあるか調べる
        # (数値としては、一番左にある1が右から何列目にあるかを表している)
        most_left = int(_max).bit_length()
        # その列だけ1にした数字を作る
        b = 1 << (most_left - 1)
        # most_left列目が1になっている全ての行について、最大値とXORする
        # most_left列目が1になっているか -> その列だけ1にした数字とandをとって非ゼロかどうか
        A_dash[A_dash & b > 0] ^= _max
        # print(A_dash, b)
        # ans のmost_left列目が1でない場合は、ans ^= 最大値とする
        if ans & b == 0:
            ans ^= _max
    
    print(2 * ans + A_xor_all)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

t=0
for i in range(60):
    if check>>i &1==0:
        t+=2**i

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

A.sort(reverse=True)
base=[]
for i in range(N):
    for b in base:
        t=A[i]^b
        A[i]=min(A[i],t)
    if A[i]!=0:
        base.append(A[i])

new=0
for b in base:
    t=new^b
    new=max(new,t)

print(check+new*2)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
e=[]
sx=0
for i in l:
    sx^=i
for i in l:
    i&=(~sx)
    for j in e:
        i=min(i,i^j)
    if i:
        e.append(i)
t=0
for i in e:
    t=max(t,t^i)
print((t^sx)+t)

Submission status: Accepted

Solution code:
def get_basis(a):
    basis=[]
    for e in a:
        for b in basis:
            e = min(e, e^b)
        if e:
            basis.append(e)
    return basis
def solve():
    n=int(input())
    a=list(map(int,input().split()))
    ans=0
    for i in a:
        ans^=i
    k=~ans
    for i in range(n):
        a[i]&=k
    basis=get_basis(a)
    res=0
    for i in basis:
        res=max(res,res^i)
    print(ans+2*res)
solve()

Submission status: Accepted

Solution code:
def get_basis(a):
    basis=[]
    for e in a:
        for b in basis:
            e = min(e, e^b)
        if e:
            basis.append(e)
    return basis
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in a:
    ans^=i
k=~ans
for i in range(n):
    a[i]&=k
rank=0
basis=get_basis(a)
res=0
for i in basis:
    res=max(res,res^i)
print(ans+2*res)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in a:
    ans^=i
k=~ans
for i in range(n):
    a[i]&=k
rank=0
# 掃き出し法
for i in range(59,-1,-1):
    for j in range(rank,n):
        if a[j]>>i&1:
            break
    if j==n:
        continue
    if j>rank:
        # a[rank]のi番目のbitを1にするswapでもいい
        a[rank]^=a[j]
    for j in range(rank+1,n):
        a[j]=min(a[j],a[j]^a[rank])
    rank+=1
res=0
for i in a:
    res=max(res,res^i)
print(ans+2*res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

L = max(A).bit_length()

dp = [[] for _ in range(L+1)]
for a in A:
    b = (a|allxor)^allxor
    if b != 0:
        dp[b.bit_length()-1].append(b)

a1 = 0
for l in reversed(range(L)):
    if not dp[l]: continue
    c = dp[l].pop()
    if not a1&(1<<l):
        a1 ^= c
    for p in dp[l]:
        b = c^p
        if b != 0:
            dp[b.bit_length()-1].append(b)


ans = 2*a1 + allxor
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
cnt = 0
ans = 0
st = set()
for j in range(60)[::-1]:
  num = 0
  for i in range(n):
    if a[i]&1<<j:
      num += 1
  if num%2:
    ans += 1<<j
    for i in range(n):
      if a[i]&1<<j:
        a[i] ^= 1<<j
for j in range(60)[::-1]:
  for i in range(cnt,n):
    if a[i]&1<<j:
      for k in range(n):
        if i != k and a[k]&1<<j:
          a[k] ^= a[i]
      a[i],a[cnt] = a[cnt],a[i]
      cnt += 1
      break
tmp = 0
for i in range(n):
  tmp ^= a[i]
print(ans+tmp*2)

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:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    A=list(map(int,input().split()))
    A.sort(reverse=1)
    Xor=0
    l=[-1]*60
    for x in A:
        Xor^=x
    
    Xornot=Xor^(2**(A[0].bit_length())-1)

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

    for x in A:
        if l[x.bit_length()-1]==-1:
            l[x.bit_length()-1]=x

    for i in range(len(l)-1,-1,-1):
        if l[i]!=-1:
            for j in range(len(l)-1,i,-1):
                if l[j]!=-1 and (l[j]>>i)&1==1:
                    l[j]^=l[i]
    f=True
    while f:
        f=False
        for x in A:
            while x.bit_length()>1:
                if l[x.bit_length()-1]!=-1:
                    x^=l[x.bit_length()-1]
                    if l[x.bit_length()-1]==-1:
                        l[x.bit_length()-1]=x         
                        f=True
                        break
                else:
                    break
        
        for i in range(len(l)-1,-1,-1):
            if l[i]!=-1:
                for j in range(len(l)-1,i,-1):
                    if l[j]!=-1 and (l[j]>>i)&1==1:
                        l[j]^=l[i]

    tmp=0
    for i in range(len(l)-1,-1,-1):
        if l[i]!=-1 and (Xor>>i)&1==0:
            tmp^=l[i]
    
    ans=tmp+(Xor^tmp)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
xorsm = 0
res = 0
for x in a: xorsm ^= x
for i in range(N): a[i] &= ~xorsm
ln = max(a).bit_length()
k = 0
for i in range(ln - 1, -1, -1):
  for j in range(k, N):
    if a[j] & (1 << i):
      a[k], a[j] = a[j], a[k]
      break
  else: continue
  for j in range(N):
    if j == k: continue
    if a[j] & (1 << i): a[j] ^= a[k]
  k += 1
for i in range(k): res ^= a[i]
print(res * 2 + xorsm)

Submission status: Accepted

Solution code:
def maxSubarrayXOR(lis, n, INT_BITS = 60):
    idx = 0
    for i in range(INT_BITS-1,-1,-1):
        Midx = -1
        bit_i = 1 << i
        for j in range(idx, n):
            if lis[j] & bit_i:
                Midx = j
                break
        else: continue
        lis[Midx], lis[idx] = lis[idx], lis[Midx]
        for j in range(n):
            if j != idx and lis[j] & bit_i:
                lis[j] ^= lis[idx]
        idx += 1
    res = 0
    for x in lis: res ^= x
    return res

n = int(input())
a = list(map(int, input().split()))
t = 0
for x in a: t ^= x
b = [x^(x&t) for x in a]
print(t + maxSubarrayXOR(b, n)*2)

Submission status: Accepted

Solution code:
def maxSubarrayXOR(lis, n, INT_BITS = 60):
    idx = 0
    for i in range(INT_BITS-1,-1,-1):
        Mele = -1
        bit_i = 1 << i
        for j in range(idx, n):
            if lis[j] & bit_i and lis[j] > Mele:
                Midx, Mele = j, lis[j]
        if Mele < 0: continue
        lis[Midx], lis[idx] = lis[idx], lis[Midx]
        for j in range(n):
            if j != idx and lis[j] & bit_i:
                lis[j] ^= lis[idx]
        idx += 1
    res = 0
    for x in lis: res ^= x
    return res

n = int(input())
a = list(map(int, input().split()))
t = 0
for x in a: t ^= x
b = [x^(x&t) for x in a]
print(t + maxSubarrayXOR(b, n)*2)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    cnt = [0] * 61
    for a in A:
        for j in range(61):
            if a >> j & 1:
                cnt[j] += 1
    ans = 0
    for j in range(61):
        if cnt[j] & 1:
           ans += 1<<j
    mask = ((1<<61) - 1) ^ ans
    for i in range(N):
        A[i] &= mask

    rnk = 0
    for j in range(60, -1, -1):
        for i in range(rnk, N):
            if A[i] >> j & 1:
                A[rnk], A[i] = A[i], A[rnk]
                a = A[rnk]
                for ii in range(N):
                    if ii == rnk:
                        continue
                    if A[ii] >> j & 1:
                        A[ii] ^= a
                rnk += 1
                break
    ans2 = 0
    for i in range(rnk):
        ans2 ^= A[i]
    print(ans + ans2 * 2)


if __name__ == '__main__':
    main()