Problem:
 Score : 400 points    Problem Statement You are given N non-negative integers A_1, A_2, ..., A_N and another non-negative integer K .  For a integer X between 0 and K (inclusive), let f(X) = (X XOR A_1)  +  (X XOR A_2)  +  ...  +  (X XOR A_N) .  Here, for non-negative integers a and b , a XOR b denotes the bitwise exclusive OR of a and b .  Find the maximum value of f .   What is XOR?  The bitwise exclusive OR of a and b , X , is defined as follows:   When X is written in base two, the digit in the 2^k 's place ( k \geq 0 ) is 1 if, when written in base two, exactly one of A and B has 1 in the 2^k 's place, and 0 otherwise.   For example, 3 XOR 5 = 6 . (When written in base two: 011 XOR 101 = 110 .)

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

keta=len(bin(max(K,max(A)))[2:])

cnt1=[0]*keta
cnt0=[0]*keta

for i in range(len(A)):
  for j in range(keta):
    if (A[i]>>j)&1:
      cnt1[keta-1-j]+=1
    else:
      cnt0[keta-1-j]+=1

Ks=bin(K)[2:].zfill(keta)
dp=[[[0 for i in range(2)] for j in range(2)] for k in range(len(Ks))]
def calc(di,v):
  unit=2**(keta-1-di)
  if v==0:
    return cnt1[di]*unit
  else:
    return cnt0[di]*unit

x0=int(Ks[0])
dp[0][0][0]=(0 if x0==1 else calc(0,0))
dp[0][0][1]=(0 if x0==0 else calc(0,1))
dp[0][1][0]=(0 if x0==0 else calc(0,0))
dp[0][1][1]=0

for i in range(1,len(dp)):
  x=int(Ks[i])
  if x==0:
    dp[i][0][0]=dp[i-1][0][0]+dp[i-1][0][1]+calc(i,0)
    dp[i][0][1]=0
  else:
    dp[i][0][0]=0
    dp[i][0][1]=dp[i-1][0][0]+dp[i-1][0][1]+calc(i,1)
  dp[i][1][0]=max(dp[i-1][0][0]*(x==1),dp[i-1][0][1]*(x==1),dp[i-1][1][0],dp[i-1][1][1])+calc(i,0)
  dp[i][1][1]=max(dp[i-1][1][0],dp[i-1][1][1])+calc(i,1)

ans=0
for i in range(2):
  for j in range(2):
    if ans<dp[len(dp)-1][i][j]:
      ans=dp[len(dp)-1][i][j]
print(ans)

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

keta=len(bin(max(K,max(A)))[2:])


cnt1=[0]*keta
cnt0=[0]*keta

for i in range(len(A)):
  for j in range(keta):
    if (A[i]>>j)&1:
      cnt1[keta-1-j]+=1
    else:
      cnt0[keta-1-j]+=1



Ks=bin(K)[2:].zfill(keta)
dp=[[[0 for i in range(2)] for j in range(2)] for k in range(len(Ks))]

def calc(di,v):
  unit=2**(keta-1-di)
  if v==0:
    return cnt1[di]*unit
  else:
    return cnt0[di]*unit
    
x0=int(Ks[0])
dp[0][0][0]=(0 if x0==1 else calc(0,0))
dp[0][0][1]=(0 if x0==0 else calc(0,1))
dp[0][1][0]=(0 if x0==0 else calc(0,0))
dp[0][1][1]=0

for i in range(1,len(dp)):
  x=int(Ks[i])
  if x==0:
    dp[i][0][0]=dp[i-1][0][0]+dp[i-1][0][1]+calc(i,0)
    dp[i][0][1]=0
  else:
    dp[i][0][0]=0
    dp[i][0][1]=dp[i-1][0][0]+dp[i-1][0][1]+calc(i,1)
  dp[i][1][0]=max(dp[i-1][0][0]*(x==1),dp[i-1][0][1]*(x==1),dp[i-1][1][0],dp[i-1][1][1])+calc(i,0)
  dp[i][1][1]=max(dp[i-1][1][0],dp[i-1][1][1])+calc(i,1)

ans=0
for i in range(2):
  for j in range(2):
    if ans<dp[len(dp)-1][i][j]:
      ans=dp[len(dp)-1][i][j]

print(ans)

Solution (Python):
import os
import sys

import numpy as np

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

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


N, K = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))

A = np.array(A, dtype=int)
if K == 0:
    print(A.sum())
    exit()












