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()))
M=max(a)
K=str(format(k,'b'))
M=str(format(M,'b'))
x=max(len(K),len(M))
K=str(format(k,'b').zfill(x))
l=[]
for i in range(n):
  l.append(str(format(a[i],'b').zfill(x)))
ctMz=0
for z in range(len(K)):
  if K[z]=='0':
    ctMz+=1
  else:
    break

l2=[]
l2=['0' for aa in range(x)]

ct=0
for j in range(x):
  ctz=0
  cto=0
  for m in range(n):
    if l[m][j]=='0':ctz+=1
    else:cto+=1
  if j+1<=ctMz:
    ct+=(2**(x-j-1))*cto
    l2[j]='0'
  else:
    if ctz>cto:
      l2[j]='1'
      if int(K)>=int(''.join(l2)):
        ct+=(2**(x-j-1))*ctz
      else:
        ct+=(2**(x-j-1))*cto
        l2[j]='0'
    else:
      ct+=(2**(x-j-1))*cto
      l2[j]='0'
print(ct)

Solution (Python):

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

binary = [bin(a) for a in A]
bin_K = bin(K)
ma_len = max([len(e) for e in binary] + [len(bin_K)]) - 2
B = [e[2:].zfill(ma_len) for e in binary]
bin_K = bin_K[2:].zfill(ma_len)


def greedy(C):
    result = []
    s = 0
    for i in range(len(C) - 1):
        s += C[len(C) - i - 1]["score"] * \
            max(C[len(C) - i - 1]["1"], C[len(C) - i - 1]["0"])
        result.append(s)
    return list(reversed(result)) + [0]


C = []
for i in range(ma_len):
    c = {"0": 0, "1": 0}
    for j in range(N):
        c[B[j][i]] += 1
    c["score"] = 2**(ma_len - i - 1)
    C.append(c)

latter = greedy(C)
ans = 0
former = 0
for i in range(ma_len):
    if bin_K[i] == "1":
        ans = max(ans, former + C[i]["1"] * C[i]["score"] + latter[i])
        former += C[i]["score"] * C[i]["0"]
    else:
        former += C[i]["score"] * C[i]["1"]







print(max(ans, former))

Solution (Python):

from sys import stdin


s_in = lambda: stdin.readline()[:-1]  
d_in = lambda: int(stdin.readline())  
ds_in = lambda: list(map(int, stdin.readline().split()))  


N, K = ds_in()
A_list = ds_in()

if K == 0:
    print(sum(A_list))
    exit()

max_A = max(A_list)

bit_K = bin(K)[2:][::-1]
n_bitK = len(bit_K)

bit_list = [0] * (len(bin(max(max_A, K))) - 2)


for a in A_list:
    bit_a = bin(a)[2:][::-1]
    for i, bit in enumerate(bit_a):
        if bit == '1':
            bit_list[i] += 1


ans = 0
for i in range(n_bitK, len(bit_list)):
    ans += 2**i * bit_list[i]

dp = [[0, 0] for _ in range(n_bitK)]
dp[n_bitK-1][1] = 2**(n_bitK-1) * (N - bit_list[n_bitK-1])
dp[n_bitK-1][0] = 2**(n_bitK-1) * bit_list[n_bitK-1]
for i in range(n_bitK-2, -1, -1):
    if bit_K[i] == '1':
        dp[i][1] = dp[i+1][1] + 2**i * (N - bit_list[i])
        dp[i][0] = max(dp[i+1][0] + 2**i * max(bit_list[i], N - bit_list[i]),
                       dp[i+1][1] + 2**i * bit_list[i])
    else:
        dp[i][1] = dp[i+1][1] + 2**i * bit_list[i]
        dp[i][0] = dp[i+1][0] + 2**i * max(bit_list[i], N - bit_list[i])

print(ans + max(dp[0]))

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = ['' for i in range(n)]
maxd = len(bin(10 ** 12 + 1))-2
bink = bin(k)[2:]
digitk = len(bink)
bink1 = bin(k+1)[2:]
digitk1 = len(bink1)
bink = bink.zfill(maxd)[::-1]
bink1 = bink1.zfill(maxd)[::-1]
for i in range(n):
    b[i] = format(a[i], 'b').zfill(maxd)[::-1]


