Problem p02609 (python)

Fixed submission:
from collections import deque
N = int(input())
X = str(input())
X = list(X)
#motokosu = X.count("1")
motokosu = 0
only = float("inf")
for i in range(N):
  if X[i] == "1":
    motokosu += 1
    only = i
if motokosu != 1:
  only = float("inf")
#print(motosuji,motokosu)
MAX = 2*pow(10,5)+10
base = [0 for _ in range(MAX)] #0から19までの答えを保存
for i in range(MAX):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(len(bin(now))-2):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    #print(now,base[now])
    base[i] = base[now] + 1
    break
    #temp += 1
  #base[i] = temp
#print(base)
A = []
pkosu = motokosu+1
mkosu = motokosu-1
P = deque([])
M = deque([])
ptemp = 1; mtemp = 1
for i in range(N):
  P.appendleft(ptemp%pkosu)
  ptemp = ptemp*2%pkosu
  if mkosu < 1:
    M.appendleft(0)
  else:
    M.appendleft(mtemp%mkosu)
    mtemp = mtemp*2%mkosu

pmotosuji = 0; mmotosuji = 0
for i in range(N):
  if X[i] == "1":
    pmotosuji = (pmotosuji+P[i])%pkosu
    if mkosu >= 1:
      mmotosuji = (mmotosuji+M[i])%mkosu
#print(P,M,pkosu,mkosu,pmotosuji,mmotosuji)

for i in range(N): #i桁目を入れ替える
  if only == i:
    print(0)
    continue
  if X[i] == "0": #その桁が0なら1にする
    kosu = motokosu + 1
    suji = (pmotosuji + P[i])%kosu
  else: #その桁が1なら0にする
    kosu = motokosu - 1
    if kosu == 0:
      suji = -1
    else:
      suji = (mmotosuji - M[i])%kosu
    
  #print(suji,kosu)
  #if suji == 0:
  #  ans = 0
  if suji == -1:
    ans = 1
  else:
    nxt = suji%kosu
    ans = 1+base[nxt]
  #A.append(ans)
  print(ans)

#print(*A,sep="\n")
#print(2**17)
#print(motokosu)

Buggy submission (verdict: Runtime Error):
N = int(input())
S = str(input())
X = [];Bit = 0;Num = 0
for i in range(N):
  if S[i] == "1":
    Bit += 1
    Num += pow(2,N-1-i)
  X.append(int(S[i]))
#print(X)
#print(Num)
MAX = 2*pow(10,5)+10
small = [-1 for _ in range(MAX)]
small[0] = 0; small[1] = 1; small[2] = 1; small[3] = 2
for i in range(4,MAX):
  ret = 0; target = i*1
  while i > 0:
    cnt = 0
    for j in range(i.bit_length()):
      if (i>>j)&1 == 1:
        cnt += 1
    i = i%cnt
    #print(i,target,cnt)
    ret += 1
    if small[i] != -1:
      ret += small[i]
      break

  small[target] = ret
#print(small)
Numm = Num%(Bit-1)
Nump = Num%(Bit+1)
#print(Num)
ans = []
for i in range(N):
  keta = N-1-i
  if X[i] == 1:
    btemp = Bit -1
    temp = (Numm - pow(2,keta,btemp))%btemp
  else:
    btemp = Bit +1
    temp = (Nump + pow(2,keta,btemp))%btemp
  ret = small[temp] + 1 #最初の一回
  ans.append(ret)
print(*ans,sep="\n")

Buggy submission (verdict: Runtime Error):
N = int(input())
S = str(input())
X = [];Bit = 0
for i in range(N):
  if S[i] == "1":
    Bit += 1
  X.append(int(S[i]))
#print(X)
MAX = 21
small = [-1 for _ in range(MAX)]
small[0] = 0; small[1] = 1; small[2] = 1; small[3] = 2
for i in range(4,MAX):
  ret = 0; target = i*1
  while i > 0:
    cnt = 0
    for j in range(i.bit_length()):
      if (i>>j)&1 == 1:
        cnt += 1
    i = i%cnt
    #print(i,target,cnt)
    ret += 1
    if small[i] != -1:
      ret += small[i]
      break

  small[target] = ret
#print(small)
Num = int(S, 2)
#print(Num)
ans = []
for i in range(N):
  keta = N-1-i
  if X[i] == 1:
    temp = Num - pow(2,keta)
    btemp = Bit -1 
  else:
    temp = Num + pow(2,keta)
    btemp = Bit + 1
  nokori = temp%btemp
  ret = small[nokori] + 1 #最初の一回
  ans.append(ret)
print(*ans,sep="\n")

Buggy submission (verdict: Runtime Error):
N = int(input())
X = str(input())
motosuji = int(X,2)
X = list(X)
motokosu = X.count("1")
#print(motosuji,motokosu)

base = [0 for _ in range(20)] #0から19までの答えを保存
for i in range(20):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(5):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    temp += 1
  base[i] = temp
#print(base)
A = []
for i in range(N): #i桁目を入れ替える
  if X[i] == "0": #その桁が0なら1にする
    suji = motosuji + pow(2,N-1-i)
    kosu = motokosu + 1
  else: #その桁が1なら0にする
    suji = motosuji - pow(2,N-1-i)
    kosu = motokosu - 1
    
  #print(suji,kosu)
  if suji == 0:
    nxt = 0
  else:
    nxt = suji%kosu
  ans = 1+base[nxt]
  A.append(ans)

print(*A,sep="\n")

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

base = [0 for _ in range(20)] #0から19までの答えを保存
for i in range(20):
  now = i
  temp = 0
  while now != 0:
    ones = 0
    tnow = now*1
    for t in range(5):
      if (now>>t)&1 == 1:
        ones += 1
    #print(i,ones,now)
    now = now%ones
    temp += 1
  base[i] = temp
#print(base)
A = []
for i in range(N): #i桁目を入れ替える
  suji = 0
  onekazu = 0
  for j in range(N):
    if i != j and X[j] == "1":
      suji += pow(2,N-1-j)
      onekazu += 1
    elif i == j and X[j] == "0":
      suji += pow(2,N-1-j)
      onekazu += 1
  #print(suji,onekazu)
  #if suji == 0:
  #  nxt = 0
  nxt = suji%onekazu
  ans = 1+base[nxt]
  A.append(ans)

print(*A,sep="\n")