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:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = input()
    if s == "Sunny":
        print("Cloudy")
    elif s == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")
    return

#B
def B():
    s = S()
    for i in range(len(s)):
        if i%2:
            if s[i] not in ["L","U","D"]:
                print("No")
                return
        else:
            if s[i] not in ["R","U","D"]:
                print("No")
                return
    print("Yes")
    return

#C
def C():
    n,k,q = LI()
    a = IR(q)
    f = [k-q]*(n)
    for i in range(q):
        ai = a[i]-1
        f[ai] += 1
    for i in f:
        if i <= 0:
            print("No")
        else:
            print("Yes")
    return

#D
def D():
    n,m = LI()
    a = LI()
    q = []
    for i in range(n):
        heappush(q,-a[i])
    for i in range(m):
        x = heappop(q)
        x *= -1
        x >>= 1
        heappush(q,-x)
    print(-sum(q))
    return

#E
def E():
    n = I()
    s = S()
    l = 0
    r = n
    M = 10**64+1
    b = 26
    alp = list("abcdefghijklmnopqrstuvwxyz")
    f = {}
    for i in alp:
        f[i] = ord(i)-ord("a")
    pb = [pow(b,i,M) for i in range(n+1)]
    while r-l > 1:
        m = (l+r)>>1
        d = defaultdict(lambda : float("inf"))
        hash = 0
        for i in s[:m]:
            hash *= b
            hash += f[i]
            hash %= M
        d[hash] = 0
        t = pb[m]
        for i in range(n-m):
            si = s[i]
            hash *= b
            hash -= t*f[si]
            hash += f[s[i+m]]
            hash %= M
            if d[hash]+m <= i+1:
                l = m
                break
            if i+1 < d[hash]:
                d[hash] = i+1
        else:
            r = m
    print(l)
    return

#F
def F():
    """
    A := 赤く塗ったもののxor
    B := 青く塗ったもののxor
    S := 全体のxor

    <問題> A^Bの最大化

    A^B = S、およびA+B = A^B+(A&B)*2より
    A+B = S+(A&B)*2、Sは定数であるため、A&Bを最大化すればよい

    ここで、Sのiビット目がたっているときどのように分けてもA&Bは0となるため
    Ajからiビット目をすべて取り払う。これにより、どのような場合も全体のxorは0となり、
    常にA=Bが成り立つ。
    よってAの最大化を考えればよい。

    AはAjのxorの線形結合により生成される集合の要素である。
    ゆえにAjのxorの線形結合で作られる数のうち最大のものを解とすることができる。
    これは上位ビットから優先的にとるようにすれば生成が可能である。
    あとは基本行変形をおこない、解を求めやすい形にして階数の分だけ大きい順にAjをとれば解となる。
    
    """
    n = I()
    m = 60
    b = [1<<i for i in range(m)]
    a = LI()
    s = 0
    for i in a:
        s ^= i
    for i in range(m):
        if s&b[i]:
            for j in range(n):
                if a[j]&b[i]:
                    a[j] -= b[i]
    k = 0
    for j in range(m):
        bj = b[-j-1]
        for i in range(k,n):
            if a[i]&bj:
                break
        else:
            continue
        a[i],a[k] = a[k],a[i]
        for i in range(n):
            if i == k:
                continue
            if a[i]&bj:
                a[i] ^= a[k]

        k += 1
        if k == n:
            break
    ans = 0
    for i in range(k):
        ans ^= a[i]

    print(s+2*ans)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = input()
    if s == "Sunny":
        print("Cloudy")
    elif s == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")
    return

#B
def B():
    s = S()
    for i in range(len(s)):
        if i%2:
            if s[i] not in ["L","U","D"]:
                print("No")
                return
        else:
            if s[i] not in ["R","U","D"]:
                print("No")
                return
    print("Yes")
    return

#C
def C():
    n,k,q = LI()
    a = IR(q)
    f = [k-q]*(n)
    for i in range(q):
        ai = a[i]-1
        f[ai] += 1
    for i in f:
        if i <= 0:
            print("No")
        else:
            print("Yes")
    return