s = [0 for i in range(maxd)]
c = [0 for i in range(maxd)]
for i in range(maxd):
    c[i] = sum(list(map(lambda x: int(x[i]), b)))
for i in range(digitk1):
    if bink1[i] == '1':
        for j in range(i):
            if c[j] <= n/2:
                s[i] += (n-c[j]) * 2 ** j
            else:
                s[i] += c[j] * 2 ** j

        s[i] += c[i] * 2 ** i

        for j in range(i+1, digitk1):
            if bink1[j] == '1':
                s[i] += (n-c[j]) * 2 ** j
            else:
                s[i] += c[j] * 2 ** j

    for j in range(digitk1, maxd):
        s[i] += c[j] * 2 ** j
print(max(s))

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

MAX = 41

k = [0 for _ in range(MAX)]
c = [0 for _ in range(MAX)]
b = [0 for _ in range(MAX)]
v = [[0 for _ in range(MAX)] for _ in range(2)]

K = input_k + 1
d = 0
while K > 0:
    if K % 2 == 1:
        k[d] = 1
    d += 1
    K //= 2

for p in a:
    counter = 0
    while p > 0:
        if p % 2 == 1:
            c[counter] += 1
        counter += 1
        p //= 2

temp = 1
for i in range(MAX):
    if c[i] > n - c[i]:
        b[i] = 0
    else:
        b[i] = 1
    v[0][i] = temp * c[i]
    v[1][i] = temp * (n - c[i])
    temp *= 2

if input_k == 0:
    print(sum(v[0]))
    exit()

ans = 0
for i in range(MAX - 1, -1, -1):
    if k[i] == 0:
        continue

    temp_ans = 0
    for j in range(i+1, MAX):
        temp_ans += v[k[j]][j]

    temp_ans += v[0][i]

    for j in range(i):
        temp_ans += v[b[j]][j]

    
    ans = max(ans, temp_ans)

print(ans)

Solution (Python):
import sys

def get_bit_order(b):
  bo = format(b, 'b')
  return len(bo) - 1


def dp(A, N, K, start):
  ans = 0
  K_order = get_bit_order(K)
  if (K_order - start) < 0:
    return 0
  S = 1 << (K_order - start)
  for b in range(40, -1, -1):
    power = 1 << b
    bit_count = sum([a & power != 0 for a in A])
    
    if (power <= min(S,K)) and (N - bit_count >  bit_count):
      opt_count = N - bit_count
      K -= power
    else:
      opt_count = bit_count
    
    ans += power * opt_count
  return ans


def main():
  input = sys.stdin.readline
  N, K = map(int, input().split())
  A = [int(a) for a in input().split()]
  
  dp_from_1st_Kbit = dp(A, N, K, 0)
  dp_from_2nd_Kbit = dp(A, N, K, 1)

  ans = max(dp_from_1st_Kbit, dp_from_2nd_Kbit)
  print(ans)


if __name__ == '__main__':
  main()

Solution (Python):
N, K = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
cnt = [sum(a >> j & 1 for a in A) for j in range(50)]
ans = 0


def dfs(x, v, f):
    global ans
    if x < 0:
        ans = max(ans, v)
    elif f:
        dfs(x - 1, v + max(cnt[x], N - cnt[x]) * (1 << x), 1)
    elif K >> x & 1:
        dfs(x - 1, v + (cnt[x]) * (1 << x), 1)  
        dfs(x - 1, v + (N - cnt[x]) * (1 << x), 0)  
    else:
        dfs(x - 1, v + (cnt[x]) * (1 << x), 0)  


dfs(49, 0, 0)
print(ans)

Solution (Python):
import sys

def get_k_order(k):
  kb = format(k, 'b')
  return len(kb) - 1


def dp(A, N, K, start):
  ans = 0
  S = 1 << start
  for b in range(40, -1, -1):
    power = 1 << b
    bit_count = sum([a & power != 0 for a in A])
    
    if (power <= S) and (power <= K) and (N - bit_count >  bit_count):
      opt_count = N - bit_count
      K -= power
    else:
      opt_count = bit_count
    
    ans += power * opt_count
  return ans


