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



bit_stand_counts = [0] * 40
for a in A:
    a = bin(a)[2:].zfill(40)
    for i in range(40):
        if a[i] == '1':
            bit_stand_counts[i] += 1



dp = [[-1, -1] for i in range(41)]
dp[0][0] = 0



K_bit = bin(K)[2:].zfill(40)


for i in range(40):
    value_0 = (2 ** (39 - i)) * bit_stand_counts[i]  
    value_1 = (2 ** (39 - i)) * (N - bit_stand_counts[i])  
    
    if K_bit[i] == '0':  
        dp[i + 1][0] = dp[i][0] + value_0
    else:
        dp[i + 1][0] = dp[i][0] + value_1
        dp[i + 1][1] = max(dp[i + 1][1], dp[i][0] + value_0)  

    if dp[i][1] != -1:  
        dp[i + 1][1] = max(dp[i + 1][1], dp[i][1] + max(value_0, value_1))


print(max(dp[-1]))

Solution (Python):
from itertools import product
N, K = map(int, input().split())
A = list(map(int, input().split()))
K_bin = bin(K)[2:]
digit = max(len(K_bin), len(bin(max(A))[2:]))
K_bin = K_bin.zfill(digit)
B = [bin(a)[2:].zfill(digit) for a in A]

C = [0] * digit
for b in B:
    for i, s in enumerate(b):
        if s == '0':
            C[i] += 1
ideal = ''
for c in C:
    binary = '1' if c > N//2 else '0'
    ideal += binary
dp = [[0 for _ in range(2)] for _ in range(digit)]
cands = [0]
gain = [2**i for i in range(digit)][::-1]

def calc(s):
    ret = 0
    for i in range(digit):
        tmp = C[i] if s[i] == '1' else N-C[i]
        ret += tmp * gain[i]
    return ret

for i in range(digit):
    if K_bin[i] == '1':
        cands.append(calc(K_bin[:i] + '0' + ideal[i+1:]))
print(max(max(cands), calc(K_bin)))

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

half = n>>1
lm = max(l)
lm = max([lm,k])
r = 1
cntlist = []
while(lm > 0):
    cnt = 0
    for i in range(len(l)):
        cnt += l[i]%2
        l[i] >>= 1
    cntlist.append(cnt)
    lm >>= 1
    r *= 2
r >>= 1
res = 0

cntlist = cntlist[::-1]

for x in cntlist:
    if(r>k):
        res += x*r
    elif(x>n-x):
        res += r*x
    else:
        res += (n-x)*r
        k -= r
    r >>= 1
print(res)

Solution (Python):





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


ans = 0

for i in range(40, -1, -1):
    
    
    power = 1 << i  
    
    
    bit_count_of_1 = sum(1 for a in A if a & power != 0)  

    
    
    if power > K:
        
        ans += power * bit_count_of_1
        
    elif bit_count_of_1 > N - bit_count_of_1:
        
        ans += power * bit_count_of_1
    else:
        ans += power * (N - bit_count_of_1)
        K -= power  
        
        
        


print(ans)

Solution (Python):
n, k = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
INF = 1e18

DP = [[0] * 41 for i in range(2)]
DP[0][40] = -INF

for i in range(39, -1, -1):
    b = 1 << i
    cnt = [0, 0]
    for a in A:
        cnt[(a >> i) & 1] += 1
    for j in range(2):
        cnt[j] *= b
    if (k >> i) & 1:
        DP[1][i] = DP[1][i+1] + cnt[0]
        DP[0][i] = max(DP[0][i+1] + cnt[0], DP[0][i+1] + cnt[1], DP[1][i+1] + cnt[1])
    else:
        DP[1][i] = DP[1][i+1] + cnt[1]
        DP[0][i] = DP[0][i+1] + max(cnt)

print(max(DP[i][0] for i in range(2)))

Solution (Python):
n, k = map(int, input().split())
a = list(map(int, input().split()))
dig=[0 for i in range(40)] 

for i in range(n) :
    temp = a[i] 
    for j in range(40) :
        if temp <= 0 :
            break
        if temp % 2 == 1 :
            dig[j] += 1
        temp = temp // 2

bin = 1 << 39 
sum0 = 0
i = 39