DIGIT = (10**12).bit_length() + 1



dp = np.zeros((DIGIT, 2), dtype=int)
dp[0][1] = 0
dp[0][0] = -IINF

for d in range(1, DIGIT):
    mask = 1 << (DIGIT - d - 1)
    cnt0 = np.count_nonzero(A & mask)
    cnt1 = N - cnt0
    s0 = mask * cnt0
    s1 = mask * cnt1

    dp[d][0] = dp[d - 1][0] + max(s0, s1)
    if K & mask:
        
        dp[d][1] = max(dp[d][1], dp[d - 1][1] + s1)
        dp[d][0] = max(dp[d][0], dp[d - 1][1] + s0)
    else:
        dp[d][1] = max(dp[d][1], dp[d - 1][1] + s0)
print(dp.max())

Solution (Python):
def p_d():
    n, k = map(int, input().split())
    *A, = map(int, input().split())
    size = (len(bin(max(A + [k]))) - 2)
    bits = [0] * size
    for a in A:
        for i in range(len(bin(a)) - 2):
            bits[i] += a >> i & 1

    now = 0
    ans = 0
    for i, bit_count in enumerate(reversed(bits)):
        b = 1 << size - i - 1
        if k < now | b or n - bit_count <= bit_count:
            ans += bit_count * b
            continue
        now |= b
        ans += (n - bit_count) * b

    print(ans)


if __name__ == '__main__':
    p_d()

Solution (Python):
import math
N,K = map(int,input().split())
A = list(map(int,input().split()))
a1 = max(A)
n = int(math.log2(max(a1,K)))+1
B = [0 for _ in range(n)]
for i in range(N):
    a = bin(A[i])[2:]
    for j in range(len(a)):
        if a[len(a)-1-j]=="1":
            B[j] += 1
x = bin(K)[2:]
y = ""
flag = 0
for i in range(len(x)):
    if flag==0:
        if x[i]=="0":
            y += x[i]
        else:
            if B[len(x)-1-i]<=N//2:
                y += x[i]
            else:
                y += "0"
                flag = 1
    else:
        if B[len(x)-1-i]<=N//2:
            y += "1"
        else:
            y += "0"
y = int(y,2)
cnt = 0
for i in range(N):
    cnt += y^A[i]
print(cnt)

Solution (Python):
import numpy as np


def solve():
    N, K, *A = map(int, open(0).read().split())
    A = np.array(A)
    
    X = 0
    for i in range(40, -1, -1):
        ones = np.sum((A >> i) & 1)
        zeros = N - ones
        if ones < zeros:
            if X + 2 ** i <= K:
                X += 2 ** i
        else:
            continue
    
    ans = np.sum(X ^ A)
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
n, k, *a = map(int, open(0).read().split())
l = k.bit_length()
pre = sum((x >> l) << l for x in a)
dp = [[0] * 2 for _ in range(l + 1)]
dp[0] = [pre, -float("inf")]
for i in range(l):
	t = 1 << l - i - 1
	s = sum(x & t for x in a)
	ms = t * n - s
	if k & t:
		dp[i + 1][0] = dp[i][0] + ms
		dp[i + 1][1] = max(dp[i][1] + max(s, ms), dp[i][0] + s)
	else:
		dp[i + 1][0] = dp[i][0] + s
		dp[i + 1][1] = dp[i][1] + max(s, ms)
print(max(dp[-1]))

Solution (Python):
import numpy as np
n, k = map(int, input().split())
a = np.array(list(map(int, input().split())))

one = np.zeros(40, dtype=int)
for i in range(40):
    one[i] = np.count_nonzero(a % 2)
    a >>= 1
zero = n-one

bk = bin(k)[2:].zfill(40)
bk = bk[::-1]
answer = 0
tmp = 0
for i in range(40 - 1, -1, -1):
    if bk[i] == "0":
        tmp += one[i] * (2 ** i)
    else:
        ans = tmp + one[i] * (2 ** i)
        for j in range(i - 1, -1, -1):
            ans += max(one[j], zero[j]) * (2 ** j)
        answer = max(answer, ans)
        tmp += zero[i] * (2 ** i)
else:
    answer = max(answer, tmp)

print(answer)

Solution (Python):
def examA():
    T, X = LI()
    ans = T/X
    print(ans)
    return

