Problem p03138 (python)

Fixed submission:
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,K = MI()
K += 1
k = K.bit_length()
K_bit = [(K >> i) & 1 for i in range(k)]  # Kのbitのリスト(下から)
A = LI()
A_bit = [[(A[i] >> j) & 1 for j in range(k)] for i in range(N)]  # Aiたちのbitのリスト(下から)

X = [0]*(k+1)  # 下i桁で最適なもの
for i in range(k):
    a = sum(A_bit[j][i] == 0 for j in range(N))  # 0の個数
    X[i+1] = X[i]
    if a >= N//2+1:
        X[i+1] += 2**i


def f(x):
    return sum(x^A[i] for i in range(N))


ans = 0
for i in range(k-1,-1,-1):
    if K_bit[i] == 1:
        ans = max(ans,f(((K >> (i+1)) << (i+1))+X[i]))

print(ans)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,K = MI()
K += 1
k = K.bit_length()
K_bit = [(K >> (k-i-1)) & 1 for i in range(k)]
A = LI()
B = [0]*N
ans = 0
for i in range(N):
    a = A[i]
    x = a.bit_length()
    if x > k:
        for j in range(k,x):
            if (a >> j) & 1:
                ans += 1 << j
                a -= 1 << j
    A[i] = a
    B[i] = [(A[i] >> (k-j-1)) & 1 for j in range(k)]

X = [0]*k
for i in range(k):
    a = 0  # 0の個数
    for j in range(N):
        if B[j][i] == 0:
            a += 1
    if a >= k//2+1:
        X[i] = 1
    else:
        X[i] = 0
Y = [0]*k
for i in range(k-2,-1,-1):
    Y[i] = X[i+1] + X[i]*(2**(k-i-1))
Y = Y + [0]


def f(x):
    return sum(x^A[i] for i in range(N))


y = 0
for i in range(k):
    if K_bit[i] == 1:
        y = max(y,f((K >> (k-i) << (k-i))+Y[i+1]))
        if X[i] == 0:
            K -= 1 << (k-i-1)

print(max(ans+y))

Buggy submission (verdict: Runtime Error):
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N,K = LI()
A = LI()

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

k = K.bit_length()

B = []  # 理想

for i in range(k):
    if i == 0:
        if sum(A[j] & 1 for j in range(N)) >= (N+1)//2:
            B.append(0)
        else:
            B.append(1)
    else:
        if sum((A[j] >> i) & 1 for j in range(N)) >= (N+1)//2:
            B.append(B[-1])
        else:
            B.append(B[-1] + (1 << i))

if B[-1] <= K:
    print(sum(B[-1]^A[i] for i in range(N)))
    exit()

ANS = [K,K-1]
a = 0
for i in range(k-1,0,-1):
    if ((K >> i) << i) + B[i-1] <= K:
        ANS.append((K >> i) << i + B[i-1])
    if K >> i == 1:
        ANS.append((K >> (i+1)) << (i+1) + B[i-1])

ans = 0
for x in ANS:
    ans = max(ans,sum(x^A[i] for i in range(N)))

print(ans)

Buggy submission (verdict: Runtime Error):
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

N,K = LI()
A = LI()

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

k = K.bit_length()

B = []  # 理想

for i in range(k):
    if i == 0:
        if sum(A[j] & 1 for j in range(N)) >= (N+1)//2:
            B.append(0)
        else:
            B.append(1)
    else:
        if sum((A[j] >> i) & 1 for j in range(N)) >= (N+1)//2:
            B.append(B[-1])
        else:
            B.append(B[-1] + (1 << i))

if B[-1] <= K:
    print(sum(B[-1]^A[i] for i in range(N)))
    exit()

ANS = [K,K-1]
a = 0
for i in range(k-1,0,-1):
    if (K >> i) << i + B[i-1] <= K:
        ANS.append((K >> i) << i + B[i-1])
    if K >> i == 1:
        ANS.append((K >> (i+1)) << (i+1) + B[i-1])

ans = 0
for x in ANS:
    ans = max(ans,sum(x^A[i] for i in range(N)))

print(ans)