#D
def D():
    n,m = LI()
    a = LI()
    q = []
    for i in range(n):
        heappush(q,-a[i])
    for i in range(m):
        x = heappop(q)
        x *= -1
        x >>= 1
        heappush(q,-x)
    print(-sum(q))
    return

#E
def E():
    n = I()
    s = S()
    l = 0
    r = n
    M = 10**64+1
    b = 26
    alp = list("abcdefghijklmnopqrstuvwxyz")
    f = {}
    for i in alp:
        f[i] = ord(i)-ord("a")
    pb = [pow(b,i,M) for i in range(n+1)]
    while r-l > 1:
        m = (l+r)>>1
        d = defaultdict(lambda : float("inf"))
        hash = 0
        for i in s[:m]:
            hash *= b
            hash += f[i]
            hash %= M
        d[hash] = 0
        t = pb[m]
        for i in range(n-m):
            si = s[i]
            hash *= b
            hash -= t*f[si]
            hash += f[s[i+m]]
            hash %= M
            if d[hash]+m <= i+1:
                l = m
                break
            if i+1 < d[hash]:
                d[hash] = i+1
        else:
            r = m
    print(l)
    return

#F
def F():
    n = I()
    m = 60
    b = [1<<i for i in range(m)]
    a = LI()
    s = 0
    for i in a:
        s ^= i
    for i in range(m):
        if s&b[i]:
            for j in range(n):
                if a[j]&b[i]:
                    a[j] -= b[i]
    k = 0
    for j in range(m):
        bj = b[-j-1]
        for i in range(k,n):
            if a[i]&bj:
                break
        else:
            continue
        a[i],a[k] = a[k],a[i]
        for i in range(n):
            if i == k:
                continue
            if a[i]&bj:
                a[i] ^= a[k]

        k += 1
        if k == n:
            break
    ans = 0
    for i in range(k):
        ans ^= a[i]
    print(s+2*ans)
    return

#Solve
if __name__ == "__main__":
    F()

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:
def xor_gauss_jordan(A):
    """掃き出し法でジョルダン標準形を求める"""
    cnt_row = len(A)
    cnt_col = len(bin(max(A))[2::])

    rank = 0
    for col in range(cnt_col):
        # ピボットを探す
        pivot = -1
        for row in range(rank, cnt_row):
            if A[row] & 2**(cnt_col - col - 1):
                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] & 2**(cnt_col - col - 1):
                A[row] ^= A[rank]
        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::]
len_max_a = len(max_a)

# 全てのxorを計算
# xor_sumが1のビットは興味深くない
# 興味深くないビットについては予めansに答えを足して、ビットを0にしておく
ans = 0
xor_sum = 0
for i in range(n):
    xor_sum ^= a[i]
for i in range(len_max_a):
    mask = 2**i
    tmp = mask & xor_sum
    if tmp:
        ans += tmp
        for i in range(n):
            a[i] -= tmp & a[i]

# ジョルダン標準形
a = xor_gauss_jordan(a)

tmp = 0
for i in range(n):
    tmp ^= a[i]
