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: 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]
            print(A[i],A[useind])
            
ANS=0
for a in A:
    ANS^=a

print(2*ANS+XOR)

Submission status: Runtime Error

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.abc 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: Runtime Error

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):
    M = max(A)
    for i in range(len(A)):
        if len(bin(M))==len(bin(A[i])):
            A[i] ^= 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:
from numpy import *
N=int(input())
A=array(input().split(),int64)
f=bitwise_xor.reduce
X=f(A)
A=hstack(([1<<i for i in range(60)if X>>i],A))
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: Runtime Error

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 (a >> i) & 1 == 0 and i >= 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: Runtime Error

Solution code:
import math

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

X = []
Y = []

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

def honya(n, L, X, Y):
  if len(L) >= 2:
    X.append(L[0])
    Y.append(L[1:])
    return True
  cnt = 0
  for i in Y:
    if (i >> (n - 1)) & 1:
      cnt += 1
  if cnt % 2 == 1:
    X.append(L)
    return True


A.sort(reverse = True)

M = nasu(A[0])

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

cnt = 0
ans = 0
X = []
Y = []
for i in range(M, 0, -1):
  L = []
  while nasu(A[cnt]) == i:
    L.append(A[cnt])
    cnt += 1
    if cnt == N:
      break
  else:
    if D[i - 1] % 2 == 1:
      X.append(L)
      ans += pow(2, i - 1)
    else:
      if honya(i, L, X, Y):
        ans += pow(2, M - 1) * 2
    continue
  break
print(ans)

Submission status: Runtime Error

Solution code:
import itertools

def list_difference(list1, list2):
    result = list1.copy()
    for value in list2:
        if value in result:
            result.remove(value)
    return result
N = int(input())
A = list(map(int, input().split()))

ans_max = 0
for i in range(int(N / 2) + 1):
  red = list(itertools.combinations(A,i))

  for j in range(len(red)):
    tmp_red = list(red[j])
    ans_red = 0
    if j != 0:
      ans_red = red[j][0]
      for k in range(1, len(red[j])):
        ans_red = ans_red ^ tmp_red[j][k]   

    blue = list_difference(A, list(red[j]))
    #print( blue)
    ans_blue = blue[0]
    for k in range(1, len(blue)):
      ans_blue = ans_blue ^ blue[k]
    if ans_blue + ans_red > ans_max:
      ans_max = ans_blue + ans_red
print(ans_max)

Submission status: Runtime Error

Solution code:
n = int(input())
tarr = list(map(int,input().split()))
tarr.sort()
tarr.reverse()
arr = ["" for i in range(n)]
red = []
blue = []


def calc_ans(red,blue):
    l = red[0]
    for i in range(1,len(red)):
        l = l^red[i]
    r = blue[0]
    for i in range(1,len(blue)):
        r = r^blue[i]
    return l+r


for i in range(n):
    arr[i] = format(tarr[i],"b").zfill(60)

ind = 0
for i in range(60):
    if ind > n-1:
        break
    num = 0
    e_place = 0
    flag = False
    for j in range(ind,n):
        if arr[j][i] == '1':
            num += 1
            e_place = j
            flag = True
    if flag:
        if num %2 == 1:
            for j in range(ind,e_place+1):
                red.append(tarr[j])
            ind = e_place+1
        else:
            for j in range(ind+1,e_place+1):
                red.append(tarr[j])
            blue.append(tarr[ind])
            ind = e_place+1


# print(blue)
# print(red)

print(calc_ans(red,blue))

Submission status: Runtime Error

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]

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

Submission status: Runtime Error

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

"""
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]

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