def main():
  input = sys.stdin.readline
  N, K = map(int, input().split())
  A = [int(a) for a in input().split()]
  ko = get_k_order(K)
  
  dp_from_1st_order = dp(A, N, K, ko)
  if ko > 0:
    dp_from_2nd_order = dp(A, N, K, ko-1)
  else:
    dp_from_2nd_order = 0
  ans = max(dp_from_1st_order, dp_from_2nd_order)
  print(ans)


if __name__ == '__main__':
  main()

Solution (Python):
n,k=map(int,input().split())
A=list(map(int,input().split()))
bit_max=40
ans=0


for c in range(bit_max,-1,-1):
  
  Xi = 1<<c
  
  ck=len([1 for a in A if a&Xi!=0])
  tmp=ck
  
  if Xi<= k and ck<=n-ck:
    tmp=n-ck
    k-=Xi
  contribution=Xi*tmp
  ans+=contribution
print(ans)

Solution (Python):

n,k = map(int, input().split())
al = list(map(int, input().split()))

def f(x):
    res = 0
    for a in al:
        res += x^a
    return res






cs = []
mi = 0
while (1<<mi)<=k:
    s0 = 0
    s1 = 0
    for a in al:
        b = (a>>mi)&1
        if b==1:
            s1 += 1
        else:
            s0 += 1
    cs.append((s0,s1))
    mi += 1
mi += 1

res = 0
for idx in range(mi):
    x = 0
    for i in range(mi):
        if i>idx:
            x += k&(1<<i)
        elif i==idx:
            pass
        else:
            if cs[i][0]>cs[i][1]:
                x += 1<<i
    if x<=k:
        res = max(res, f(x))

print(res)

Solution (Python):
n, k = map(int, input().split(' '))
arr  = list(map(int, input().split(' ')))
count = [0 for _ in range(45)]
for i in arr:
    s = bin(i)[2:]
    
    for idx, val in enumerate(reversed(s)):
        count[45 - idx - 1] += int(val)
        
ans  = 0
prev = 0
f = -1

for idx, val in enumerate(count):
    prev = ans
    if val > n // 2:
        ans |= (0 << 44 - idx)
    else:
        ans |= (1 << 44 - idx)
        
    
    if ans > k:
        ans = prev
        continue 



rep = 0
for val in arr:
    rep += val ^ ans
    
print(rep)

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

xors = lambda x, y: sum([(a & x) ^ y for a in A])
memo = {}

def dp(bind, bit):
  if bit < 0: return 0
  if (bind, bit) in memo: return memo[(bind, bit)]

  x = 1 << bit

  if bind and not(K & x):
    ans = xors(x, 0) + dp(True, bit-1)
  else:
    ans = max(xors(x, x) + dp(bind, bit-1), xors(x, 0) + dp(False, bit-1))

  memo[(bind, bit)] = ans
  return ans

print(dp(True, 40))

Solution (Python):
N,K = map(int,input().split())
A = list(map(int,input().split()))
degit = len(format(10**12,"b"))
bit_1 = [0]*degit
bit_0 = [0]*degit
for a in A:
    string = format(a,"b")
    length = len(string)
    for i in range(length):
        index = degit - length + i
        if string[i] == "1":
            bit_1[index] += 1
        elif string[i] == "0":
            bit_0[index] += 1
    for j in range(degit-length):
        bit_0[j] += 1
        
ideal = ["0"]*degit
for i in range(degit):
    if bit_1[i] >= bit_0[i]:
        ideal[i] = "0"
    elif bit_1[i] < bit_0[i]:
        ideal[i] = "1"

candidate = []
hoge = []
K_bin = format(K,"b")
for i in range(len(K_bin)):
    if K_bin[i] == "1":
        candidate.append(hoge+["0"]+ideal[degit-len(K_bin)+i+1:])
        hoge.append("1")
    elif K_bin[i] == "0":
        hoge.append("0")
    if len(hoge) == len(K_bin):
        candidate.append(hoge)    
ans = 0
for c in candidate:
    c = "".join(c)
    c = c.lstrip("0")
    if c == "":
        c = "0"
    c = int(c,2)
    res = 0
    for a in A:
        res += c ^ a
    if res > ans:
        ans = res

print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def slv2(N, K, A):
    ans = (-1, -1)
    for k in range(K+1):
        tmp = 0
        for a in A:
            tmp += k ^ a
            
        if ans[0] < tmp:
            ans = (tmp, k)
    
    
    return ans[0]