def examB():
    N = I()
    L = LI()
    ans = "Yes"
    if max(L)*2>=sum(L):
        ans = "No"
    print(ans)
    return

def examC():
    N, M = LI()
    X = LI(); X.sort()
    x = []
    for i in range(M-1):
        x.append(X[i+1]-X[i])
    x.sort()
    ans = 0
    if N>=M:
        ans = 0
    else:
        for i in range(M-N):
            ans += x[i]
    print(ans)
    return

def examD():
    N, K = LI()
    A = LI()
    d = defaultdict(int)
    maxl = len(bin(K)) -2
    if K==0:
        print(sum(A))
        exit()
    for a in A:
        for j in range(maxl):
            if a&1==1:
                d[j] +=1
            a >>=1
            if a==0:
                break

    X = 0
    d0 = defaultdict(bool)
    cur = []
    for i in range(maxl):
        c = (2**i)*(N-d[i]*2)
        cur.append(max(0,c))
    curK = [0]*(maxl+1)
    curK[maxl-1] = cur[maxl-1]
    for i in range(maxl-2, -1, -1):
        if K & (1 << i) == (1 << i):
            curK[i] += curK[i + 1] + cur[i]
        else:
            d0[i] = True
            curK[i] += curK[i + 1]
    ansC = curK[0]


    for l in range(maxl):
        if d0[l]:
            continue
        now = curK[l+1]
        for i in range(l-1, -1, -1):
            now += cur[i]
        ansC = max(ansC,now)
    ans = ansC+sum(A)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examD()

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

L = len(bin(max(max(A), K))[2:])
B = list(map(lambda x: "0"*(L-len(bin(x)[2:]))+bin(x)[2:], A))


answer = 0
for i in range(L):
  cnt = 0
  for j in range(N):
    if B[j][i] == "0":
      cnt += 1
  if cnt > N - cnt and 2**(L-i-1) <= K:
    K -= 2**(L-i-1)
    answer += 2**(L-i-1) * cnt
  else:
    K -= 0
    answer += 2**(L-i-1) * (N - cnt)
print(answer)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0] * 2 for _ in range(41)]
dp[40][0] = 0

for d in range(1, 41):
    if dp[d-1][1] == 1:
        dp[d][1] = 1

    mask = 1 << (40 - d)
    num_1 = 0
    for i in range(N):
        if A[i] & mask:
            num_1 += 1

    if num_1 >= N - num_1:      
        dp[d][0] = dp[d-1][0] + num_1 * (2 ** (40-d))
        if K & mask:
            dp[d][1] = 1
    else:                       
        if dp[d][1]:
            dp[d][0] = dp[d-1][0] + (N - num_1) * (2 ** (40 - d))
        else:
            if K & mask:
                dp[d][0] = dp[d-1][0] + (N - num_1) * (2 ** (40 - d))
            else:
                dp[d][0] = dp[d-1][0] + num_1 * (2 ** (40 - d))

print(dp[-1][0])

Solution (Python):


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

ans = 0
for d in range(40, -2, -1):
    if d != -1 and not (K & 1 << d):
        continue
    
    tmp = 0
    for e in range(40, -1, -1):
        mask = 1 << e
        num_1 = 0
        for i in range(N):
            if A[i] & mask:
                num_1 += 1
        if e > d:
            if K & mask:
                tmp += mask * (N - num_1)
            else:
                tmp += mask * num_1
        elif e == d:
            tmp += mask * num_1
        else:
            tmp += mask * max(num_1, N - num_1)
    
    ans = max(ans, tmp)

print(ans)

Solution (Python):
import math
N,K = map(int,input().split())
A = list(map(int,input().split()))
m = math.ceil(math.log2(max(max(A),K)))+1
C = []
F = []
X = 0
for j in range(m):
  cnt = 0
  for i in range(N):
    cnt += A[i]>>j & 1
  if (N-cnt) < cnt:
    F.append(0)
  else:
    F.append(1)
    X += 2**j
  C.append(N-cnt)
ans = 0
for i in range(m-1,-1,-1):
  KK = K>>i & 1
  XX = X>>i & 1
  if KK==0 and XX==1:
    X += -2**i
    F[i]=0
  elif KK==1 and XX==0:
    break
  else:
    continue
for i in range(m-1,-1,-1):
  ans += C[i]*F[i]*(2**i)+(N-C[i])*(1-F[i])*(2**i)
print(ans)

Solution (Python):
N, K = map(int, input().split())  
A = list(map(int, input().split()))
K += 1
k_bit = format(K, "b")