print(ans + 2*tmp)

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())
aaa = np.fromiter(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(2 * ans + all_x)

Submission status: Accepted

Solution code:
import numpy as np

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

all_x = np.bitwise_xor.reduce(aaa)
mask = ~all_x
bbb = aaa & mask

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

print(2 * ans + all_x)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    s = 0
    # s=総xorを求める
    for a in aa:
        s ^= a
    # print(format(s, "b"))

    # sで1がたっている桁はaの選び方で影響を受けないので、aのその桁を0にする
    for i in range(n):
        # print(format(aa[i], "b"), end=" ")
        aa[i] &= ~s
        # print(format(aa[i], "b"))

    # 掃き出し法
    rnk = 0  # ランク
    for k in range(60, -1, -1):
        # k桁目に1がたっているaを探す(kは0-indexed)
        mask = 1 << k
        for i in range(rnk, n):
            if mask & aa[i]:
                aa[i], aa[rnk] = aa[rnk], aa[i]
                break
        else:
            continue
        # 見つかったa以外のk桁目をすべて0にするため、k桁目が1のaに、見つかったaをxorする
        for i in range(n):
            if i == rnk: continue
            if aa[i] & mask:
                aa[i] ^= aa[rnk]
        rnk += 1

    # できるだけ上位に1が来るよう、aを選んでいく
    red = 0
    for i in range(rnk):
        red ^= aa[i]
    blue = s ^ red
    # red+blue=(red xor blue)+2*(red & blue)
    print(s + 2 * (red & blue))

main()

Submission status: Accepted

Solution code:
from functools import reduce

MAX_DIGIT = 60

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

xorsum = reduce(lambda x, y: x ^ y, A)

A = [xor & ~xorsum for xor in A]

rank = 0
for digit in range(59, -1, -1):
    if (xorsum >> (MAX_DIGIT - digit - 1)) & 1 == 1:
        continue

    if rank >= N:
        break
    for j in range(rank, N):
        if A[j] & (1 << digit):
            break

    if j == N:
        continue

    if j > rank:
        A[rank] ^= A[j]

    for j in range(rank + 1, N):
        A[j] = min(A[j], A[j] ^ A[rank])

    rank += 1

x = 0
for i in range(N):
    x = max(x, x ^ A[i])

print(x * 2 + xorsum)

Submission status: Accepted

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))

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

N = I()
A = III()

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

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

max_digit = len(format(max(A), 'b'))
rank = 0
for col in range(max_digit)[::-1]:
    pivot = -1
    for row in range(rank,N):
        if A[row]>>col & 1:
            pivot = row
            break
    if pivot == -1: 
        continue
    A[pivot],A[rank] = A[rank],A[pivot]
    for row in range(rank+1,N):
        if A[row]>>col & 1:
            A[row] ^= A[rank]
    rank += 1

val = 0
for i in range(N):
    val = max(val,val^A[i])

print(2*val + xor)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

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

    idx = 0
    for i in range(59, -1, -1):
        if x >> i & 1 == 0:
            for j, a in enumerate(A[idx:], idx):
                if a >> i & 1:
                    break
            else:
                continue
            A[idx], A[j] = A[j], A[idx]
            for j in range(N):
                if j != idx and A[j] >> i & 1:
                    A[j] ^= a
            idx += 1

    # for a in A:
    #    print(bin(a))

    s = 0
    for a in A:
        s ^= a
    # print(f"s={bin(s)}")

    for i in range(60):
        if x >> i & 1 == 1 and s >> i & 1:
            s ^= 1 << i

    # print(x, s)
    print(x + (s << 1))

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = np.array(input().split(),dtype=np.int64)

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

red = np.bitwise_xor.reduce(A)
blue = red^xor
answer = red + blue
print(answer)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
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()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    xor=0
    for a in A: xor^=a
    # xorのうち、bitが立っていない部分だけでスクリーニング
    for i in range(n): A[i]&=(~xor)
    # このAに対してsweeping
    r=0 # Aのrank
    for d in reversed(range(61)): # digit
        for i in range(r,n):
            if A[i]&(1<<d): # 候補のiをfixする
                for j in range(i+1,n): # sweep
                    if j==i: continue # 自分自身は掃き出さない
                    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()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    xor=0
    for a in A: xor^=a
    # xorのうち、bitが立っていない部分だけでスクリーニング
    for i in range(n): A[i]&=(~xor)
    # このAに対してsweeping
    r=0 # Aのrank
    for d in reversed(range(61)): # digit
        for i in range(r,n):
            if A[i]&(1<<d): # 候補のiをfixする
                for j in range(n): # sweep
                    if j==i: continue # 自分自身は掃き出さない
                    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()

Submission status: Accepted

