Problem p02609 (python)

Fixed submission:
N = int(input())
X = input()

X_int = int(X, 2)
cnt1 = bin(X_int).count('1')
pcXi01 = cnt1 + 1
pcXi10 = cnt1 - 1
zero_idx = N + 5
if cnt1 == 1:
  for i in range(N):
    if X[i] == '1':
      zero_idx = i

if pcXi10 < 1:
  pcXi10 = 1
Xmod01 = X_int % pcXi01
Xmod10 = X_int % pcXi10

tmp01 = [1]
tmp10 = [-1]
for i in range(N - 1):
  tmp01.append(tmp01[i]*2 % pcXi01)
  tmp10.append(tmp10[i]*2 % pcXi10)

init_n = [0] * N
next_n = [0] * N
for i in range(N):
  if X[i] == '0':
    next_n[i] = (Xmod01 + tmp01[N - 1 - i]) % pcXi01
  else:
    next_n[i] = (Xmod10 + tmp10[N - 1 - i]) % pcXi10

for i in range(N):
  fn = 0
  if i == zero_idx:
    print(0)
    continue

  n = next_n[i]
  fn += 1
  while n != 0:
    n = n % bin(n).count('1')
    fn += 1
  
  print(fn)

Buggy submission (verdict: Runtime Error):
import copy

N = int(input())
X = input()

plus = bin(int(X, 2)).count('1') + 1
minus = bin(int(X, 2)).count('1') - 1

init_n = [0] * N
init_X = [0] * N
for i in range(N):
  X_list = list(X)
  if X_list[i] == '0':
    X_list[i] = '1'
    first = plus
  else:
    X_list[i] = '0'
    first = minus
  X_str = ''.join(X_list)
  init_n[i] = int(X_str, 2)
  init_X[i] = init_n[i] % first

for i in range(N):
  
  fn = 0
  n = init_n[i]
  if n != 0:
    n = init_X[i]
    fn += 1
  while n != 0:
    n = n % bin(n).count('1')
    fn += 1
  
  print(fn)

Buggy submission (verdict: Runtime Error):
import copy

N = int(input())
X = input()

plus = bin(int(X, 2)).count('1') + 1
minus = bin(int(X, 2)).count('1') - 1

init_n = [0] * N
init_X = [0] * N
for i in range(N):
  X_list = list(X)
  if X_list[i] == '0':
    X_list[i] = '1'
    first = plus
  else:
    X_list[i] = '0'
    first = minus
  X_str = ''.join(X_list)
  init_n[i] = int(X_str, 2)
  init_X[i] = init_n[i] % first

for i in range(N):
  
  fn = 0
  if init_n[i] != 0:
    n = init_X[i]
    fn += 1
  while n != 0:
    n = n % bin(n).count('1')
    fn += 1
  
  print(fn)

Buggy submission (verdict: Runtime Error):
N = int(input())
X = input()

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

for i in range(N):
  
  X_list = list(X)
  if X_list[i] == '0':
    X_list[i] = '1'
  else:
    X_list[i] = '0'
  
  X_str = ''.join(X_list)
  n = int(X_str, 2)
  fn = 0
  while n != 0:
    n = n % popcount(n)
    fn += 1
  
  print(fn)

Buggy submission (verdict: Runtime Error):
import copy

N = int(input())
X = int(input(), 2)

def rev(num, i):
  i = N - 1 - i
  return num ^ (1 << i)



def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f



for i in range(N):
  n = rev(X, i)
  cnt = 0
  
  while n != 0:
    n = n % popcount(n)
    cnt += 1
  print(cnt)

Buggy submission (verdict: Runtime Error):
import copy

N = int(input())
X = int(input(), 2)

def rev(num, i):
  i = N - 1 - i
  return num ^ (1 << i)



def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f



for i in range(N):
  X = rev(X, i)
    
  fn = copy.deepcopy(X)
  cnt = 0
  
  while fn != 0:
    fn = fn % popcount(fn)
    cnt += 1
  print(cnt)
  
  X = rev(X, i)

Buggy submission (verdict: Runtime Error):
N = int(input())
X = int(input(), 2)

def rev(num, i):
  i = N - 1 - i
  return num ^ (1 << i)



def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f



for i in range(N):
  X = rev(X, i)
    
  fn = X
  cnt = 0
  
  while fn != 0:
    fn = fn % popcount(fn)
    cnt += 1
  print(cnt)
  
  X = rev(X, i)