tmp = ""  
for i in reversed(range(len(k_bit))):  
    bit = 1 << i
    count = 0  
    for a in A:
        if a & bit:
            count += 1
    if count > N - count:
        tmp += "0"
    else:
        tmp += "1"

ans = 0  
for i in range(len(k_bit)):  
    if k_bit[i] == "0":
        continue
    x = k_bit[:i] + "0" + tmp[i+1:]
    num = int(x, 2)
    
    hoge = 0
    for a in A:
        hoge += a ^ num
    ans = max(ans, hoge)
print(ans)

Solution (Python):
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    a = list(map(int, input().rstrip('\n').split()))
    ls = [0] * 45
    for v in a:
        d = 0
        while True:
            bt = v >> d
            if bt != 0:
                ls[d] += bt & 1
                d += 1
            else:
                break
    t = 0
    for i in range(44, -1, -1):
        if n / 2 >= ls[i]:
            t += 2 ** i
            if t > k:
                t -= 2 ** i
    ans = 0
    for v in a:
        ans += v ^ t
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
n,k=map(int,input().split())
A=list(map(int,input().split()))
if k==0:
    print(sum(A))
    exit()
ans=sum(A)
for i in range(40,-1,-1):
    if 2**i > k:
        continue
    cnt=0
    for a in A:
        if 1<<i & a:
            cnt+=1
    if cnt<n-cnt:
        k-=2**i
        ans -=cnt*2**i
        ans += (n-cnt)*2**i

print(ans)

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















MAX_DIGIT = 42
dp = [[-1 for _ in range(2)] for _ in range(MAX_DIGIT+1)]
dp[MAX_DIGIT][0] = 0
for i in range(MAX_DIGIT-1,-1,-1):
  c0 = c1 = 0
  for a in A:
    if (a>>i)&1 == 1:
      c1 += 1
    else:
      c0 += 1
  if dp[i+1][1] >= 0:
    
    dp[i][1] = dp[i+1][1] + max((c1<<i),(c0<<i))
  if dp[i+1][0] >= 0:
    if (K>>i)&1 == 1:
      
      dp[i][0] = dp[i+1][0] + (c0<<i)
      
      dp[i][1] = max(dp[i][1], dp[i+1][0] + (c1<<i))
    else:
      
      dp[i][0] = dp[i+1][0] + (c1<<i)


print(max(dp[0][0],dp[0][1]))

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















MAX_DIGIT = 42
dp = [[-1 for _ in range(2)] for _ in range(MAX_DIGIT+1)]
dp[MAX_DIGIT][0] = 0
for i in range(MAX_DIGIT-1,-1,-1):
  c0 = c1 = 0
  for a in A:
    if (a>>i)&1 == 1:
      c1 += 1
    else:
      c0 += 1
  if dp[i+1][1] >= 0:
    
    dp[i][1] = max(dp[i][1], dp[i+1][1] + max((c1<<i),(c0<<i)))
  if dp[i+1][0] >= 0:
    if (K>>i)&1 == 1:
      
      dp[i][0] = dp[i+1][0] + (c0<<i)
      
      dp[i][1] = max(dp[i][1], dp[i+1][0] + (c1<<i))
    else:
      
      dp[i][0] = dp[i+1][0] + (c1<<i)


print(max(dp[0][0],dp[0][1]))

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















MAX_DIGIT = 42
dp = [[-1 for _ in range(2)] for _ in range(MAX_DIGIT+1)]
dp[MAX_DIGIT][0] = 0
for i in range(MAX_DIGIT-1,-1,-1):
  c0 = c1 = 0
  for a in A:
    if (a>>i)&1 == 1:
      c1 += 1
    else:
      c0 += 1
  if dp[i+1][1] >= 0:
    
    dp[i][1] = max(dp[i][1], dp[i+1][1] + max((c1<<i),(c0<<i)))
  if dp[i+1][0] >= 0:
    if (K>>i)&1 == 1:
      
      dp[i][0] = max(dp[i][0], dp[i+1][0] + (c0<<i))
      
      dp[i][1] = max(dp[i][1], dp[i+1][0] + (c1<<i))
    else:
      
      dp[i][0] = max(dp[i][0], dp[i+1][0] + (c1<<i))


print(max(dp[0][0],dp[0][1]))

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
x=bin(k)[2:]

ans=0
flag=True