Solution code:
# copyright by cs_tree

class xorbasis:
    sz = 60
    table = [0] * sz

    def __init__(self):
        sz = self.sz
        for i in xrange(sz):
            self.table[i] = 0

    def add(self, x):
        sz = self.sz
        table = self.table
        
        for i in xrange(sz - 1, -1, -1):
            if x == 0: break
            
            if table[i] == 0: table[i] = x
            x = min(x, x ^ table[i])

    def maxi(self, s = 0):
        sz = self.sz
        table = self.table
        
        for i in xrange(sz - 1, -1, -1): s = max(s, s ^ table[i])

        return s

n = input()
a = map(int, raw_input().strip().split())

bits = [0] * 60

for i in xrange(n):
    for j in xrange(60):
        if (a[i] & (1 << j)): bits[j] += 1

ans = 0
for j in xrange(60):
    if (bits[j] & 1):
        xj = (1 << j)
        ans += xj
        for i in xrange(n):
            if (a[i] & xj): a[i] ^= xj

mat = xorbasis()

for i in xrange(n): mat.add(a[i])

x = mat.maxi()
ans += (2 * x)

print ans

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
x = 0
# for a in A:
#     print(bin(a))
# print()
for a in A:
    x ^= a
idx = 0
for i in range(59, -1, -1):
    if x>>i & 1 == 0:
        for j, a in enumerate(A[idx:], idx):
            if a>>i & 1:
                break
        else:
            continue
        A[idx], A[j] = A[j], A[idx]
        for j in range(N):
            if j != idx and A[j] >> i & 1:
                A[j] ^= a
        idx += 1
s = 0
#for a in A:
#    print(bin(a))
for a in A:
    s ^= a
#print(f"s={bin(s)}")
for i in range(60):
    if x>>i & 1 == 1 and s>>i & 1:
        s ^= 1<<i
#print(x, s)
print(x + (s<<1))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n = int(input())
a = [int(i) for i in readline().split()]

from functools import reduce
from operator import xor

NMAX = 62
omask = reduce(xor,a)
emask = (1<<NMAX)-1
emask ^= omask

for i in range(n):
    a[i] &= emask

k = 0
for i in range(NMAX,-1,-1):
    for j in range(k,n):
        if a[j] & (1<<i):
            if j != k: a[j], a[k] = a[k], a[j]
            for l in range(n):
                if l != k and a[l] & (1<<i): a[l] ^= a[k]
            k += 1
            break


print(omask + 2*reduce(xor,a))

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:
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:
rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())

def maxxorsum(A):
    N = len(A)
    low = 0
    for i in xrange(59, -1, -1):
        mi = low
        m = -(1 << 60)
        for j in range(low, N):
            if A[j] & (1 << i) and A[j] > m:
                mi = j
                m = A[j]
        if m == -(1 << 60):
            continue

        A[low], A[mi] = A[mi], A[low]
        mi = low
        for j in xrange(N):
            if j != mi and A[j] & (1 << i):
                A[j] ^= A[mi]
        low += 1

    ans = 0
    for x in A: ans ^= x
    return ans

def solve(N, A):
    base = 0
    for x in A:
        base ^= x

    baseneg = ~base
    for i, x in enumerate(A):
        A[i] &= baseneg
    return 2 * maxxorsum(A) + base

print solve(rri(), rrm())

Submission status: Accepted

Solution code:
# Python program to find  
# maximum XOR subset 
  
# Number of bits to  
# represent int 
INT_BITS=61
   
# 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 = -2147483648
        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 ==-2147483648): 
            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[j] ^ set[maxInd] 
          
   
        # Increment index of 
        # chosen elements 
        index=index + 1
      
   
    # Final result is  
    # XOR of all elements 
    res = 0
    for i in range(n): 
        res =res ^ set[i] 
    return res 
  
  
# This code is contributed 
# by Anant Agarwal. 


# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
#n,k = [int(i) for i in readline().split()]

n = int(input())
a = [int(i) for i in readline().split()]