@mt
def slv(N, K, A):

    @lru_cache(maxsize=None)
    def ai(i):
        ii = 1 << i
        c = 0
        for a in A:
            if a & ii > 0:
                c += 1
        return c, ii

    @lru_cache(maxsize=None)
    def a(i):
        if i < 0:
            return 0
        c, ii = ai(i)
        return max(ii*(N-c), ii*c) + a(i-1)

    
    def r(k, i):
        if i < 0:
            return 0
        
        c, ii = ai(i)
        
        if k < ii:
            return r(k, i-1)+ii*(c)
        
        return max(r(k-ii, i-1)+ii*(N-c), a(i-1)+ii*(c))
    
    return r(K, 40)

def main():
    N, K = read_int_n()
    A = read_int_n() 
    print(slv(N, K, A))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def slv2(N, K, A):
    ans = (-1, -1)
    for k in range(K+1):
        tmp = 0
        for a in A:
            tmp += k ^ a
            
        if ans[0] < tmp:
            ans = (tmp, k)
    
    
    return ans[0]


@mt
def slv(N, K, A):

    @lru_cache(maxsize=None)
    def ai(i):
        ii = 1 << i
        c = 0
        for a in A:
            if a & ii > 0:
                c += 1
        return c, ii

    def a(i):
        if i < 0:
            return 0
        c, ii = ai(i)
        return max(ii*(N-c), ii*c) + a(i-1)

    
    @lru_cache(maxsize=None)
    def r(k, i):
        if i < 0:
            return 0
        
        c, ii = ai(i)
        
        if k < ii:
            return r(k, i-1)+ii*(c)
        
        return max(r(k-ii, i-1)+ii*(N-c), a(i-1)+ii*(c))
    
    return r(K, 40)

def main():
    N, K = read_int_n()
    A = read_int_n() 
    print(slv(N, K, A))


    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    

if __name__ == '__main__':
    main()

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

xors = lambda x, y: sum([(a & x) ^ y for a in A])
memo = {}

def dp(flag, k):
  if k < 0: return 0
  if (flag, k) in memo: return memo[(flag, k)]

  x = 1 << k
  ans = 0

  if flag and not(K & x):
    ans = xors(x, 0) + dp(True, k-1)
  else:
    ans = max(xors(x, x) + dp(flag, k-1), xors(x, 0) + dp(False, k-1))

  memo[(flag, k)] = ans
  return ans

print(dp(True, 40))

Solution (Python):
import numpy
n,k=map(int,input().split())
a=list(map(int,input().split()))
d=max(a)
def p(x):
    return len(bin(x))-2
e=p(k)
f=p(d)
h=[]
if e>=f:
    for i in range(n):
        l=bin(a[i])
        h.append(list("0"*(e-len(l)+2)+l[2:]))
else:
    for i in range(n):
        l=bin(a[i])
        h.append(list("0"*(f-len(l)+2)+l[2:]))
p=numpy.array(h)
p=p.T
p=p.tolist()
c=0
if k==0:
    print(sum(a))
else:
    ans=0
    for i in range(len(p)):
        o=p[i].count("1")
        if o<n/2 and k>=2**(len(p)-i-1):
            c+=(n-o)*(2**(len(p)-i-1))
            k-=2**(len(p)-i-1)
        else:
            c+=o*(2**(len(p)-i-1))
    print(c)

Solution (Python):




from copy import deepcopy

def main():
  n, k = map(int, input().split())
  xs   = list(map(int, input().split()))
  k_bin = list(bin(k)[2:])
  keta = len(k_bin)
  li = []
  _xs = deepcopy(xs)
  for i in range(keta):

    tmp = []
    count = 0
    for x in _xs:
      if x%2 == 1:
        count += 1
        tmp += [int((x-1)/2)]
      else:
        tmp += [int((x)/2)]
    _xs = tmp

    li += ['0' if count >= n/2 else '1']
  li = li[::-1]

  ans_picklist = []
  for i in range(keta):
    if k_bin[i] == '0':
      continue
    kouho = int('0b' + ''.join(k_bin[:i]) + '0' + ''.join(li[i+1:]), 0)
    ans_picklist += [(kouho, sum([kouho^x for x in xs]))]
  kouho = int('0b'+''.join(k_bin), 0)
  ans_picklist += [(kouho, sum([kouho^x for x in xs]))]
  ans_picklist.sort(key=lambda x:x[1])
  print(ans_picklist[-1][1])