for i in range(50):
    count=0
    for j in range(n):
        if (a[j]>>(50-i-1))&1==1:
            count+=1

    if 50-i-1>len(x)-1:
        ans+=2**(50-i-1)*count

    elif not flag:
        ans+=2**(50-i-1)*max(count, n-count)
    else:
        if 2*count>=n:
            if int(x[-(50 - i)]) == 1:
                ans+=2**(50-i-1)*count
                flag=False
            else:
                ans += 2 ** (50 - i - 1) * count
        
        else:
            if int(x[-(50-i)])==1:
                ans+=2**(50-i-1)*(n-count)
            else:
                ans+=2**(50-i-1)*count

print(ans)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
x=bin(k)[2:]

ans=0
flag=True

for i in range(50):
    count=0
    for j in range(n):
        if (a[j]>>(50-i-1))&1==1:
            count+=1

    if 50-i-1>len(x)-1:
        ans+=2**(50-i-1)*count

    elif not flag:
        ans+=2**(50-i-1)*max(count, n-count)
    else:
        if 2*count>=n:
            if int(x[-(50 - i)]) == 1:
                ans+=2**(50-i-1)*count
                flag=False
            else:
                ans += 2 ** (50 - i - 1) * count
        
        else:
            if int(x[-(50-i)])==1:
                ans+=2**(50-i-1)*(n-count)
            else:
                ans+=2**(50-i-1)*count
print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,k = inpl()
a = inpl()
a.sort()
ln = len(bin(max(k,a[-1]))) - 2 
bit = [0 for i in range(ln)]
res = 0
ans = 0
for x in a:
    for i in range(ln):
        if i: 
            (x>>1) % 2
            x = x>>1
        if x%2:
            bit[i] += 1
    
for i,j in enumerate(bit):
    if j < n/2:
        bit[i] = 1
    else:
        bit[i] = 0

for i in range(ln):
    if bit[ln-i-1]:
        c = pow(2,ln-i-1)
        if k >= c:
            res += c
            k -= c

for i in a:
    ans += i^res
print(ans)

Solution (Python):
N,K = map(int, input().split())
A = [int(a) for a in input().split()]

d = 50
L = [0]*d
for i in range(N):
    b = list(bin(A[i]))
    for j in range(2, len(b)):
        if b[j] == "1":
            L[len(b)-j-1] += 1

X0 = [0]*d
X1 = [0]*d
for i in range(d):
    X0[i] = 2**i*L[i]
    X1[i] = 2**i*(N-L[i])
    
ans = 0
    
Kb = list(bin(K))
for i in range(2, len(Kb)):
    if Kb[i] == "0":
        continue
    c = 0
    for j in range(2, len(Kb)):
        if j < i:
            if Kb[j] == "0":
                c += X0[len(Kb)-1-j]
            else:
                c += X1[len(Kb)-1-j]
        elif j == i:
            c += X0[len(Kb)-1-j]
        else:
            c += max(X0[len(Kb)-1-j], X1[len(Kb)-1-j])
    ans = max(ans, c)
    
for i in range(len(Kb)-2, d):
    ans += X0[i]
    
c = 0
for i in range(N):
    c += K^A[i]
    
ans = max(ans, c)
print(ans)

Solution (Python):
n,k=map(int,input().split())
l=list(map(int,input().split()))
a=[0]*42
for i in range(n):
    p=l[i]
    j=0
    while p>0:
        a[j]+=p%2
        p=p//2
        j+=1
ans=0
for i in range(41,-1,-1):
    if a[i]<n-a[i]:
        if k>=2**i:
            k-=2**i
            ans+=(2**i)*(n-a[i])
        else:
            ans+=(2**i)*a[i]
    else:
        ans+=(2**i)*a[i]
print(ans)

Solution (Python):
def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    MAX_DIGIT = 45
    dp = [[-1] * 2 for _ in range(MAX_DIGIT+1)]
    dp[45][0] = 0
    for d in range(MAX_DIGIT-1,-1,-1):
        mask = 1 << d
        num = 0
        for i in range(N):
            if A[i] & mask:
                num += 1
        
        zero = mask * num
        one = mask * (N - num)

        if dp[d+1][1] != -1:
            dp[d][1] = max(dp[d][1], dp[d+1][1] + max(one, zero))

        if dp[d+1][0] != -1:
            if K & mask:
                dp[d][1] = max(dp[d][1], dp[d+1][0] + zero)
                dp[d][0] = max(dp[d][0], dp[d+1][0] + one)
            else:
                dp[d][0] = max(dp[d][0], dp[d+1][0] + zero)

    print(max(dp[0][0],dp[0][1]))


