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):
def calc():
  n,k=map(int,input().split())
  arr=list(map(int,input().split()))
  flag=format(k,'b')[::-1]
  l=len(flag)
  xor1=0
  xor2=0
  cnt=0
  check=False
  for i in range(l-1,-1,-1):
    if check==False and flag[i]=='0':
      continue
    for j in arr:
      if j&(2**i)!=0:
        cnt+=1
    if cnt<=n//2:
      if i!=l-1:
        xor1+=2**i
      if check==True or flag[i]=='1':
        xor2+=2**i
    else:
      if flag[i]=='1':
        check=True
    cnt=0
  ans1=0
  ans2=0
  for i in arr:
    ans1+=i^xor1
    ans2+=i^xor2
  print(max(ans1,ans2))

calc()

Solution (Python):
n,k=map(int,input().split())
arr=list(map(int,input().split()))
flag=format(k,'b')[::-1]
l=len(flag)
xor1=0
cnt=0
for i in range(l-2,-1,-1):
  for j in arr:
    if j&(2**i)!=0:
      cnt+=1
  if cnt<=n//2:
    xor1+=2**i
  cnt=0
ans1=0
for i in arr:
  ans1+=i^xor1
xor2=0
cnt=0
check=False
for i in range(l-1,-1,-1):
  if check==False and flag[i]=='0':
    continue
  for j in arr:
    if j&(2**i)!=0:
      cnt+=1
  if cnt<=n//2:
    if check==True or flag[i]=='1':
      xor2+=2**i
  else:
    if flag[i]=='1':
      check=True
  cnt=0
ans2=0
for i in arr:
  ans2+=i^xor2
print(max(ans1,ans2))

Solution (Python):
N,K=map(int,input().split())
from collections import defaultdict
cnt=defaultdict(int)
for a in map(int,input().split()):
    now=a
    k=0
    while now>0:
        cnt[k]+=now%2
        now//=2
        k+=1
X=bin(K)[2:]
X=(40-len(X))*"0"+X
FREE=[0]*40
FREE[0]=max(N-cnt[0],cnt[0])*pow(2,0)
for i in range(1,40):
    FREE[i]=FREE[i-1]+max(N-cnt[i],cnt[i])*pow(2,i)
FREE.append(0)
ans=-1
now=0
for i in range(40):
    if X[i]=="0":
        now+=cnt[39-i]*pow(2,39-i)
    if X[i]=="1":
        ans=max(ans,now+cnt[39-i]*pow(2,39-i)+FREE[38-i])
        now+=(N-cnt[39-i])*pow(2,39-i)
ans=max(ans,now)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

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

max_dig = 40
K_bin = format(K,'b').zfill(max_dig)
A_bin = []
greed = [0] * max_dig
score0 = [0] * max_dig
score1 = [0] * max_dig

for i in range(N):
	A_bin.append(format(A[i], 'b').zfill(max_dig))

for i in range(max_dig):
	c_one = 0
	c_zero = 0
	for j in range(N):
		if A_bin[j][i] == '1':
			c_one += 1
		else:
			c_zero += 1
		
	if c_zero > c_one:
		greed[i] = '1'
	else:
		greed[i] = '0'
		
	score0[i] = c_one * (2 ** (max_dig - i - 1))
	score1[i] = c_zero * (2 ** (max_dig - i - 1))

greed = ''.join(greed)
ans = 0

for i in range(max_dig):
	ans_list = ''
	if K_bin[i] == '1':
		ans_list = K_bin[:i] + '0' + greed[i + 1:]
		tmp = 0
		for j in range(max_dig):
			if ans_list[j] == '1':
				tmp += score1[j]
			else:
				tmp += score0[j]
				
		if tmp > ans:
			ans = tmp
			
ans_list = K_bin
tmp = 0
for j in range(max_dig):
	if ans_list[j] == '1':
		tmp += score1[j]
	else:
		tmp += score0[j]
		
if tmp > ans:
	ans = tmp

print(ans)

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

max_len = len(format(K, 'b'))
for a in alist:
  max_len = max(max_len, len(format(a, 'b')))

bin_K_str = format(K, '0'+str(max_len)+'b')


a0list=[0]*max_len
a1list=[0]*max_len
for a in alist:
  bin_a_str = format(a,  '0'+str(max_len)+'b')
  
  for i in range(max_len):
    a_bit = bin_a_str[i]
    if a_bit == "0":
      a0list[i] += 1
    elif a_bit == "1":
      a1list[i] += 1