if __name__=='__main__':
  main()

Solution (Python):
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
m=len(bin(max(a+[k])))-2
b=[0]*m
ans=""
x=0
a2=[bin(i)[2:] for i in a]
for i in a2:
    for j in range(-1,-len(i)-1,-1):
        b[j]+=int(i[j])
B=len(b)
for (i,j) in enumerate(b):
    if j<(n/2) and k>=2**(B-i-1):
        ans=ans+"1"
        k-=2**(B-i-1)
    else:
        ans=ans+"0"
ans=int(ans,2)
for i in a:
    x+=ans^i
print(x)

Solution (Python):
def d_xxor(N, K, A):
    bit_max = 40  
    ans = 0

    for b in range(bit_max, -1, -1):
        power = 1 << b
        
        bit_count_1 = len([1 for a in A if a & power != 0])

        
        tmp = bit_count_1
        if power <= K and bit_count_1 <= N - bit_count_1:
            
            tmp = N - bit_count_1
            K -= power
        contribution = power * tmp

        ans += contribution  
    return ans

N, K = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
print(d_xxor(N, K, A))

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

max_digit = 40


def JudgeDigitN(x, n):
    return x >> n & 1 == 1 
    
c1 = [0] * max_digit
for i in a:
    for j in range(max_digit):
        if JudgeDigitN(i,j):
            c1[j] += 1
b = []

for i in range(max_digit-1,-1,-1):
    if not JudgeDigitN(k,i):
        continue
    tmp = 0
    for j in range(max_digit-1,i,-1):
        if JudgeDigitN(k,j):
            tmp += 2**j * (n-c1[j])
        else:
            tmp += 2**j * c1[j]
    tmp += 2**i * c1[i]
    for j in range(i-1, -1, -1):
        tmp += 2**j * max(c1[j], n-c1[j])
    b.append(tmp)
    
tmp = 0    
for i in range(max_digit):
    if JudgeDigitN(k,i):
        tmp += 2**i * (n-c1[i])
    else:
        tmp += 2**i * c1[i]
b.append(tmp)

print(max(b))

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
sA = [list('{0:040b}'.format(i)) for i in A]
B = list(zip(*sA))
C = [0]*40
for i in range(40):
  if B[i].count('0') > len(B[i])/2:
    C[i] = 1
  else:
    C[i] = 0

ans = 0
for i in range(40):
  if ans + C[i] * 2**(39-i) <= K:
    ans += C[i] * 2**(39-i)
  else:
    ans += ((C[i]+1)%2)*2**(39-i)
s = 0
for i in range(N):
  s += ans ^ A[i]
print(s)

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

max_digits = 40
ans = 0

for i in range(max_digits, -1, -1):
    num = 2 ** i
    count = len([1 for a in A if a & num > 0])
    if count < N / 2 and num <= K:
        count = N - count
        K -= num
    ans += num * count
print(ans)

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

max_digits = 40
ans = 0

for i in range(max_digits,-1,-1):
    num = 2**i
    count = len([1 for a in A if a&num > 0])
    if count < N/2 and num <= K:
        count = N - count
        K -= num
    ans += num * count

print(ans)

Solution (Python):



"""
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = sum(l) - 2*l[-1]
if ans > 0:
    print("Yes")
else:
    print("No")
"""


"""
import bisect
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
xb = [abs(x[i] - x[i + 1]) for i in range(m-1)]
xb.sort(reverse=True)
ans = sum(xb[n - 1::])
print(ans)
"""


n, m = map(int, input().split())
x = list(map(int, input().split()))
a = 0
b = 0
ans = 0
ansb = 0
mae = 0
b = [0 for i in range(40)]
for i in range(40):
    for k in x:
        b[i] += (k & (1 << i)) >> i

for i in range(39, -1, -1):
    if m & (1 << i) > 0:
        ansb = mae
        ansb += b[i] << i
        for k in range(i):
            ansb += max(b[k], n-b[k]) << k
        ans = max(ans, ansb)
        mae += (n-b[i]) << i
    else:
        mae += b[i] << i