if __name__ == "__main__":
    main()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
A = LIST()

M = max(A+[K]).bit_length()

bitcnt = [0] * M
for a in A:
    
    i = 0
    while (a>>i) > 0:
        bitcnt[i] += a >> i & 1
        i += 1

dp = list2d(M+1, 2, -INF)
dp[M][0] = 0
for i in range(M-1, -1, -1):
    bit = 1 << i
    for j in range(2):
        
        if j == 0:
            
            if bit & K:
                dp[i][1] = max(dp[i][1], dp[i+1][0] + bit*bitcnt[i])
            else:
                dp[i][0] = max(dp[i][0], dp[i+1][0] + bit*bitcnt[i])
            dp[i][1] = max(dp[i][1], dp[i+1][1] + bit*bitcnt[i])
        
        else:
            
            if bit & K:
                dp[i][0] = max(dp[i][0], dp[i+1][0] + bit*(N-bitcnt[i]))
            dp[i][1] = max(dp[i][1], dp[i+1][1] + bit*(N-bitcnt[i]))
print(max(dp[0][0], dp[0][1]))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
A = LIST()

M = max(A+[K]).bit_length()

bitcnt = [0] * M
for a in A:
    
    i = 0
    while (a>>i) > 0:
        bitcnt[i] += a >> i & 1
        i += 1


x = 0

for i in range(M-1, -1, -1):
    bit = 1 << i
    
    if bitcnt[i] <= N // 2 and x + bit <= K:
        x += bit

ans = 0
for a in A:
    ans += a ^ x
print(ans)

Solution (Python):
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
x=0
dp=[0]*40
for i in a:
    for j in range(40):
        if i&(1<<j):
            dp[j]+=1

for i in range(39,-1,-1):
    if x+ (1<<i) >k:
        continue
    if dp[i]<(n+1)//2:
        x+=(1<<i)





for  i in a:
    ans+=x^i
print(ans)

Solution (Python):






N, K = map(int, input().split())





A = [int(x) for x in input().split()]





ones = [0] * 40
for a in A:
    s = format(a, '040b')
    for i in range(40):
        ones[i] += int(s[i])
    





kb = format(K, '040b')
flag = False
ret = []
for i in range(40):
    if flag:
        if ones[i] >= N / 2:
            ret.append(0)
        else:
            ret.append(1)
    else:
        if kb[i] == '0':
            ret.append(0)
        else:
            if ones[i] >= N / 2:
                ret.append(0)
                flag = True
            else:
                ret.append(1)





ans = 0
for i in range(40):
    if ret[i] == 0:
        ans += 2 ** (39 - i) * ones[i]
    else:
        ans += 2 ** (39 - i) * (N - ones[i])





print(ans)

Solution (Python):
n, k = map(int, input().split())
aa = list(map(int, input().split()))

ki = 0
while True:
    if 2 ** ki >= k:
        break
    else:
        ki += 1

mask = 0
for i in range(ki, -1, -1):
    b = 1 << i
    cnt = 0
    for a in aa:
        if a & b > 0:
            cnt += 1
    if len(aa) - cnt > cnt:
        if mask | b <= k:
            mask = mask | b

ans = 0
for a in aa:
    ans += a ^ mask
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    l=[0]*(len(str(bin(K)))-2)
    for a in A:
        for i in range(len(str(bin(a)))-2):
            if len(l)<=i:
                l.append(0)
            if (a >> i) & 0b1 == 1:
                l[i]+=1
    ans=0
    for j in reversed(range(max(len(l),len(str(bin(a)))-2))):
        if (K >> j) & 0b1 == 1:
            ans+=max(l[j],N-l[j])*(2**j)
        else:
            ans+=l[j]*(2**j)
    for i in range(len(bin(K))-3,0,-1):
        if (K >> i) & 0b1 == 1:
            tmp=0
            f=False
            for j in reversed(range(max(len(l),len(str(bin(a)))-2))):
                if j==i:
                    tmp+=l[j]*(2**j)
                    f=True
                else:
                    if f==True or (K >> j) & 0b1 == 1:
                        tmp+=max(l[j],N-l[j])*(2**j)
                    else:
                        tmp+=l[j]*(2**j)
            ans=max(ans,tmp)
    print(ans)
    
            