res = [0]*60
for i in a:
    b = bin(i)[:1:-1]
#    print(b)
    for j,c in enumerate(b):
        if c == "1": res[j] += 1

omask = 0
emask = 0
for i,c in enumerate(res):
    if c%2: omask |= 1<<i
    elif c: emask |= 1<<i

#print(bin(omask)[2:])
#print(bin(emask)[2:])
for i in range(n):
    a[i] &= emask

res = maxSubarrayXOR(a, n)
#print(bin(res)[2:]) 


print(omask + res*2)

Submission status: Runtime Error

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]*A[0].bit_length()
    for x in A:
        Xor^=x
        if l[x.bit_length()-1]==-1:
            l[x.bit_length()-1]=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: Runtime Error

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    A = tuple(map(int, args[1].split()))

    ret = 0

    xor = [0]*(2**n)
    xor[1] = A[0]

    for i in range(1, n):
        for j in range(2**i):
            xor[2**i+j] = A[i] ^ xor[j]

    for i in range(1, 2**(n-1)):
        ret = max(ret, xor[i] + xor[-1-i])

    return str(ret)


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

Submission status: Runtime Error

Solution code:
import numpy as np
from numpy.fft import fft, ifft
from bisect import bisect_left
import sys
Max = 10**6
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = np.zeros(Max+1)
D = np.zeros(Max+1)
for a in A:
    C[a] +=1
for b in B:
    D[b]+=1
L = 2**8
res = ifft(fft(C, L)*fft(D, L))
res = np.where(res>1.5)
if res[0].size == 0:
    print(-1)
    sys.exit()
res = res[0][-1]
B.sort()
ans  = []
for i, a in enumerate(A):
    j = bisect_left(B, res-a)
    b = B[j]
    if b == res-a:
        ans.append(i)
        ans.append(j)
    if len(ans) == 4:
        break
if len(ans) < 4:
    print(liahbcon)
print(*ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from numpy.fft import rfft, irfft
from bisect import bisect_left
import sys
Max = 10**6
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = np.zeros(Max+1)
D = np.zeros(Max+1)
for a in A:
    C[a] +=1
for b in B:
    D[b]+=1
L = 2**8
res = irfft(rfft(C, L)*rfft(D, L))
res = np.where(res>1.4)
if res[0].size == 0:
    print(ahfkgashg)
    sys.exit()
res = res[0][-1]
B.sort()
ans  = []
for i, a in enumerate(A):
    j = bisect_left(B, res-a)
    b = B[j]
    if b == res-a:
        ans.append(i)
        ans.append(j)
    if len(ans) == 4:
        break
if len(ans) < 4:
    print(liahbcon)
print(*ans)

Submission status: Runtime Error

Solution code:

def f(arr) :
  sort(arr)
  reverse(arr)
  
  left = 0
  right = 0
  
  for a in arr :
    put_left = left^a + right
    put_right = left + right^a
    if put_left > put_right:
      left = left^a
    else :
      right = right^a
  
  return left + right

input()
print(f([int(x) for x in input().split(' ')]))

Submission status: Runtime Error

Solution code:
import sys
N=[]
for l in sys.stdin:
  N.append(int(l))

for i in N:
  print(i)
  j=0
  ans=0
  while j<600:
    ans+=j**2
    j+=i
  print(ans)

Submission status: Runtime Error

Solution code:
ist(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

A = [a for a in A if a != 0]
heapq.heapify(A)
b = []

if A:
    M = -heapq.heappop(A)
    while A:
        m = -heapq.heappop(A)
        if len(bin(M)) == len(bin(m)):
            m ^= M
            if m != 0:
                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: Runtime Error

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

A = [a for a in A if a != 0]
heapq.heapify(A)
b = []

M = -heapq.heappop(A)
while A:
    m = -heapq.heappop(A)
    if len(bin(M)) == len(bin(m)):
        m ^= M
        if m != 0:
            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: Runtime Error

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]*60

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)