ans = max(ans, mae)
print(ans)

Solution (Python):
n, k = map(int, input().split())
aList = list(map(int, input().split()))
bits0 = [0] * 42
bits1 = [0] * 42
def getBit(a):
    mask = 1
    for i in range(42):
        if mask > a and mask > k:
            break
        if a & mask:
            bits1[i] += 1
        else:
            bits0[i] += 1
        mask <<= 1

for a in aList:
    getBit(a)


"""
私は嘘解法でACしました
hack_case
5 2
0 0 0 2 2
-> 6

ans = 0
for i in range(41, -1, -1):
    cnt1 = bits1[i]
    cnt0 = bits0[i]
    if k < 2 ** i:
        ans += 2 ** i * cnt1
        continue
    if cnt0 <= cnt1:
        ans += 2 ** i * cnt1
    else:
        ans += 2 ** i * cnt0
        k -= 2 ** i
print(ans)
"""

INF = 10 ** 20
dp = [[0, -INF] for _ in range(43)]
for i in range(41, -1, -1):
    cnt0 = bits0[i]
    cnt1 = bits1[i]
    if k & (1 << i):
        dp[i][0] = dp[i + 1][0] + 2 ** i * cnt0
        dp[i][1] = max(dp[i + 1][0] + 2 ** i * cnt1, dp[i + 1][1] + 2 ** i * max(cnt0, cnt1))
    else:
        dp[i][0] = dp[i + 1][0] + 2 ** i * cnt1
        dp[i][1] = max(dp[i + 1][1] + 2 ** i * cnt1, dp[i + 1][1] + 2 ** i * cnt0)
print(max(dp[0]))

Solution (Python):
import math
N, K = map(int, input().split())
A = list(map(int, input().split()))
sA = [list('{0:040b}'.format(i)) for i in A]

B = list(zip(*sA))



C = [0]*40
for i in range(40):
  if B[i].count('0') > len(B[i])/2:
    C[i] = 1
  else:
    C[i] = 0



cnt = 0
dig = 39
ans = 0
while dig >= 0:
  if ans + C[cnt] * 2**dig <= K:
    ans += C[cnt] * 2**dig
    cnt += 1
    dig -= 1
  elif ans + ((C[cnt]+1)%2)*2**dig <= K:
    ans += ((C[cnt]+1)%2)*2**dig
    cnt += 1
    dig -= 1
  
s = 0
for i in range(N):
  s += ans ^ A[i]
print(s)

Solution (Python):
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
S=[]
for i in range(51):
  num1=0
  for a in A:
    if a&(1<<i):
      num1+=1
  S.append(num1)
f=0
for i in range(50):
  s=0
  flag=False
  for j in range(51)[::-1]:
    if i>j:
      s+=max(S[j],N-S[j])*(1<<j)
    elif i==j:
      if (K+1)&(1<<j):
        flag=True
        s+=S[j]*(1<<j)
      else:
        s=0
        break
    else:
      if (K+1)&(1<<j):
        s+=(N-S[j])*(1<<j)
      else:
        s+=S[j]*(1<<j)
  f=max(f,s)
s=0
for j in range(51):
  s+=S[j]*(1<<j)
f=max(f,s)

print(f)

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


from collections import defaultdict
counter=defaultdict(int)


def makebit(a):
    return bin(a)[2:]


def count(a):
    l=len(a)
    for i in range(1,l+1):
        if a[-i]=='1':
            counter[i]+=1
    return


for i in range(len(a)):
    count(makebit(a[i]))


kbit=makebit(k)

onetime=kbit.count('1')

if len(counter)>0:
    maxlenth=max(counter)
elif len(counter)==0:
    maxlenth=0





for i in range(1,1+max(maxlenth,len(kbit))):
    if counter[i]==0:
        counter[i]=0

if maxlenth>len(kbit):
    kbit='0'*(maxlenth-len(kbit))+kbit
elif maxlenth<len(kbit):
    maxlenth=len(kbit)
    
kaijo=[]
for i in range(maxlenth+1):
    kaijo.append(2**i)