if __name__ == '__main__':
    main()

Solution (Python):
def solve():
    n, k = map(int, input().split())
    a = tuple(map(int, input().split()))

    x = [[0] * 2 for _ in range(50)]
    
    

    for j in range(50):
        b = sum(1 for x in a if (x >> j) & 1)
        x[j][0] = b << j
        x[j][1] = (n - b) << j

    dp = [-1] * 2
    dp[False] = 0
    

    for j in reversed(range(50)):
        if (k >> j) & 1:
            
            if dp[True] == -1:
                dp[True] = dp[False] + x[j][0]
            else:
                dp[True] = max(dp[True] + max(x[j]), dp[False] + x[j][0])
            dp[False] += x[j][1]
        else:
            
            if dp[True] == -1:
                pass
            else:
                dp[True] += max(x[j])
            dp[False] += x[j][0]
    return max(dp)


print(solve())

Solution (Python):
def solve():
    n, k = map(int, input().split())
    a = tuple(map(int, input().split()))

    b = [0] * 50

    for x in a:
        for j in range(50):
            if (x >> j) & 1:
                b[j] += 1

    dp = [-1] * 2
    dp[False] = 0
    

    for j in reversed(range(50)):
        if (k >> j) & 1:
            
            if dp[True] == -1:
                dp[True] = dp[False] + (b[j] << j)
            else:
                dp[True] = max(
                    dp[True] + (max(b[j], n - b[j]) << j),
                    dp[False] + (b[j] << j)
                )
            dp[False] += (n - b[j]) << j
        else:
            
            if dp[True] == -1:
                pass
            else:
                dp[True] += max(b[j], n - b[j]) << j
            dp[False] += (b[j] << j)
    return max(dp)


print(solve())

Solution (Python):
import sys
from collections import Counter
INF = 10**18
N, K = [int(i) for i in sys.stdin.readline().split()]
len_k = len(bin(K)[2:])
A_ls = [bin(int(i))[2:] for i in sys.stdin.readline().split()]
max_len = max([len(i) for i in A_ls] + [len_k])
K = bin(K)[2:].zfill(max_len)
A_ls = [A.zfill(max_len) for A in A_ls]

memo_ls = [0 for i in range(max_len)]

memo_ls2 = [0 for i in range(max_len)]
for i in range(max_len):
    ct = Counter([A[-1-i] for A in A_ls])
    
    ans_0 = 2**i*ct["1"]
    ans_1 = 2**i*ct["0"]
    ct.clear()
    memo_ls[-1-i] = (ans_0, ans_1)
    memo_ls2[-1-i] = max(ans_0, ans_1)


memo_ls3 = [[0 for i in range(2)] for i in range(max_len + 1)]
memo_ls3[0][1] = -INF
for i, j in enumerate(K, 1):
    if j == "0":
        memo_ls3[i][0] = memo_ls3[i-1][0] + memo_ls[i-1][0]
        memo_ls3[i][1] = memo_ls3[i-1][1] + memo_ls2[i-1]
    else:
        memo_ls3[i][0] = memo_ls3[i-1][0] + memo_ls[i-1][1]
        memo_ls3[i][1] = max(memo_ls3[i-1][1] + memo_ls2[i-1], memo_ls3[i-1][0] + memo_ls[i-1][0])
res = max(memo_ls3[-1])
print(int(res))

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

length = len(bin(max(max(a), k))[2:])
n_1 = [0] * length

for i in range(n):
    abin = bin(a[i])[2:].zfill(length)
    for j in range(length):
        if abin[j] == '1':
            n_1[j] += 1

def search(i, left_w):
    if i >= length:
        return 0

    w1 = 2 ** (length - i - 1)
    w0 = 0
    v1 = (n - n_1[i]) * 2 ** (length - i - 1)
    v0 = n_1[i] * 2 ** (length - i - 1)

    if left_w >= 2 * w1:
        if v1 > v0:
            return v1 + search(i+1, left_w - w1)
        else:
            return v0 + search(i+1, left_w - w0)

    if left_w >= w1 and v1 >= v0:
        return max(v1 + search(i+1, left_w - w1), v0 + search(i+1, left_w - w0))
    else:
        return v0 + search(i+1, left_w - w0)

print(search(0, k))

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict


def getlist():
	return list(map(int, input().split()))


