Problem p03138 (python)

Fixed submission:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    l = []
    for _ in range(40):
        cnt = 0
        for i in range(n):
            if a[i] & 1:
                cnt += 1
            a[i] >>= 1
        l.append(cnt)

    pows = [1]
    for _ in range(39):
        pows.append(pows[-1] * 2)

    if k == 0:
        print(sum([l[i] * pows[i] for i in range(40)]))
        exit()

    # when it does not use the biggest bit of k
    ans1 = 0
    for i in range(k.bit_length() - 1):
        if l[i] < n - l[i]:
            ans1 += (n - l[i]) * pows[i]
        else:
            ans1 += l[i] * pows[i]
    for i in range(k.bit_length() - 1, 40):
        ans1 += l[i] * pows[i]

    # when it use the biggest bit of k
    ans2 = 0
    ans3 = 0
    for i in range(40):
        if l[i] < n - l[i]:
            if k & 1:
                ans2 += (n - l[i]) * pows[i]
            else:
                ans2 += l[i] * pows[i]
            ans3 += (n - l[i]) * pows[i]
        else:
            if k & 1:
                ans2 = ans3 + l[i] * pows[i]
            else:
                ans2 += l[i] * pows[i]
            ans3 += l[i] * pows[i]
        k >>= 1

    print(max(ans1, ans2))

main()

Buggy submission (verdict: Runtime Error):
from sys import setrecursionlimit
setrecursionlimit(10**9)

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

    l = []
    for _ in range(40):
        cnt = 0
        for i in range(n):
            if a[i] & 1:
                cnt += 1
            a[i] >>= 1
        l.append(cnt)

    pows = [1]
    for _ in range(39):
        pows.append(pows[-1] * 2)

    right = 40

    def solve(k, right):
        if right == 0:
            return 0

        left = k.bit_length()
        x = 0
        y = 0
        for i in range(left):
            if l[i] < n - l[i]:
                x += pows[i]
                y += (n - l[i]) * pows[i]
            else:
                y += l[i] * pows[i]
        for i in range(left, right):
            y += l[i] * pows[i]

        if x <= k:
            return y
        else:
            return max(y - (n-2*l[right-1]) * pows[right-1], (n - l[i]) * pows[right-1] + solve(k - pows[right-1], left))

    print(solve(k, right))

main()

Buggy submission (verdict: Runtime Error):
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    l = []
    for _ in range(40):
        cnt = 0
        for i in range(n):
            if a[i] & 1:
                cnt += 1
            a[i] >>= 1
        l.append(cnt)

    pows = [1]
    for _ in range(39):
        pows.append(pows[-1] * 2)

    right = 40

    def solve(k, right):
        if right == 0:
            return 0

        left = k.bit_length()
        x = 0
        y = 0
        for i in range(left):
            if l[i] < n - l[i]:
                x += pows[i]
                y += (n - l[i]) * pows[i]
            else:
                y += l[i] * pows[i]
        for i in range(left, right):
            y += l[i] * pows[i]

        if x <= k:
            return y
        else:
            return max(y - (n-2*l[right-1]) * pows[right-1], (n - l[i]) * pows[right-1] + solve(k - pows[right-1], left))

    print(solve(k, right))

main()

Buggy submission (verdict: Runtime Error):
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    l = []
    for _ in range(40):
        cnt = 0
        for i in range(n):
            if a[i] & 1:
                cnt += 1
            a[i] >>= 1
        l.append(cnt)

    pows = [1]
    for _ in range(39):
        pows.append(pows[-1] * 2)

    right = 40

    def solve(k, right):
        if right == 0:
            return 0

        left = k.bit_length()
        x = 0
        y = 0
        for i in range(left):
            if l[i] < n - l[i]:
                x += pows[i]
                y += (n - l[i]) * pows[i]
            else:
                y += l[i] * pows[i]
        for i in range(left, right):
            y += l[i] * pows[i]

        if x <= k:
            return y
        else:
            return max(y - (n-2*l[right-1]) * pows[right-1], (n - l[i]) * pows[right-1] + solve(k - pows[right-1], left-1))

    print(solve(k, right))

main()

Buggy submission (verdict: Runtime Error):
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    l = []
    for _ in range(40):
        cnt = 0
        for i in range(n):
            if a[i] & 1:
                cnt += 1
            a[i] >>= 1
        l.append(cnt)

    pows = [1]
    for _ in range(39):
        pows.append(pows[-1] * 2)

    right = k.bit_length()

    y = 0
    for i in range(right, 40):
        y += l[i] * pows[i]

    def solve(k, right):
        x = 0
        y = 0
        for i in range(right):
            if l[i] < n - l[i]:
                x += pows[i]
                y += (n - l[i]) * pows[i]
            else:
                y += l[i] * pows[i]

        if x <= k:
            return y

        else:
            return max(y - (n-2*l[right-1]) * pows[right-1], (n - l[i]) * pows[right-1] + solve(k - pows[right-1], right-1))

    print(y + solve(k, right))

main()