while(bin > k) :
    sum0 += bin * dig[i]
    bin //= 2
    i += -1

memo={}

def solve (k, bin, i) :
    if i < 0 :
        return 0, 0
    if (k,bin) in memo:
        return memo[(k,bin)]
    if k >= bin :  
        sum1, ans1 = solve(k-bin, bin//2, i-1)
        sum1 += bin * (n- dig[i]) 
        sum0, ans0 = solve(bin-1,bin//2, i-1)
        sum0 += bin * dig[i]
        if sum1 >= sum0 :
            sum = sum1
            ans = ans1 + bin
        else :
            sum = sum0
            ans = ans0
    else :         
        sum, ans = solve(k,bin//2, i-1)
        sum += bin * dig[i]
    memo[(k,bin)] = sum, ans
    return sum, ans

sum, ans = solve(k, bin, i)

print (sum+sum0)

Solution (Python):
N,K = map(int, input().split())
A = list(map(int, input().split()))
def f(X):
    res = 0
    for a in A:
        res += X ^ a
    return res

ans = max(f(0), f(K))
for d in range(60, 0, -1):
    if K & (1<<d) == 0:
        continue
    X = K &  ~((1<<d+1)-1)

    for j in range(d): 
        count_should_raise = 0
        mask = 1<<j
        for a in A:
            if a & mask == 0: count_should_raise += 1
        if count_should_raise > N//2:
            X |= 1<<j
    ans = max(ans, f(X))
print(ans)

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

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

ans = max(f(0), f(K))

for d in range(60, 0, -1):
    if K & (1<<d) == 0:
        continue

    
    
    X = K &  ~((1<<d+1)-1)
    if d == 0:
        ans = max(f(0), f(K-1))

    


    for j in range(d): 
        count_should_raise = 0
        mask = 1<<j
        for a in A:
            if a & mask == 0: count_should_raise += 1
        if count_should_raise > N//2:
            
            X |= 1<<j

    
    
    ans = max(ans, f(X))
print(ans)

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

ans = 0

for i in range(40,-1,-1):
    power = 1 << i
    
    bit_count_of_1 = sum(1 for a in a if a & power != 0) 

    if power > k: 
        ans += power * bit_count_of_1
    elif bit_count_of_1 > n - bit_count_of_1: 
        ans += power * bit_count_of_1
    else:
        ans += power * (n - bit_count_of_1)
        k -= power

print(ans)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
bit = [0] * 41
for i in A:
    for j in range(41):
        bit[j] += (i >> j) & 1
x = {}
for i in range(41):
    x[i, 0] = 2 ** i * bit[i]
    x[i, 1] = 2 ** i * (N - bit[i])
ans = sum(A)
for i in range(41):
    if ((K + 1) >> i) & 1 == 0:
        continue
    f = 0
    for j in range(i):
        f += max(x[j, 0], x[j, 1])
    f += x[i, 0]
    for j in range(i + 1, 41):
        f += x[j, ((K + 1) >> j) & 1]
    ans = max(ans, f)
print(ans)

Solution (Python):
def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    print(solve(N,K,A))
def maxBitNum(num):
    
    q = num//2
    if q==0:
        return(1)
    else:
        return(1+maxBitNum(q))
def solve(N,K,A):
    
    maxA = 10**12
    maxDigit = maxBitNum(maxA)
    
    kString = format(K,'0'+str(maxDigit)+'b')
    
    bitNumList = [countBitForGivenDigit(A,i) for i in range(maxDigit)]
    
    greedySolutions = [0 for _ in range(maxDigit)]
    greedySolutions[0] = getGreedNum(0,bitNumList[0],N)
    for i in range(1,maxDigit):
        greedySolutions[i] = greedySolutions[i-1] + getGreedNum(i,bitNumList[i],N)
    
    
    ans = 0
    
    
    
    partialSumForXeqK = [0 for _ in range(maxDigit + 1)]
    for x in range(1,maxDigit+1):
        bitKx = int(kString[x-1])
        
        
        d = maxDigit - x
        if bitKx == 1:
            xDiff = (N - bitNumList[d]) * pow(2,d)
        else:
            xDiff = bitNumList[d] * pow(2,d)
        partialSumForXeqK[x] = partialSumForXeqK[x-1] + xDiff
    
    for x in range(1,maxDigit+1):
        
        bitKx = int(kString[x-1])
        if bitKx == 0:
            continue
        
        d = maxDigit - x
        if d != 0:
            candidate = partialSumForXeqK[x-1] + pow(2,d) * bitNumList[d] + greedySolutions[d-1]
        else:
            candidate = partialSumForXeqK[x-1] + pow(2,d) * bitNumList[d] 
        
        ans = max(ans,candidate)
    
    
    ans = max(ans,partialSumForXeqK[maxDigit])

    return(ans)

def getGreedNum(d,bitNum,N):
    ans = pow(2,d) * max(bitNum,N-bitNum)
    
    return(ans)

def countBitForGivenDigit(alist,digit):
    
    
    num = pow(2,digit)
    bitNum = 0
    for x in alist:
        bitNum += (x & num)//num
    return(bitNum)


main()

Solution (Python):

def 解():
    N,K=[int(_) for _ in input().split()]
    aD =[0]*40
    aA=[int(_) for _ in input().split()]
    iL = 0
    for i in range(40):
        m = 2**i
        aD[i]=sum((_ & m) for _ in aA)
        if aD[i]:
            iL = i
    iLK = len(bin(K))-3
    iML = max(iL,iLK)
    dp = [[0]*2 for _ in range(2)]
    
    
    for i in range(iML,-1,-1):
        ib = i%2 
        inb = 0 if ib else 1 
        i0 = aD[i] 
        i1 = (2**i)*N-i0 
        iM = max(i0,i1) 
        bL = i < iLK 
        if (K>>i)&1:
            dp[inb][1] = dp[ib][1] + i1
            dp[inb][0] = max(dp[ib][1] + i0 ,dp[ib][0]+(iM if bL else i0))
        else:
            dp[inb][1] = dp[ib][1] + i0
            dp[inb][0] = dp[ib][0] + (iM if bL else i0)
    print(max(dp[inb]))
解()

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


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


def ceil(a, b):
    return (a + b - 1) // b



def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)



def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


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

    count = [0] * 41
    for a in A:
        for i in range(40, -1, -1):
            if (a >> i) & 1:
                count[40 - i] += 1

    x = 0
    for i in range(40, -1, -1):
        if count[40 - i] <= N / 2:
            if (x | 1 << i) <= K:
                x |= 1 << i

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


if __name__ == '__main__':
    main()

Solution (Python):

"""
Created on Sat Feb  9 13:24:45 2019

@author: Yamazaki Kenichi
"""

N,K = map(int,input().split())
A = list(map(int,input().split()))
a = ['{:040b}'.format(i) for i in A]
k = '{:040b}'.format(K)
res = 0
flg = False
for i in range(40):
    counta = 0
    for elem in a:
        if elem[i] == '1':
            counta += 1
    check = True if counta<N/2 else False
    if flg:
        if check:
            res += pow(2,39-i)
        continue
    if check and k[i]=='1':
        res += pow(2,39-i)
    else:
        if k[i]=='1':
            flg = True
ans =0
for elem in A:
    ans += elem^res
print(ans)

Solution (Python):

"""
Created on Sat Feb  9 13:24:45 2019

@author: Yamazaki Kenichi
"""

N,K = map(int,input().split())
A = list(map(int,input().split()))
def int2bin(n):
    return '{:040b}'.format(n)
a = list(map(int2bin, A))
k = int2bin(K)
res = 0
flg = False
for i in range(40):
    counta = 0
    for elem in a:
        if elem[i] == '1':
            counta += 1
        check = True if counta<N/2 else False
    if flg:
        if check:
            res += pow(2,39-i)
        continue
    if check and k[i]=='1':
        res += pow(2,39-i)
    else:
        if k[i]=='1':
            flg = True
ans =0
for elem in A:
    ans += elem^res
print(ans)

Solution (Python):

"""
Created on Sat Feb  9 13:24:45 2019

@author: Yamazaki Kenichi
"""

N,K = map(int,input().split())
A = list(map(int,input().split()))
a = ['{:040b}'.format(i) for i in A]
k = '{:040b}'.format(K)
res = 0
flg = False
for i in range(40):
    counta = 0
    for elem in a:
        if elem[i] == '1':
            counta += 1
        check = True if counta<N/2 else False
    if flg:
        if check:
            res += pow(2,39-i)
        continue
    if check and k[i]=='1':
        res += pow(2,39-i)
    else:
        if k[i]=='1':
            flg = True
ans =0
for elem in A:
    ans += elem^res
print(ans)

Solution (Python):

"""
Created on Sat Feb  9 13:24:45 2019

@author: Yamazaki Kenichi
"""

N,K = map(int,input().split())
A = list(map(int,input().split()))
a = ['{:040b}'.format(i) for i in A]
k = '{:040b}'.format(K)
res = 0
flg = False
for i in range(40):
    counta = 0
    for elem in a:
        counta += 1 if elem[i] == '1' else 0
        check = True if counta<N/2 else False
    if flg:
        if check:
            res += pow(2,39-i)
        continue
    if check and k[i]=='1':
        res += pow(2,39-i)
    else:
        if k[i]=='1':
            flg = True
ans =0
for elem in A:
    ans += elem^res
print(ans)

Solution (Python):

"""
Created on Sat Feb  9 13:24:45 2019

@author: Yamazaki Kenichi
"""

N,K = map(int,input().split())
A = list(map(int,input().split()))
a = ['{:040b}'.format(i) for i in A]
k = '{:040b}'.format(K)
res = 0
flg = False
for i in range(40):
    counta = 0
    for j in range(N):
        counta += 1 if a[j][i] == '1' else 0
        check = True if counta<N/2 else False
    if flg:
        if check:
            res += pow(2,39-i)
        continue
    if check and k[i]=='1':
        res += pow(2,39-i)
    else:
        if k[i]=='1':
            flg = True
ans =0
for elem in A:
    ans += elem^res
print(ans)

Solution (Python):

"""
Created on Sat Feb  9 13:24:45 2019

@author: Yamazaki Kenichi
"""

N,K = map(int,input().split())
A = list(map(int,input().split()))
a = ['{:040b}'.format(i) for i in A]
k = '{:040b}'.format(K)
ans = 0
flg = False
for i in range(40):
    counta = 0
    for j in range(N):
        counta += 1 if a[j][i] == '1' else 0
        check = 1 if counta<N/2 else 0
    
    if flg:
        ans += pow(2,39-i)*(N-counta) if check==1 else pow(2,39-i)*counta
        continue
    if check==1 and k[i]=='0':
        ans += pow(2,39-i)*counta
    elif check==0 and k[i]=='1':
        ans += pow(2,39-i)*counta
        flg = True
    else:
        ans += pow(2,39-i)*(N-counta) if check==1 else pow(2,39-i)*counta
print(ans)

Solution (Python):

"""
Created on Sat Feb  9 13:24:45 2019

@author: Yamazaki Kenichi
"""

N,K = map(int,input().split())
A = list(map(int,input().split()))
a = ['{:040b}'.format(i) for i in A]
k = '{:040b}'.format(K)
ans = 0
b = 0
for i in range(40):
    counta = 0
    for j in range(N):
        counta += 1 if a[j][i] == '1' else 0
        check = 1 if counta<N/2 else 0
    
    if b == 1:
        ans += pow(2,39-i)*(N-counta) if check==1 else pow(2,39-i)*counta
    elif check==1 and k[i]=='0':
        ans += pow(2,39-i)*counta
    elif check==0 and k[i]=='1':
        ans += pow(2,39-i)*counta
        b=1
    else:
        ans += pow(2,39-i)*(N-counta) if check==1 else pow(2,39-i)*counta
print(ans)

Solution (Python):
n,m=map(int,input().split())
A=list(map(int,input().split()))
ans=0
for i in range(40,-1,-1):
    cnt=0
    for j in A:
        if j%(1<<(i+1))>=(1<<i):
            cnt+=1
    a=cnt
    if m>=2**i and cnt<=n-cnt:
        a=n-cnt
        m-=2**i
    ans+=a*(2**i)
print(ans)

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

bits_k = len(bin(k)) - 2
forma = '0%db' % bits_k
data = [0 for i in range(bits_k)]

for an in a:
    anb = format(an, forma)
    
    for i in range(bits_k):
        if anb[-i-1] == '0':
            data[i] += 1
        else:
            data[i] -= 1


ans = 0
for i in range(bits_k - 1, -1, -1):
    if data[i] > 0:
        ans |= (1 << i)
        if ans > k:
            ans &= ~(1 << i)


b = sum([ans ^ an for an in a])
print(b)

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

ans = 0
s = 0

for i in range(39, -1, -1):
    cnt = [0, 0]
    for a in A:
        cnt[(a >> i) & 1] += 1
    b = 0 if cnt[0] > cnt[1] else 1
    if s + (1 << i) > k:
        b = 1
    if b == 0:
        s += 1 << i
    ans += cnt[b] * (1 << i)

print(ans)

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

zero = [0] * 50
one = [0] * 50

for a in A:
  for d in range(40):
    r = a % 2
    if r:
      one[d] += 1
    else:
      zero[d] += 1
    a = int(a / 2)

k = [0] * 50
d = 0
while K:
  r = K % 2
  if r:
    k[d] = 1
  K = int(K / 2)
  d += 1

d = 49
flag = 0
max = 0
while d >= 0:
  if flag == 0:
    if k[d] == 0:
      max += one[d] * pow(2, d)
    else:
      if zero[d] >= one[d]:
        max += zero[d] * pow(2, d)
      else:
        max += one[d] * pow(2, d)
        flag = 1
  else:
    if zero[d] >= one[d]:
      max += zero[d] * pow(2, d)
    else:
      max += one[d] * pow(2, d)
  d -= 1

print(max)

Solution (Python):
def XOR(A, B):
    BA = int(A)
    BB = int(B)
    result = BA + BB
    result = str(result)
    result = result.replace('2', '0')
    result = int(result, 2)
    return result


L1 = input()
L2 = input()
L1 = L1.split()
L2 = L2.split()
for i, val in enumerate(L1):
    L1[i] = int(val)
K = L1[1]
K = bin(K)
K = K[2:]
lenK = len(K)
L3 = []
for i, val in enumerate(L2):
    L2[i] = int(val)
    L2[i] = bin(L2[i])
    lenL2i = len(L2[i])-2
    L2[i] = L2[i][2:]
    if lenL2i < lenK:
        dif = lenK - lenL2i
        for a in range(dif):
            L2[i] = '0' + L2[i]
        L3.append(L2[i])
    elif lenL2i == lenK:
        L3.append(L2[i])
    else:
        dif = lenL2i - lenK
        L3.append(L2[i][dif:])
final = ''
judgeFlag = 0
i = 0
finalJudge = 0

if K == '0':
    final = '0'
else:
    while i < lenK:
        
        
        
        
        if (judgeFlag == 1) & (finalJudge == 0):
            if K[i] == '0':
                final += '0'
                i += 1
            else:
                
                count_0 = 0
                count_1 = 0
                for each in L3:
                    if each[i] == '0':
                        count_1 += 1
                    else:
                        count_0 += 1
                if count_1 >= count_0:
                    final += '1'
                    judgeFlag = 1
                else:
                    final += '0'
                    finalJudge = 1
                i += 1
        else:
            
            count_0 = 0
            count_1 = 0
            for each in L3:
                if each[i] == '0':
                    count_1 += 1
                else:
                    count_0 += 1
            if count_1 >= count_0:
                final += '1'
                judgeFlag = 1
            else:
                final += '0'
                finalJudge = 1
            i += 1
sumInt = 0
for each in L2:
    sumInt += XOR(final, each)

print(sumInt)

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

while mask > k:
    mask >>= 1

x = 0
while True:
    bit_count = 0
    for aa in a:
        if aa & mask > 0:
            bit_count += 1
    if n > bit_count * 2 and x + mask <= k:
        x += mask
    if mask <= 1:
        break
    mask >>= 1

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

Solution (Python):
from itertools import accumulate
N, K = map(int, input().split())
A = list(map(int, input().split()))
m = K.bit_length()
b = [sum((a >> k) & 1 for a in A) for k in range(m)]
opt = [0] + list(accumulate(1 << k if 2 * b[k] < N else 0 for k in range(m)))


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


def g(k, s):
    if k == 0:
        return f(s)
    r = k.bit_length()
    return max(
      f(s + opt[r - 1]),
      g(k - (1 << (r - 1)), s + (1 << (r - 1)))
    )


ans = g(K, 0)
print(ans)

Solution (Python):
def solve(n, k, al):
    bin_k = format(k,"b")
    len_k = len(bin_k)
    
    
    answer = 0
    enable_one = False
    zero_limit = n // 2
    for i in range(len_k,-1,-1):
        bit = 1 << i
        answer = answer << 1
        if enable_one or ((k & bit) != 0):
            
            zero_count = 0
            for e in al:
                if (e & bit) == 0:
                    zero_count += 1
            if zero_count > zero_limit:
                answer += 1
            else:
                enable_one = True
    

    s = 0
    for e in al:
        s = s + (answer ^ e)
    print(s)

def main():
    n, k = map(int, input().split())
    al = list(map(int, input().split()))
    solve(n, k, al)

main()

Solution (Python):



from collections import Counter

def main():
    inf = float("inf")
    dp = [[-inf for _ in range(2)] for _ in range(42)]
    dp[41][0] = 0

    n, k = list(map(int, input().split()))
    As = list(map(int, input().split()))
    ans = 0
    x = 0
    for i in range(40, -1, -1):
        pow2i = 1 << i
        c = 0
        for a in As:
            if (a >> i) & 1:
                c += 1
        bit = (k >> i) & 1
        dp[i][1] = max(n-c, c) * pow2i + dp[i+1][1]
        if bit == 0:
            dp[i][0] = c * pow2i + dp[i+1][0]
        else:
            dp[i][0] = (n - c) * pow2i + dp[i+1][0]
            dp[i][1] = max(dp[i][1], c * pow2i + dp[i+1][0])
    ans = max(dp[0][0], dp[0][1])
    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import math

_, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

logk = 50
half = len(a) / 2

base = np.array([2**i for i in range(logk + 1)])

a = np.array(a)

ones = a[:,None] & base > 0
zeros = (ones != True)





no = np.sum(ones, axis=0)
nz = np.sum(zeros, axis=0)

ov = no * base
zv = nz * base




inc = ov < zv

inceq = ov == zv


















kk = [0]
fx = [0]
for i, b in reversed(list(enumerate(base))):
    for j in range(len(fx)):
        added = kk[j] + b
        if (inc[i] or inceq[i]) and added <= k:
            if inceq[i]:
                fx.append(fx[j] + ov[i])
                kk.append(kk[j])
            fx[j] += zv[i]
            kk[j] += b

        else:
            fx[j] += ov[i]

print(max(fx))

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



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

for i in range(1,42):
    if dp[i-1][1] == 1:
        dp[i][1] = 1
    
    
    ctr = 0
    for j in range(n):
        if (a[j]>>(41-i))&1 == 1:
            ctr += 1

    if ctr >= n-ctr:
        
        dp[i][0] = dp[i-1][0] + ctr*(2**(41-i))
        if (k >> (41-i))&1 == 1:
            dp[i][1] = 1
    else:
        
        if dp[i][1] == 1:
            
            dp[i][0] = dp[i-1][0]+(n-ctr)*(2**(41-i))
        else:
            if (k >> (41-i))&1 == 1:
                
                dp[i][0] = dp[i-1][0]+(n-ctr)*(2**(41-i))
            else:
                
                dp[i][0] = dp[i-1][0] + ctr*(2**(41-i))

print(dp[41][0])

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

rtn = 0
bit_max = 40

for i in range(bit_max)[::-1]:
    target = 1 << i
    hit_num = len([1 for i in A_list if i & target != 0])
    
    if N-hit_num > hit_num and K >= target:
        K -= target
        hit_num = N - hit_num
    
    rtn += target * hit_num
print(rtn)

Solution (Python):

import math

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

digit_K = int(math.log(K, 2)) + 1 if not K == 0 else 0
d1s = [0]*digit_K
gain = []

ans = sum(A)
for i in range(digit_K):
    for j in range(N):
        d1s[i] += A[j] % 2
        A[j] = A[j] // 2
    gain.append((N - d1s[i] * 2) * 2**i)

pGain = [max(g, 0) for g in gain]
cK, kGain = K, []
for i in range(digit_K):
    cK, dK = divmod(cK,2)
    kGain.append(pGain[i] * dK)

maxgain = sum(kGain)
for i in range(digit_K):
    K, dK = divmod(K, 2)
    if dK == 1:
        sumgain = sum(pGain[:i] + kGain[i+1:])
        maxgain = max(maxgain, sumgain)

ans += maxgain
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
num = [0]*42
n_num = [0]*42
for e in range(41,-1,-1):
    mask = 1<<e
    for a in A:
        if a&mask:
            num[e]+=1
    n_num[e] = N-num[e]
max_f = 0

for d in range(41,-2,-1):
    
    if (d != -1 and not (K & 1 << d)):
        continue
    f=0
    
    for e in range(41,-1,-1):
        mask = 1<<e
        if e>d:
            if K&mask:
                f += mask*n_num[e]
            else:
                f += mask*num[e]
        elif e==d:
            f += mask*num[e]
        else:
            f += mask*max(n_num[e],num[e])
    max_f = max(f,max_f)
print(max_f)

Solution (Python):
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
max_A = max(A)
bit = bin(K)
if max_A > K:
    bit = bin(max_A)
max_f = 0
for d in range(1,len(bit))[::-1]:
   
   
    d=d-2
    if (d != -1 and not (K & 1 << d)):
        continue
    f=0
    for e in range(2,len(bit))[::-1]:
        e=e-2
        mask = 1<<e
        num=0
        for a in A:
            if a&mask:
                num+=1
        n_num = N - num
        
        if e>d:
            
            if K&mask:
                f += mask*n_num
            else:
                f += mask*num
        elif e==d:
            f += mask*num
        else:
            f += mask*max(n_num,num)
    max_f = max(f,max_f)
print(max_f)

Solution (Python):
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
"""
N, K = map(int, input().split())
A = [int(x) for x in input().split()]
max_A = max(A)
bit = bin(K)
if max_A > K:
    bit = bin(max_A)"""
max_f = 0

for d in range(41,-2,-1):
    
    if (d != -1 and not (K & 1 << d)):
        continue
    f=0
    
    for e in range(41,-1,-1):
        
        mask = 1<<e
        num=0
        for a in A:
            if a&mask:
                num+=1
        n_num = N - num
        if e>d:
            if K&mask:
                f += mask*n_num
            else:
                f += mask*num
        elif e==d:
            f += mask*num
        else:
            f += mask*max(n_num,num)
    max_f = max(f,max_f)
print(max_f)

Solution (Python):
B='{:041b}'.format
n,k,*a=map(int,open(0).read().split())
if not k:
  print(sum(a))
  exit()
l=[0]*41
for i in a:
  for j,t in enumerate(B(i)):
    if int(t):l[j]+=1
dp=[[0,-1]for i in range(41)]
for i,f in enumerate(map(int,B(k))):
  if not i:continue
  v=pow(2,40-i)
  v0,v1=(n-l[i])*v,l[i]*v
  if f:
    dp[i][0]=dp[i-1][0]+v0
    if dp[i-1][1]>=0:
      dp[i][1]=max(dp[i-1][0]+v1,dp[i-1][1]+max(v0,v1))
    else:
      dp[i][1]=dp[i-1][0]+v1
  else:
    dp[i][0]=dp[i-1][0]+v1
    if dp[i-1][1]>=0:
      dp[i][1]=dp[i-1][1]+max(v0,v1)
print(max(dp[-1]))

Solution (Python):
N,K=map(int,input().split())
A=list(map(int,input().split()))
K=K+1
bk=bin(K)
i=-1
keta1=[]
p2=[2**i for i in range(40)]
while bk[i]!="b":
  if bk[i]=="1":
    keta1.append(-i-1)
  i-=1
  
bk="0"*40+bk[2:]
A.sort(reverse=True)
B=[bin(item) for item in A]
sto=[0 for i in range(40)]
for i in range(N):
  c=-1
  d=0
  while True:
    if B[i][c]=="b":
      break
    elif B[i][c]=="1":
      sto[d]+=1
    c-=1
    d+=1
stos=[]
sums=[0 for i in range(40)]
sumk=[0 for i in range(40)]
for i in range(40):
  l=[sto[i],N-sto[i]]
  sums[i]=(p2[i]*max(l))
  sumk[i]=(p2[i]*l[int(bk[-i-1])])
ans=[]

for i in keta1:
  ans.append(sum(sums[:i])+sum(sumk[i+1:])+p2[i]*sto[i])




print(max(ans))

Solution (Python):





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


ans = 0

for i in range(40, -1, -1):
    
    
    power = 1 << i  
    
    
    bit_count_of_1 = sum(1 for a in A if a & power != 0)  

    
    
    if power > K:
        
        ans += power * bit_count_of_1
        
    elif bit_count_of_1 > N - bit_count_of_1:
        
        ans += power * bit_count_of_1
    else:
        ans += power * (N - bit_count_of_1)
        K -= power  
        
        
        


print(ans)

Solution (Python):





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


ans = 0

for i in range(40, -1, -1):
    
    
    power = 1 << i  
    
    
    bit_count_of_1 = sum(1 for a in A if a & power != 0)  

    
    
    if power > K:
        
        ans += power * bit_count_of_1
        
    elif bit_count_of_1 > N - bit_count_of_1:
        
        ans += power * bit_count_of_1
    else:
        ans += power * (N - bit_count_of_1)
        K -= power

print(ans)

Solution (Python):

"""
https://atcoder.jp/contests/abc117/tasks/abc117_a
"""

def sol_naive(k, S):
    maxi = 0
    for x in range(k+1):
        ttl = 0
        for s in S:
            ttl += (x ^ s)
        maxi = max(maxi, ttl)
    return maxi


def keta(x):
    if x <= 0:
        return 0
    else:
        return 1 + keta(int(x/2))

def bin(x):
    return "{0:08b}".format(x)

def rec(k, S, b_keta, ans): 
    
    if b_keta == 0:
        
        return ans
    else:
        
        ones = 0
        for s in S:
            
            if (1 << (b_keta-1) & s) > 0:
                
                ones += 1
        if ones < len(S) - ones: 
            if ans + (1 << (b_keta-1)) <= k:
                ans += (1 << (b_keta-1))
            
            return rec(k, S, b_keta-1, ans)
        else:
            return rec(k, S, b_keta-1, ans)


def sol(k, S):
    maxi = max(S)
    b_keta = keta(k)
    
    x = rec(k, S, b_keta, 0)
    ans = 0
    for s in S:
        ans += (x ^ s)
    return ans

test = False

if test:
    n, k = 3, 7
    S =list( map(int, "1 6 3".split()))
    print(sol(k, S))

    n, k = 4, 9
    S =list( map(int, "7 4 0 3".split()))
    print(sol(k, S))
    
    n, k = 1, 0
    S =list( map(int, "1000000000000".split()))
    print(sol(k, S))


else:
    n, k = map(int, input().split())
    S =list( map(int, input().split()))
    print(sol(k, S))

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

rtn=0
bit_max = 40
for s in range(bit_max, -1, -1):
  target = 1 << s
  numof_hit = len([1 for a in An if a & target != 0])
  
  if target<=K and numof_hit < N-numof_hit:
    numof_hit = N-numof_hit
    K -= target
  
  rtn += target * numof_hit

print(rtn)

Solution (Python):
n ,k = map(int, input().split())
an = list(map(int, input().split()))
result = 0
def keta(i):
  return len(bin(i)[2:])

for j in range(keta(k), 0, -1):
  cnt = 0
  b = 1 << j-1
  for a in an:
    if a & b != 0:
      cnt += 1
  
  if len(an) - cnt > cnt and k >= b:
    result += b
    k -= b
wanted = 0
for a in an:
  wanted += result ^ a
  
print(wanted)

Solution (Python):
N, K = map(int, input().split())
A = list(map(int, input().split()))
Kb = format(K, 'b')
f = lambda x: sum(a ^ x for a in A)
table = [f(2 ** i) - f(0) for i in range(42)]
candy = {i: x for i, x in enumerate(table) if x > 0 and 2 ** i <= K}
mask = [K]
for i in range(len(Kb) - 1, 0, -1):
    if K & (1 << i):
        mask += [K ^ (1 << i) | ((1 << i) - 1)]
res = 0
for m in mask:
    tmp = 0
    for b in range(42):
        if b in candy and m & (1 << b):
            tmp += candy[b]
    res = max(res, tmp)
print(res + f(0))