def main():
	N, K = getlist()
	A = getlist()
	if K == 0:
		print(sum(A))
		sys.exit()	
	dp = [0] * 41
	j = 0
	while True:
		if K % 2 == 1:
			dp[-1 - j] = 1
		K = K // 2
		if K == 0:
			break
		j += 1
	

	p1 = [0] * 41
	p0 = [N] * 41
	for i in range(N):
		a = A[i]
		j = 0
		while True:
			if a % 2 == 1:
				p1[-1 - j] += 1
			a = a // 2
			if a == 0:
				break
			j += 1
	for i in range(41):
		p0[i] -= p1[i]
	
	

	
	DP0 = [0] * 41
	DP1 = [0] * 41
	s = dp.index(1)
	DP0[0] = (2 ** 40) * p1[0]
	DP1[0] = (2 ** 40) * p1[0]
	for i in range(1, s):
		DP0[i] += DP0[i - 1] + (2 ** (40 - i)) * p1[i]
		DP1[i] += DP1[i - 1] + (2 ** (40 - i)) * p1[i]
	if s != 0:
		DP0[s] = DP0[s - 1] + (2 ** (40 - s)) * p0[s]
		DP1[s] = DP1[s - 1] + (2 ** (40 - s)) * p1[s]
	else:
		DP0[s] = (2 ** (40 - s)) * p0[s]
		DP1[s] = (2 ** (40 - s)) * p1[s]
	for i in range(s + 1, 41):
		if dp[i] == 1:
			DP0[i] = DP0[i - 1] + (2 ** (40 - i)) * p0[i]
			DP1[i] = max(DP1[i - 1] + (2 ** (40 - i)) * max(p0[i], p1[i]), DP0[i - 1] + (2 ** (40 - i)) * p1[i])
		else:
			DP0[i] = DP0[i - 1] + (2 ** (40 - i)) * p1[i]
			DP1[i] = DP1[i - 1] + (2 ** (40 - i)) * max(p0[i], p1[i])
	
	
	print(max(DP0[-1], DP1[-1]))

if __name__ == '__main__':
	main()

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
msb = 1
ret = sum(a)
acc = sum(a)
while msb <= k:
    d = sum(msb if ai & msb == 0 else -msb for ai in a)
    ret = max(d + ret, acc) if msb & k != 0 else ret
    acc = max(d + acc, acc)
    msb *= 2
print(ret)

Solution (Python):
import os, sys, re, math

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

d = math.ceil(math.log2(1e+12))
ones = [0 for _ in range(d)]

for a in A:
    s = bin(a)[::-1]
    for i in range(len(s)-2):
        if s[i] == '1':
            ones[i] += 1

X = 0
for di in range(d-1,-1,-1):
    if X + 2 ** di <= K and ones[di] <= N * 0.5:
        X += 2 ** di

ret = 0
for a in A:
    ret += X ^ a

print(ret)

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
memo = {}

def doit(k):
    if not k in memo:
        if k == 0:
            memo[k] = sum(a)
        else:
            b = 1
            while k >= b:
                b *= 2
            b = b // 2
            d = 0
            for ai in a:
                d += b if ai & b == 0 else -b
            memo[k] = max(d + doit(k - b), doit(b - 1))
    return memo[k]

print(doit(k))

Solution (Python):
n,k = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]


for i in range(len(a)):
    a[i] = '{:040b}'.format(a[i])
p = len(bin(k))-2
k = '{:040b}'.format(k)
t = True
ans = 0
for i in range(0,40):
    num_1 = 0
    num_0 = 0
    if t:
        if k[i] == '1':
            for j in range(n):
                if a[j][i] == '1':
                    num_1 += 1
                elif a[j][i] == '0':
                    num_0 += 1
            if num_0 > num_1:
                num = num_0
                ans += (2**(39-i))*num
            else:
                t = False
                num = num_1
                ans += (2**(39-i))*num
        elif k[i] == '0':
            for j in range(n):
                if a[j][i] == '1':
                    num_1 += 1
                elif a[j][i] == '0':
                    num_0 += 1
            num = num_1
            ans += (2**(39-i))*num
    else:
        for j in range(n):
            if a[j][i] == '1':
                num_1 += 1
            elif a[j][i] == '0':
                num_0 += 1
        if num_0 > num_1:
            num = num_0
            ans += (2**(39-i))*num
        else:
            num = num_1
            ans += (2**(39-i))*num
print(ans)