minor_list = ["-1"]*max_len
for i in range(max_len):
  if a0list[i] > a1list[i]:
    minor_list[i] = "1"
  else:
    minor_list[i] = "0"


equal = True
dp_str = ""
for i in range(max_len):
  if not equal:
    dp_str += minor_list[i]
  else:
    if bin_K_str[i] == "1":
      if minor_list[i] == "0":
        dp_str += "0"
        equal = False
      else:
        dp_str += "1"
    else:
      dp_str += "0"


argmax = int(dp_str,2)


fmax=0
for a in alist:
  fmax += argmax ^ a
  
print(fmax)

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

len_K=40
bin_K_str = format(K, '040b')


a0list=[0]*len_K
a1list=[0]*len_K
for a in alist:
  bin_a_str = format(a, '040b')
  
  for i in range(len_K):
    a_bit = bin_a_str[i]
    if a_bit == "0":
      a0list[i] += 1
    elif a_bit == "1":
      a1list[i] += 1



minor_list = [-1]*len_K
for i in range(len_K):
  if a0list[i] > a1list[i]:
    minor_list[i] = 1
  else:
    minor_list[i] = 0


equal = True
dp = [-1]*len_K
for i in range(len_K):
  if not equal:
    dp[i] = minor_list[i]
  else:
    if bin_K_str[i] == "1":
      if minor_list[i] == 0:
        dp[i] = 0
        equal = False
      else:
        dp[i] = 1
    else:
      dp[i] = 0


argmax = 0
pow2 = 1
for d in reversed(dp):
  if d == 1:
    argmax += pow2
  pow2 *= 2


fmax=0
for a in alist:
  fmax += argmax ^ a
  
print(fmax)

Solution (Python):
import sys
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()

N,K = na()
A = na()

bit = [0]*41
for a in A:
    for j in range(41):
        if a & (1<<j):
            bit[j]+=1
ans = 0
iam = 0
for i in range(40,-1,-1):
    
    if iam + (1<<i) > K:
        
        ans += (1<<i)*bit[i]
        continue
    if N//2 >= bit[i]:
        ans += (1<<i)*(N-bit[i])
        iam += 1<<i
    else:
        ans += (1<<i)*bit[i]
print(ans)

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

Rewards_0, Rewards_1 = [], []  
for i in range(40):
    reward_0, reward_1 = 0, 0
    for a in A:
        if a & (2 ** i):
            reward_0 += 2 ** i
        elif 2 ** i <= K:
            reward_1 += 2 ** i
    Rewards_0.append(reward_0)
    Rewards_1.append(reward_1)

dp0 = [0] * 41  
dp1 = [0] * 41  

for i in reversed(range(40)):
    if K & (2 ** i):
        dp0[i] = dp0[i + 1] + Rewards_1[i]
        dp1[i] = dp0[i + 1] + Rewards_0[i]
    else:
        dp0[i] = dp0[i + 1] + Rewards_0[i]

    if dp1[i + 1] != 0:
        dp1[i] = max(dp1[i], dp1[i + 1] + max(Rewards_0[i], Rewards_1[i]))

print(max(dp0[0], dp1[0]))

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

    
li_cnt_0 = [0]*100
li_cnt_1 = [0]*100
for times in range(100):
    for i in range(n):
        if a[i] % 2 == 1:
            li_cnt_1[times] += 1
        if a[i] % 2 == 0:
            li_cnt_0[times] += 1
        a[i] = a[i] // 2

li_cnt_0 = li_cnt_0[::-1]
li_cnt_1 = li_cnt_1[::-1]
k  = format(k, '0100b')
dp = [[0]*2 for i in range(101)]

