Problem p02609 (python)

Fixed submission:
# coding: utf-8
from collections import defaultdict, deque


def popcount(x):
    assert x.bit_length() <= 32
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f


def solve(*args: str) -> str:
    n = int(args[0])
    x = args[1]

    ret = []
    dp = defaultdict(int)
    x_count = x.count('1')
    x_dec = int(x, 2)

    x_mod_set = x_dec % (x_count+1)
    xor_set = 1 % (x_count+1)
    if 1 < x_count:
        x_mod_reset = x_dec % (x_count-1)
        xor_reset = 1 % (x_count-1)

    for i in range(n):
        bitcount = x_count + (1 if x[-1-i] == '0' else -1)
        if bitcount == 0:
            ret.append(str(0))
            continue

        m = (x_mod_set + xor_set
             if x[-1-i] == '0' else
             x_mod_reset - xor_reset) % bitcount
        deq = deque([m])

        count = 1
        while m:
            deq.append(m)
            if 0 < dp[m]:
                count += dp[m]
                break

            m = m % popcount(m)
            count += 1

        ret.append(str(count))

        while deq:
            dp[deq.popleft()] = count
            count -= 1

        xor_set = (xor_set << 1) % (x_count+1)
        if 1 < x_count:
            xor_reset = (xor_reset << 1) % (x_count-1)

    return '\n'.join(ret[::-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Buggy submission (verdict: Runtime Error):
# coding: utf-8
from collections import defaultdict, deque


def popcount(x):
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f


def solve(*args: str) -> str:
    n = int(args[0])
    x = args[1]

    ret = []
    dp = defaultdict(int)
    x_count = x.count('1')
    x_dec = int(x, 2)

    x_mod_set = x_dec % (x_count+1)
    x_mod_reset = x_dec % (x_count-1)
    xor_set = 1 % (x_count+1)
    xor_reset = 1 % (x_count-1)
    for i in range(n):
        bitcount = x_count + (1 if x[-1-i] == '0' else -1)
        if bitcount == 0:
            ret.append(0)
            continue

        m = (x_mod_set + xor_set
             if x[-1-i] == '0' else
             x_mod_reset - xor_reset) % bitcount
        deq = deque([m])

        count = 1
        while m:
            deq.append(m)
            if 0 < dp[m]:
                count += dp[m]
                break

            m = m % popcount(m)
            count += 1

        ret.append(str(count))

        while deq:
            dp[deq.popleft()] = count
            count -= 1

        xor_set = (xor_set << 1) % (x_count+1)
        xor_reset = (xor_reset << 1) % (x_count-1)

    return '\n'.join(ret[::-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Buggy submission (verdict: Runtime Error):
# coding: utf-8
from collections import defaultdict, deque


def popcount(x):
    assert x.bit_length() <= 32
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f


def solve(*args: str) -> str:
    n = int(args[0])
    x = args[1]

    ret = []
    dp = defaultdict(int)
    x_count = x.count('1')
    x_dec = int(x, 2)

    x_mod_set = x_dec % (x_count+1)
    x_mod_reset = x_dec % (x_count-1)
    xor_set = 1 % (x_count+1)
    xor_reset = 1 % (x_count-1)
    for i in range(n):
        bitcount = x_count + (1 if x[-1-i] == '0' else -1)
        if bitcount == 0:
            ret.append(0)
            continue

        m = (x_mod_set + xor_set
             if x[-1-i] == '0' else
             x_mod_reset - xor_reset) % bitcount
        deq = deque([m])

        count = 1
        while m:
            deq.append(m)
            if 0 < dp[m]:
                count += dp[m]
                break

            m = m % popcount(m)
            count += 1

        ret.append(str(count))

        while deq:
            dp[deq.popleft()] = count
            count -= 1

        xor_set = (xor_set << 1) % (x_count+1)
        xor_reset = (xor_reset << 1) % (x_count-1)

    return '\n'.join(ret[::-1])


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))