def search(kbit,default,ans,before,counter):
    if kbit.count('1')==0:
        dlenth=len(kbit)
        for keta in counter:
            if keta>before:continue
            elif keta<=dlenth:
                default+=counter[keta]*kaijo[keta-1]
        if default>ans:ans=default
        return ans
    dlenth=len(kbit)-kbit.index('1')
    now=default
    newcounter=counter.copy()
    for keta in counter:
        if keta>before:continue
        elif keta>dlenth:
            default+=counter[keta]*kaijo[keta-1]
            now+=counter[keta]*kaijo[keta-1]
            newcounter.pop(keta)
        elif keta==dlenth:
            default+=(n-counter[keta])*kaijo[keta-1]
            now+=counter[keta]*kaijo[keta-1]
            newcounter.pop(keta)
        elif keta<dlenth:now+=max(n-counter[keta],counter[keta])*kaijo[keta-1]
    if kbit.index('1')==len(kbit)-1:
        now=default-(n-counter[1])
        now+=max(n-counter[1],counter[1])
        if now>ans:ans=now
        return ans
    if now>ans:ans=now
    idx=kbit.index('1')
    kbit=kbit[idx+1:]
    return search(kbit,default,ans,dlenth,newcounter)
print(search(kbit,0,0,maxlenth+1,counter))

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

len_a=len(str(bin(max(a))))-2
len_k=len(str(bin(k)))-2

if len_a >= len_k:
  length =len_a
  for i in range(n):
    a[i] = ("0"*length+str(bin(a[i]))[2:])[-len_a:] 
elif len_a < len_k:
  length =len_k
  for i in range(n):
    a[i] = ("0"*length+str(bin(a[i]))[2:])[-len_k:]
    
k = ("0"*length+str(bin(k))[2:])[-length:]

flag = False
for i in range(length):
  count_0 =0
  count_1 =0
  for j in range(n):
    if a[j][i]=="0":
      count_0 += 1
    else:
      count_1 += 1
  
  if count_0 <= count_1 and k[i]=="1":
    if i==0:   
      k="0"+k[1:length]
    elif i == length - 1:
      k= k[0:i]+"0"
    else:
      k= k[0:i]+"0"+k[i+1:]
    flag = True
  elif count_0 > count_1 and k[i]=="0" and flag:
    if i==0:   
      k="1"+k[1:length]
    elif i == length - 1:
      k= k[0:i]+"1"
    else:
      k=k[0:i]+"1"+k[i+1:]
      
ans = 0
for i in range(n):
  for j in range(length):
    if a[i][j]!=k[j]:
      ans +=2**(length-1-j)
print(ans)

Solution (Python):

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

ans = 0
for b in range(-1, 60)[::-1]:
    if b >= 0 and not K >> b & 1:
        continue
    tmp = 0
    for i in range(60)[::-1]:
        c = sum(x >> i & 1 for x in A)
        if i > b:
            tmp += (1 << i) * (N - c if K >> i & 1 else c)
        elif i == b:
            tmp += (1 << i) * c
        else:
            tmp += (1 << i) * max(c, N - c)
    ans = max(ans, tmp)

print(ans)

Solution (Python):
def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

L = 40

N, K = reads()
A = reads()
K = K + 1

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

maj = 0
for j in range(L):
  if sum(a & (1 << j) > 0 for a in A) <= N // 2:
    maj |= (1 << j)

ans = 0
for i in range(L):
  if K & (1 << i) == 0:
    continue
  X = K & ((~0) << (i+1)) | (maj & ((1 << i) - 1))
  ans = max(ans, f(X))

print(ans)

Solution (Python):
from numpy import array
N, K = map(int, input().split())
A = [int(i) for i in input().split()]
k = '{0:040b}'.format(K)
a = array([[int(i) for i in '{0:040b}'.format(a)] for a in A])
ans = list(k)

f = False
for i in range(40):
    if k[i] == '0' and not f:
        continue
    ik = a[:, [i]].sum()
    zk = N - ik
    if ik > zk:
        ans[i] = '0'
        f = True
    else:
        ans[i] = '1'

ans = ''.join(ans)
k = int(ans, 2)
print(sum([x ^ k for x in A]))

Solution (Python):
N,K=map(int,input().split())
A=[bin(int(i))[2:][::-1] for i in input().split()]
Kd=K&((1<<20)-1)
Ku=K-Kd
L=[0]*41
for a in A:
    for i in range(len(a)):
        if a[i]=='1':
            L[i]+=1