flag = False
for i in range(len(k)):
    cnt_0 = li_cnt_0[i]
    cnt_1 = li_cnt_1[i]
    
    
    if k[i] == "0":
        dp[i+1][0] = dp[i][0] + cnt_1 * 2**(99 - i)
    else:
        dp[i+1][0] = dp[i][0] + cnt_0 * 2**(99 - i)

    
    if flag:
        if k[i] == "0":
            dp[i+1][1] = max(dp[i][1] + cnt_1 * 2**(99 - i), dp[i+1][1])
            dp[i+1][1] = max(dp[i][1] + cnt_0 * 2**(99 - i), dp[i+1][1])
        else:
            dp[i+1][1] = max(dp[i][1] + cnt_1 * 2**(99 - i), dp[i+1][1])
            dp[i+1][1] = max(dp[i][1] + cnt_0 * 2**(99 - i), dp[i+1][1])

    
    if k[i] == "0":
        pass
    else:
        flag = True
        dp[i+1][1] = max(dp[i][0] + cnt_1 * 2**(99 - i), dp[i+1][1])

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

Solution (Python):
import numpy as np
N,K = map(int,input().split())
A = np.int64(input().split())

d = [0]*40
for k in range(40):
    d[k] = np.sum(A%2**(k+1)//2**k)

dd = [0]*41
for k in range(40):
    dd[k] = dd[k-1]+max(d[k],N-d[k])*2**k

dp = [0]*(40)

for k in range(40):
    if K&2**k == 0:
        dp[k] = dp[k-1]+d[k]*2**k
    else:
        dp[k] = max(dp[k-1]+(N-d[k])*2**k,dd[k-1]+d[k]*2**k)

print(dp[-1])

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
c = [0] * 100
k = bin(K)[2:]
kl = len(bin(K)) - 2
for a in A:
    a = list(bin(a)[2:])
    a.reverse()
    for i, b in enumerate(a):
        if b == '1':
            c[i] += 1
X = ''
C = c[:kl]
C.reverse()
for ck in C:
    if ck * 2 <= N:
        if int(k[:len(X)+1]) >= int(X + '1'):
            X += '1'
        else:
            X += '0'
    else:
        X += '0'
X = '0b' + X
X = int(X, base=2)
ans = sum([X ^ a for a in A])
print(ans)

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

res = 0
for d in range(40, -2, -1):
    
    if d != -1 and (K & 1 << d) == 0:
        continue

    tmp = 0
    for e in range(40, -1, -1):
        
        
        
        mask = 1 << e
        num = 0

        
        for i in range(N):
            if A[i] & mask:
                num += 1
        if e > d:
            
            
            if K & mask:
                tmp += mask * (N - num)
            else:
                tmp += mask * num
        elif e == d:
            tmp += mask * num
        
        else:
            tmp += mask * max(num, N - num)

    res = max(res, tmp)

print(res)

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

max_len = 0
num = max(a+[k])
while num > 0:
    num //= 2
    max_len += 1

dp = [[0, 0] for _ in range(max_len)]

for i in range(0, max_len)[::-1]:
    
    one_cnt = 0
    for el in a:
        if el & (1<<i):
            one_cnt += 1
            
    
    if i == max_len-1:
        if k & (1<< i):
            dp[i][0] = one_cnt*(1<<i)
            dp[i][1] = (len(a) - one_cnt)*(1<<i) 
        else:
            dp[i][1] = one_cnt*(1<<i)
        continue
            
    
    if k & (1<<i):
        
        dp[i][1] = (len(a) - one_cnt)*(1<<i) + dp[i+1][1]
        dp[i][0] = (len(a) - one_cnt)*(1<<i) + dp[i+1][0]
        
        dp[i][0] = max(dp[i][0], one_cnt*(1<<i) +  max(dp[i+1][0], dp[i+1][1]))
    else:
        dp[i][0] = max(one_cnt, len(a) - one_cnt)*(1<<i) + dp[i+1][0]
        
        dp[i][1] = one_cnt*(1<<i) + dp[i+1][1]

print(max(dp[0]))

Solution (Python):
import numpy as np

n, k = map(int, input().split())
A = list(map(int, input().split()))
All = [[0]*41 for i in range(n)]
K = [0]*41
stopper = 0
sum_ = 0



for i in range(len(A)):
    bin_a = format(A[i],'b')
    list_a = [int(i) for i in bin_a]
    All[i] = [0]*(41-len(list_a))+ list_a
    
bin_k =   format(k,'b') 
list_k = [int(i) for i in bin_k]
K = [0]*(41-len(list_k))+list_k

b = np.cumsum(All, axis = 0)
B = b[len(b)-1]
    
for i in range(41):
    if K[i]==1 and B[i]>= (n+1)//2:
        K[i]=0
        stopper = i
        break

if stopper!=0 and stopper<=39:
    for i in range(stopper+1,41):
        if  B[i]>= (n+1)//2:
            K[i] = 0
        else:
            K[i] = 1
            
            
for i in range(41):
    if K[i]==1:
        B[i] = n-B[i]

for i in range(1,42):
    sum_ = sum_ + B[-i]*(2**(i-1))

print(sum_)

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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

mx=max(K, max(A))
bmx=format(mx, 'b')
mxlen=len(bmx)
bK=format(K, '0'+str(mxlen)+'b')


cnt1=[0]*mxlen
for i in range(N):
    ba = format(A[i], '0'+str(mxlen)+'b')
    for j, bit in enumerate(ba):
        if bit=='1':
            cnt1[j]+=1
num0=[0]*mxlen
num1=[0]*mxlen
for i in range(mxlen):
    
    num0[i]=cnt1[i]*2**(mxlen-i-1)
    num1[i]=(N-cnt1[i])*2**(mxlen-i-1)


dp=list2d(mxlen+1, 2, -1)
dp[0][0]=0
for i in range(mxlen):
    if dp[i][1]!=-1:
        
        dp[i+1][1]=max(dp[i+1][1], dp[i][1]+max(num0[i], num1[i]))
    if dp[i][0]!=-1:
        
        if bK[i]=='0':
            dp[i+1][0]=max(dp[i+1][0], dp[i][0]+num0[i])
        else:
            dp[i+1][0]=max(dp[i+1][0], dp[i][0]+num1[i])
        
        if bK[i]=='1':
            dp[i+1][1]=max(dp[i+1][1], dp[i][0]+num0[i])
print(max(dp[mxlen][0], dp[mxlen][1]))

Solution (Python):

import sys
INTMAX = 10**30

def solve(N: int, K: int, A: "List[int]"):
    K = bin(K)[2:]
    A = [bin(a)[2:] for a in A]
    ndig = max([len(a) for a in A+[K]])
    
    A = [(ndig-len(s))*"0"+s for s in A]
    K = (ndig-len(K))*"0"+K
    
    dp = [0, -INTMAX] 
    base = 2**(ndig-1)
    for k, digs in zip(K, zip(*A)):
        n1 = digs.count("1")
        n0 = len(A)-n1
        dp[1] = max([dp[0]+base*n1 if k=="1" else -INTMAX, dp[1]+base*max(n1,n0)])
        dp[0] = dp[0] + base*(n1 if k=="0" else n0)
        base //= 2
    print(max(dp))

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    K = int(next(tokens))  
    A = [ int(next(tokens)) for _ in range(N) ]  
    solve(N, K, A)

if __name__ == '__main__':
    main()

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

    if dp[d+1][1]>=0:
        dp[d][1]=max(dp[d][1],dp[d+1][1]+mask*max(num,N-num))
    if dp[d+1][0]>=0:
        if K &mask:
            dp[d][1]=max(dp[d][1],dp[d+1][0]+mask*num)
            dp[d][0]=max(dp[d][0],dp[d+1][0]+mask*(N-num))
        else:
            dp[d][0]=max(dp[d][1],dp[d+1][0]+mask*num)
print(max(dp[0][0],dp[0][1]))

Solution (Python):
import numpy as np

N, K = map(int, input().split())
MAX_DIGIT = 50
A = [int(_) for _ in input().split()]
dp = np.full((MAX_DIGIT+1, 2), -1, dtype=np.int64)
dp[0][0] = 0

for d in range(MAX_DIGIT):
    mask = 1 << (MAX_DIGIT - 1 - d)
    onenum = 0
    for i in A:
        if (i & mask) == mask:
            onenum += 1
    
    cost0 = mask * onenum
    cost1 = mask * (N - onenum)
    
    if dp[d][1] != -1:
        dp[d+1][1] = max(dp[d+1][1], dp[d][1] + max(cost0, cost1))
    
    if dp[d][0] != -1:
        if K & mask:
            dp[d+1][1] = max(dp[d+1][1], dp[d][0] + cost0)
    
    if dp[d][0] != -1:
        if K & mask:
            dp[d+1][0] = max(dp[d+1][0], dp[d][0] + cost1)
        else:
            dp[d+1][0] = max(dp[d+1][0], dp[d][0] + cost0)

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

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
res=0
for d in range(40,-2,-1):
    if(d!=-1 and K&(1<<d)==0):
        continue
    tmp=0
    for e in range(40,-1,-1):
        mask=1<<e
        num=0
        for i in range(N):
            if(mask&A[i]):
                num+=1
        
        
        
        if(e>d):
            
            if(K&mask):
                tmp+=mask*(N-num)
            
            else:
                tmp+=mask*num
        
        elif(e==d):
            tmp+=mask*num      
        
        else:
            tmp+=mask*max(num,N-num)
    
    res=max(res,tmp)
print(res)

Solution (Python):

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




def s(i):
    return sum((a >> (i - 1)) & 1 for a in A)


def g(L, b):
    m = 2**(b - 1)
    return (
        0 if b == 0 else
        g(L, b - 1) + m * s(b) if L < m else
        g(L >> 1, b - 1) + m * max(
            s(b),
            N - s(b)
        ) if L == (2**b - 1) else
        max(
            g(m - 1, b - 1) + m * s(b),
            g(L - m, b - 1) + m * (N - s(b))
        )
    )


ans = g(K, max(K, *A).bit_length())


print(ans)

Solution (Python):

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




def s(i):
    return sum((a >> (i - 1)) & 1 for a in A)


def g(L, b):
    return (
        0 if b == 0 else
        g(L, b - 1) + 2**(b - 1) * s(b) if L < 2**(b - 1) else
        g(L >> 1, b - 1) + 2**(b - 1) * max(
            s(b),
            N - s(b)
        ) if L == (2**b - 1) else
        max(
            g(2**(b - 1) - 1, b - 1) + 2**(b - 1) * s(b),
            g(L - 2**(b - 1), b - 1) + 2**(b - 1) * (N - s(b))
        )
    )


ans = g(K, max(K, *A).bit_length())


print(ans)

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

def f(X):
    return sum([X ^ a for a in A])

if K==0:
    print(f(0))
else:
    l = len(bin(K)[2:])
    a_bit = [N - 2*sum([(a>>i) & 1 for a in A]) for i in range(l)]
    k_bit = [a > 0 for a in a_bit]
    ans = f(0)
    for j in range(l+1):
        k=0
        for i,b in enumerate(k_bit[::-1],1):
            if i==j:continue
            if b and (k + (1<<(l-i)) <= K):
                k += (1<<(l-i))
        ans = max(ans,f(k))
    print(ans)

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

def f(X):
    return sum([X ^ a for a in A])

if K==0:
    print(f(0))
else:
    l = len(bin(K)[2:])
    a_bit = [N - 2*sum([(a>>i) & 1 for a in A]) for i in range(l)]
    k_bit = [a > 0 for a in a_bit]
    k = 0
    ans = f(0)
    for j in range(l+1):
        for i,b in enumerate(k_bit[::-1],1):
            if i==j:continue
            if b and (k + (1<<(l-i)) <= K):
                k += (1<<(l-i))
        ans = max(ans,f(k))
    print(ans)

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

def f(X):
    return sum([X ^ a for a in A])

if K==0:
    print(f(0))
else:
    l = len(bin(K)[2:])
    a_bit = [N - 2*sum([(a>>i) & 1 for a in A]) for i in range(l)]
    k_bit = [a > 0 for a in a_bit]
    k = 0
    ans = f(0)
    for j in range(l):
        for i,b in enumerate(k_bit[::-1],1):
            if i==j:continue
            if b and (k + (1<<(l-i)) <= K):
                k += (1<<(l-i))
        ans = max(ans,f(k))
    print(ans)

Solution (Python):

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

def f(X):
    return sum([X ^ a for a in A])

if K==0:
    print(f(0))
else:
    l = len(bin(K)[2:])
    a_bit = [N - 2*sum([(a>>i) & 1 for a in A]) for i in range(l)]
    k_bit = [a > 0 for a in a_bit]
    k = 0
    for i,b in enumerate(k_bit[::-1],1):
        if b and (k + (1<<(l-i)) <= K):
            k += (1<<(l-i))
    print(f(k))

Solution (Python):
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[("0"*40+bin(A[i])[2:])[-40:] for i in range(N)]

cnt="".join([str(int(sum([int(B[i][j]) for i in range(N)]) < (N+1)//2)) for j in range(40)])
M=("0"*40+bin(M)[2:])[-40:]

ans=[]

def dp(cur,seq):
    if cur==40:
        if seq<=M:
            ans.append(seq)
    elif seq[:cur]+cnt[cur:] <= M:
        ans.append(seq[:cur]+cnt[cur:])
    elif seq[:cur]+"0"*(40-cur) > M:
        pass
    else:
        dp(cur+1,seq[:cur]+"0"+cnt[cur+1:])
        dp(cur+1,seq[:cur]+"1"+cnt[cur+1:])
        
dp(0,cnt)
print(max([sum([a^int(i,2) for a in A]) for i in ans]))

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

X = 0
for i in range(40, -1, -1):
    if X | (1 << i) > K:
        continue
    cnt = 0
    for j in range(N):
        if A[j] & (1 << i) == 0:
            cnt += 1
    if cnt > N - cnt:
        X |= (1 << i)

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

print(ans)

Solution (Python):
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[("0"*40+bin(A[i])[2:])[-40:] for i in range(N)]

cnt="".join([str(int(sum([int(B[i][j]) for i in range(N)]) < (N+1)//2)) for j in range(40)])
M=("0"*40+bin(M)[2:])[-40:]

for i in range(40):
    if cnt > M:
        cnt=list(cnt)
        cnt[i]=str(int(cnt[i])&int(M[i]))
        cnt="".join(cnt)
    else:
        break

k=int(cnt,2)
print(sum([k^A[i] for i in range(N)]))

Solution (Python):
N, k = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
x = k
for i in range(len(bin(k)) - 1):
    if x <= k:
        tem = 0
        for a in A:
            tem += a ^ x
        ans = max(ans, tem)
    x = list(format(x, '045b'))
    c = 0
    for a in A:
        c += a >> i & 1
    if N <= 2 * c:
        x[-1 - i] = '0'
    else:
        x[-1 - i] = '1'
    x = int('0b' + ''.join(x), 0)
print(ans)

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

def to_bin_arr(a, digit):
    '''
    2進数の0,1配列に変換する
    ex) a = 6, digit = 5 -> [0,0,1,1,0]
    '''
    t = format(a, 'b').zfill(digit)
    return list(map(int, t))

def digit(a):
    '''
    2進数にしたときの桁数を求める
    '''
    return len(format(a, 'b'))


max_a = max(A)

d = max(digit(max_a), digit(K))


K_bin = to_bin_arr(K, d)
A_bin = [to_bin_arr(a, d) for a in A]



Axor0 = [0] * d
for ab in A_bin:
    for i in range(d):
        Axor0[i] += ab[i]
Axor1 = [N-x for x in Axor0]


def score_after(k):
    s = 0
    for i in range(k, d):
        s += (max(Axor0[i], Axor1[i]) << (d - 1 - i))
    return s


def f(X, free, score):
    k = len(X)

    if k == d:
        return score

    if free:
        return score + score_after(k)
    
    if K_bin[k] == 1:
        a = f(X + [0], True, score + (Axor0[k] << d - 1 - k))
        b = f(X + [1], False, score + (Axor1[k] << d - 1 - k))
        return max(a, b)
    else:
        a = f(X + [0], False, score + (Axor0[k] << d - 1 - k))
        return a

ans = f([], False, 0)
print(ans)

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


def digit2(n):
    s = 0
    while n > 0:
        n = n // 2
        s += 1
    return s
dK = digit2(max(K, max(A)))

K2 = list(map(int, list(bin(K))[2:]))
K2 = [0] * (dK - len(K2)) + K2



Axor0 = [0] * dK
for a in A:
    for i in range(dK):
        a, x = divmod(a, 2)
        Axor0[i] += x

Axor0 = Axor0[::-1]
Axor1 = [N-x for x in Axor0]


Abest = [None] * dK
for i in range(dK):
    Abest[i] = 0 if Axor0[i] >= Axor1[i] else 1



def f(X, free):
    n = len(X)

    if free or n == len(K2):
        a = X + Abest[len(X):]
        s = 0
        for i in range(len(a)):
            s = s * 2 +(Axor0[i] if a[i] == 0 else Axor1[i])
        return s
    
    if K2[n] == 1:
        a = f(X + [0], True)
        b = f(X + [1], False)
        return max(a, b)
    else:
        a = f(X + [0], False)
        return a

ans = f([], False)
print(ans)

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

X = 0
for i in range(40, -1, -1):
    if X | (1 << i) > K:
        continue
    cnt = 0
    for j in range(N):
        if A[j] & (1 << i) == 0:
            cnt += 1
    if cnt > N - cnt:
        X |= (1 << i)

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

print(ans)

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

X = 0
for i in range(42, -1, -1):
    if X | (1 << i) > K:
        continue
    cnt1, cnt0 = 0, 0
    for a in A:
        if a & (1 << i) == 0:
            cnt0 += 1
        else:
            cnt1 += 1
    if cnt0 > cnt1:
        X |= (1 << i)

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

print(ans)

Solution (Python):
import numpy as np
from sys import setrecursionlimit
setrecursionlimit(10**8)


def get_ans(k, value, index):
    
    if index < 0:
        return value
    if k < 2**index:
        return get_ans(k, value + (2**index) * count_array[index], index - 1)
    elif k >= 2**(index + 1) - 1:
        return value + sum_array[index]
    return max(
        get_ans(k, value + (2**index) * count_array[index], index - 1),
        get_ans(k - 2**index, value + (2**index) * (N - count_array[index]),
                index - 1))


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

A_array = np.array(list(map(int, input().split())))

count_array = np.zeros(40, dtype=np.int)

for A in A_array:
    array = np.array(list(map(int, bin(A)[2:].zfill(40)))[::-1])
    count_array += array
    

sum_array = np.array([], dtype=np.int64)

last_value = 0
for i in range(40):
    last_value += 2**i * max(count_array[i], N - count_array[i])
    sum_array = np.append(sum_array, last_value)


print(get_ans(K, 0, 39))

Solution (Python):

















import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations
from bisect import bisect_left, bisect_right


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")
MAX_DIGIT = 50





N, K = l_inpl()
A = l_inpl()




dp = [[-1] * 2 for _ in range(MAX_DIGIT+1)]
dp[0][0] = 0

for d in range(1, MAX_DIGIT+1):
    mask = 1<<(MAX_DIGIT - d)

    
    cnt = 0
    for i in range(N):
        if A[i] & mask:
            cnt += 1

    
    cost0 = mask * cnt
    cost1 = mask * (N - cnt)

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

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

Solution (Python):
import numpy as np
from functools import lru_cache

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

bit_cnt = [((A>>k)&1).sum() for k in range(40)]

@lru_cache(maxsize = 10**6)
def F(K,k = 39):
  
  if k == -1:
    return 0
  bit = 1<<k
  
  x = 0
  if K >= bit:
    x = ((N-bit_cnt[k])<<k) + F(K-bit,k-1)
  
  y = (bit_cnt[k]<<k) + F(min(K,bit-1),k-1)
  return max(x,y)

answer = F(K)
print(answer)

Solution (Python):
import numpy as np
from functools import lru_cache

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

bit_cnt = [((A>>k)&1).sum() for k in range(50)]

@lru_cache(maxsize = 10**6)
def F(K,k = 49):
  
  if k == -1:
    return 0
  bit = 1<<k
  
  x = 0
  if K >= bit:
    x = ((N-bit_cnt[k])<<k) + F(K-bit,k-1)
  
  y = (bit_cnt[k]<<k) + F(min(K,bit-1),k-1)
  return max(x,y)

answer = F(K)
print(answer)

Solution (Python):
def sub():
    N, K = [int(e) for e in input().split()]
    As = [int(e) for e in input().split()]

    bK = "{:b}".format(K)
    
    size_K = len(bK)
    fmt = "{:0" + str(size_K) + "b}"
    bAs = [fmt.format(a) for a in As]
    bAs = [a[-size_K:] for a in bAs]
    
    buf = []
    d = float(N) / 2.0
    flagFree = False
    for i in range(size_K):
        k = bK[i]
        if k == "0" and flagFree is False:
            buf.append("0")
            continue
        cc = [int(a[i]) for a in bAs]
        t = sum(cc)
        if t > d:
            buf.append("0")
            if k == "1":
                flagFree = True
        else:
            buf.append("1")
    xOpt = "".join(buf)
    xOpt = int(xOpt,2)

    ans = [xOpt ^ a for a in As]
    print(sum(ans))


if __name__ == "__main__":
    sub()

Solution (Python):
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
dp = [[-1 for i in range(2)] for i in range(51)]
dp[50][0] = 0
for i in range(49, -1, -1):
  mask = 1<<i
  ones = 0
  for e in a:
    if e&mask:
      ones+= 1
  for e in a:
    if dp[i+1][0]!=-1:
      if k&mask:
        dp[i][0] = max(dp[i][0], dp[i+1][0] + mask*(n-ones))
        dp[i][1] = max(dp[i][1], dp[i+1][0] + mask*ones)
      else:
        dp[i][0] = max(dp[i][0], dp[i+1][0] + mask*ones)
    if dp[i+1][1]!=-1:
      dp[i][1] = max(dp[i][1], dp[i+1][1] + mask*max(ones, n-ones))
print(max(dp[0][0], dp[0][1]))

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

l = len(bin(k)) - 2
num = []
for i in range(l):
    temp = 0
    for j in range(n):
        if ((a[j] >> i) % 2 == 0):
            temp += 1
    if (temp >= n / 2):
        num.append([1, temp])
    else:
        num.append([0, n - temp])

ind = 0
t = sum([num[i][0] * 2 ** i for i in range(l)])
for i in range(l):
    if ((k - (k >> (l - i)) * 2 ** (l - i)) >= t):
        ind = l - i
        break
    t -= num[l - i - 1][0] * 2 ** (l - i - 1)

t1 = t + ((k >> ind) << ind)
t2 = t + sum([num[i][0] * 2 ** i for i in range(ind, l - 1)])

sum1 = sum([a[i] ^ t1 for i in range(n)])
sum2 = sum([a[i] ^ t2 for i in range(n)])
    
print(sum1 if sum1 > sum2 else sum2)

Solution (Python):

"""
D - XXOR
https://atcoder.jp/contests/abc117/tasks/abc117_d

"""
import sys

from collections import Counter

def solve(N, K, A):
    cnt = Counter()
    for a in A:
        for i in range(40):
            if a & 2**i:
                cnt[i] += 1

    bits = sorted([i for i in range(40) if cnt[i] < N/2], reverse=True)
    X = 0
    for b in bits:
        t = 2**b
        if X + t <= K:
            X += t
    return sum([a^X for a in A])


def __solve(N, K, A):
    cnt = Counter()
    for a in A:
        for i in range(40):
            if a & 2**i:
                cnt[i] += 1

    for i in range(K.bit_length()+1):
        if cnt[i] == 0:
            cnt[i] += 1

    bits = sorted([k for k, v in cnt.items() if v%2])
    while bits:
        ans = sum([2**b for b in bits])
        if ans <= K:
            break
        bits.pop()
    ans = sum([2**b for b in bits]) if bits else 0
    return sum([a^ans for a in A])



def main(args):
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    ans = solve(N, K, A)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Solution (Python):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N,K = inpl()
aa = inpl()
bitmax = 40
bitcnt = [0]*bitmax

for a in aa:
    for b in range(bitmax):
        if (a>>b) & 1 :
            bitcnt[b] += 1

X = 0
for b in reversed(range(bitmax)):
    if bitcnt[b] < N/2:
        X += 1<<b
    if X > K:
        X -= 1<<b

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

Solution (Python):
n, k = map(int, input().split(" "))
b_k = list(map(int, format(k+1, "b").zfill(40)[::-1]))
target = [ 0 for _ in range(40) ]
numbers = list(map(int, input().split(" ")))
for i in numbers:
  for idx, v in enumerate(format(i, "b")[::-1]):
    if v=="1":
      target[idx] += 1
best = [ 1 if n > 2*target[i] else 0 for i in range(40) ]

maxr = sum(numbers)
for i in range(len(b_k)):
  if b_k[i] == 1:
    maxr = max(maxr, sum((2**idx)*(t if r==0 else n-t) for idx, (t, r) in enumerate(zip(target, best[:i] + [0] + b_k[i+1:]))))
print(maxr)

Solution (Python):
N, K = map(int,input().split())
As = list(map(int,input().split()))
bit_length = max(len(bin(K)), len(bin(max(As))))-2 
ans = 0
for i in range(bit_length,-1,-1): 
    bit = 2**i 
    
    n_bit = sum([1 for a in As if a & bit]) 
    
    
    if n_bit < N - n_bit and K-bit >= 0:
        n_bit = N - n_bit
        K -= bit
    ans += bit * n_bit
print(ans)