downans=0
otherans=0
for i in range(1<<20):
    t=0
    for j in range(20):
        if i & (1<<j):
            t+=(N-L[j])*(1<<j)
        else:
            t+=(L[j])*(1<<j)
    otherans=max(otherans,t)
    if i<=Kd:
        downans=max(downans,t)
upans=0
Kdown=0
for i in range(1<<20):
    t=0
    if i>(Ku>>20):
        continue
    for j in range(20):
        if i & (1<<j):
            t+=(N-L[j+20])*(1<<(j+20))
        else:
            t+=(L[j+20])*(1<<(j+20))
    if i<(Ku>>20):
        upans=max(upans,t)
    else:
        Kdown=max(Kdown,t)

if Ku==0:
    print(Kdown+downans)
else:
    print(max(Kdown+downans,upans+otherans))

Solution (Python):





N,K = map(int,input().split())
A = list(map(int,input().split()))
degit = len(format(10**12,"b"))
bit_1 = [0]*degit
bit_0 = [0]*degit
for a in A:
    string = format(a,"b")
    length = len(string)
    for i in range(length):
        index = degit - length + i
        if string[i] == "1":
            bit_1[index] += 1
        elif string[i] == "0":
            bit_0[index] += 1
    for j in range(degit-length):
        bit_0[j] += 1
        
can = ["0"]*degit

for i in range(degit):
    if bit_1[i] >= bit_0[i]:
        can[i] = "0"
    elif bit_1[i] < bit_0[i]:
        copy = can[:]
        copy[i] = "1"
        res = int("".join(copy),2)
        if res <= K:
            can = copy

can = int("".join(can),2)

ans = 0
for a in A:
    ans += can ^ a

print(ans)

Solution (Python):
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, K] = [long(input_raw[0]), long(input_raw[1])]
    input_raw = read_func().strip().split()
    A = []
    for i in range(N):
        A.append(long(input_raw[i]))

    max_x = 0L
    for i in range(40):
        mask = 0x01 << i
        one_count = 0
        for j in range(len(A)):
            one_count += 1 if (A[j] &  mask ) > 0 else 0
        if one_count <= N/2:
            max_x += (0x01 << i)

    x = 0L
    flag = False
    for i in range(40, -1, -1):
        mask = 0x01 << i
        if K & mask != 0 & flag == False:
            if (max_x & mask) == 0:
                flag = True
            else:
                x += (max_x & mask)
        elif flag == True:
            x += (max_x & mask)

    fx = 0L
    for i in range(len(A)):
        fx += (x ^ A[i])
    max_fx = fx

    for i in range(40, -1, -1):
        mask = ~(0x01L << i)
        x = max_x & mask
        max_x = x
        if x <= K:
            fx = 0L
            for i in range(len(A)):
                fx += (x ^ A[i])
            max_fx = max(max_fx, fx)
    print max_fx



if __name__ == '__main__':
    main()

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





keta = (len(bin(K)[2:]))

num1s = [0] * keta
for a in A:
    for j in range(keta):
        if (1 << j) & a :
            num1s[j] = num1s[j] + 1

half = N/2
X = 0
if K != 0:
    for j in range(keta):
            X = X + ((num1s[j] < half)<<j)
answer = 0

def f (X):
    r = 0
    for a in A:
        r = r + (a^X)
    return r

maxfx = f(K)
for j in range(keta):
    if (1<<j)&K:
        
        x = (((1<<j) -1)&X ) 
        x = x | ((~((1<<(j+1))-1))&K)
        if f(x) > maxfx:
            maxfx = f(x)
            
print(maxfx)

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





keta = (len(bin(K)[2:]))

num1s = [0] * keta
for a in A:
    for j in range(keta):
        if (1 << j) & a :
            num1s[j] = num1s[j] + 1




half = N/2
X = 0
if K != 0:
    for j in range(keta):
        
        
        
            X = X + ((num1s[j] < half)<<j)
answer = 0



def f (X):
    r = 0
    for a in A:
        r = r + (a^X)
    return r

maxfx = f(K)
for j in range(keta):
    if (1<<j)&K:
        
        x = (((1<<j) -1)&X ) 
        x = x | ((~((1<<(j+1))-1))&K)
        if f(x) > maxfx:
            maxfx = f(x)
            
print(maxfx)