Problem p02609 (python)

Fixed submission:
n = int(input())
x = input()

init_pop_cnt = x.count('1')
init_pop_cnt_less = init_pop_cnt - 1
init_pop_cnt_more = init_pop_cnt + 1

valid_l = init_pop_cnt_less != 0

# x's state after f
init_res_less = 0
init_res_more = 0
seed_more = 1
seed_less = 1
for i in range(1, n+1):
  xp = x[-1 * i]
  if xp == '1':
    if valid_l:
      init_res_less += seed_less % init_pop_cnt_less
    init_res_more += seed_more % init_pop_cnt_more
  if valid_l:
    seed_less = (seed_less * 2) % init_pop_cnt_less
  seed_more = (seed_more * 2) % init_pop_cnt_more


dif_less = [0] * (2 * 10**5 + 100)
dif_more = [0] * (2 * 10**5 + 100)
if valid_l:
  dif_less[0] = 1 % init_pop_cnt_less
dif_more[0] = 1 % init_pop_cnt_more
for i in range(1, n+1):
  if valid_l:
    dif_less[i] = (dif_less[i-1] * 2) % init_pop_cnt_less
  dif_more[i] = (dif_more[i-1] * 2) % init_pop_cnt_more


def get_pc(dec):
  out = 0
  while dec > 0:
    if dec % 2 == 1:
      out+=1
    dec = dec // 2
  return out

def f(dec):
  pc = get_pc(dec)
  return dec % pc

cnt = [0] * (2 * 10**5 + 200)

for i in range(1, 2 * 10**5 + 100):
  c = 0
  cur = i
  while cur > 0:
    c += 1
    cur = f(cur)
  cnt[i] = c

for i in range(n):
  xi = x[i]

  if xi == '1':
    if valid_l:
      lx = init_res_less
      lx -= dif_less[n-i-1]
      lx %= init_pop_cnt_less
      print((cnt[lx] % init_pop_cnt_less) + 1)
    else:
      print(0)
  else:
    lx = init_res_more
    lx += dif_more[n-i-1]
    lx %= init_pop_cnt_more
    print((cnt[lx] % init_pop_cnt_more) + 1)

Buggy submission (verdict: Runtime Error):
n = int(input())
x = input()

init_pop_cnt = x.count('1')
init_pop_cnt_less = init_pop_cnt - 1
init_pop_cnt_more = init_pop_cnt + 1

# x's state after f
init_res_less = 0
init_res_more = 0
seed_more = 1
seed_less = 1
for i in range(1, n+1):
  xp = x[-1 * i]
  if xp == '1':
    init_res_less += seed_less % init_pop_cnt_less
    init_res_more += seed_more % init_pop_cnt_more
  seed_less = (seed_less * 2) % init_pop_cnt_less
  seed_more = (seed_more * 2) % init_pop_cnt_more


dif_less = [0] * (2 * 10**5 + 100)
dif_more = [0] * (2 * 10**5 + 100)
dif_less[0] = 1 % init_pop_cnt_less
dif_more[0] = 1 % init_pop_cnt_more
for i in range(1, n+1):
  dif_less[i] = (dif_less[i-1] * 2) % init_pop_cnt_less
  dif_more[i] = (dif_more[i-1] * 2) % init_pop_cnt_more


def get_pc(dec):
  out = 0
  while dec > 0:
    if dec % 2 == 1:
      out+=1
    dec = dec // 2
  return out

def f(dec):
  pc = get_pc(dec)
  return dec % pc

cnt = [0] * (2 * 10**5 + 200)

for i in range(1, 2 * 10**5 + 100):
  c = 0
  cur = i
  while cur > 0:
    c += 1
    cur = f(cur)
  cnt[i] = c


for i in range(n):
  xi = x[i]

  if xi == '1':
    lx = init_res_less
    lx -= dif_less[n-i-1]
    lx %= init_pop_cnt_less
    print((cnt[lx] % init_pop_cnt_less) + 1)
  else:
    lx = init_res_more
    lx += dif_more[n-i-1]
    lx %= init_pop_cnt_more
    print((cnt[lx] % init_pop_cnt_more) + 1)

Buggy submission (verdict: Runtime Error):
n = int(input())
x = input()

outf = {}
res = []

dec_d = {}
def get_dec(bin):
  if bin in dec_d.items():
    return dec_d[bin]
  s = 0
  seed = 2 ** (len(bin)-1)
  for el in bin:
    if el == '1':
      s += seed
    seed = seed // 2
  dec_d[bin] = s
  return s

bin_d = {}
def get_bin(dec):
  if dec in bin_d.items():
    return bin_d[dec]
  s = ''
  while dec > 0:
    if dec % 2 == 1:
      s = s + '1'
    else:
      s = s + '0'
    dec = dec // 2
  bin_d[dec] = s
  return s

pop_d = {}
def popcount(n):
  if n in pop_d.items():
    return pop_d[n]
  out = 0
  while n > 0:
    if n % 2 == 1:
      out += 1
    n = n // 2
  pop_d[n] = out
  return out

init_pop_cnt = popcount(get_dec(x))

for i in range(n):
  if x[i] == '0':
    lx = x[:i] + '1' + x[i+1:]
    ip = init_pop_cnt + 1
  else:
    lx = x[:i] + '0' + x[i+1:]
    ip = init_pop_cnt - 1
  x_dec = get_dec(lx)
  res.append(x_dec)

  kp = []
  f = 0

  # calc first op
  kp.append(x_dec)
  f += 1
  x_dec = x_dec % ip

  # calc f
  while x_dec > 0:
    st = get_bin(x_dec)
    if st in outf.items():
      f += outf[st]
      break
    kp.append(x_dec)
    f += 1
    pc = popcount(x_dec)
    x_dec = x_dec % pc

  # keep
  lf = f
  for k in kp:
    st = get_bin(k)
    outf[st] = lf
    lf -= 1


for i in res:
  st = get_bin(i)
  print(outf[st])

Buggy submission (verdict: Runtime Error):
n = int(input())
x = input()

outf = {}
res = []

dec_d = {}
def get_dec(bin):
  if bin in dec_d.items():
    return dec_d[bin]
  s = 0
  seed = 2 ** (len(bin)-1)
  for el in bin:
    if el == '1':
      s += seed
    seed = seed // 2
  dec_d[bin] = s
  return s

bin_d = {}
def get_bin(dec):
  if dec in bin_d.items():
    return bin_d[dec]
  s = ''
  while dec > 0:
    if dec % 2 == 1:
      s = s + '1'
    else:
      s = s + '0'
    dec = dec // 2
  bin_d[dec] = s
  return s

pop_d = {}
def popcount(n):
  if n in pop_d.items():
    return pop_d[n]
  out = 0
  while n > 0:
    if n % 2 == 1:
      out += 1
    n = n // 2
  pop_d[n] = out
  return out


for i in range(n):
  if x[i] == '0':
    lx = x[:i] + '1' + x[i+1:]
  else:
    lx = x[:i] + '0' + x[i+1:]
  x_dec = get_dec(lx)
  res.append(x_dec)

  # calc f
  kp = []
  f = 0
  while x_dec > 0:
    st = get_bin(x_dec)
    if st in outf.items():
      f += outf[st]
      break
    kp.append(x_dec)
    f += 1
    pc = popcount(x_dec)
    x_dec = x_dec % pc

  # keep
  lf = f
  for k in kp:
    st = get_bin(k)
    outf[st] = lf
    lf -= 1


for i in res:
  st = get_bin(i)
  print(outf[st])

Buggy submission (verdict: Runtime Error):
n = int(input())
x = input()

outf = {}
res = []

dec_d = {}
def get_dec(bin):
  if bin in dec_d.items():
    return dec_d[bin]
  s = 0
  seed = 2 ** (len(bin)-1)
  for el in bin:
    if el == '1':
      s += seed
    seed = seed // 2
  dec_d[bin] = s
  return s

bin_d = {}
def get_bin(dec):
  if dec in bin_d.items():
    return bin_d[dec]
  s = ''
  while dec > 0:
    if dec % 2 == 1:
      s = s + '1'
    else:
      s = s + '0'
    dec = dec // 2
  bin_d[dec] = s
  return s

pop_d = {}
def popcount(n):
  if n in pop_d.items():
    return pop_d[n]
  out = 0
  while n > 0:
    if n % 2 == 1:
      out += 1
    n = n // 2
  pop_d[n] = out
  return out


for i in range(n):
  if x[i] == '0':
    x = x[:i] + '1' + x[i+1:]
  else:
    x = x[:i] + '0' + x[i+1:]
  x_dec = get_dec(x)
  res.append(x_dec)

  # calc f
  kp = []
  f = 0
  while x_dec > 0:
    st = get_bin(x_dec)
    if st in outf.items():
      f += outf[st]
      break
    kp.append(x_dec)
    f += 1
    pc = popcount(x_dec)
    x_dec = x_dec % pc

  # keep
  lf = f
  for k in kp:
    st = get_bin(k)
    outf[st] = lf
    lf -= 1

  if x[i] == '0':
    x = x[:i] + '1' + x[i+1:]
  else:
    x = x[:i] + '0' + x[i+1:]


for i in res:
  st = get_bin(i)
  print(outf[st])

Buggy submission (verdict: Runtime Error):
n = int(input())
x = input()

outf = {}
res = []

dec_d = {}
def get_dec(bin):
  if bin in dec_d.items():
    return dec_d[bin]
  s = 0
  seed = 2 ** (len(bin)-1)
  for el in bin:
    if el == '1':
      s += seed
    seed = seed // 2
  dec_d[bin] = s
  return s

bin_d = {}
def get_bin(dec):
  if dec in bin_d.items():
    return bin_d[dec]
  s = ''
  while dec > 0:
    if dec % 2 == 1:
      s = s + '1'
    else:
      s = s + '0'
    dec = dec // 2
  bin_d[dec] = s
  return s

pop_d = {}
def popcount(n):
  if n in pop_d.items():
    return pop_d[n]
  out = 0
  while n > 0:
    if n % 2 == 1:
      out += 1
    n = n // 2
  pop_d[n] = out
  return out


for i in range(n):
  if x[i] == '0':
    x = x[:i] + '1' + x[i+1:]
  else:
    x = x[:i] + '0' + x[i+1:]
  x_dec = get_dec(x)
  res.append(x_dec)

  # calc f
  kp = []
  f = 0
  while x_dec > 0:
    st = get_bin(x_dec)
    if st in outf.items():
      f += outf[st]
      break
    kp.append(x_dec)
    f += 1
    pc = popcount(x_dec)
    x_dec = x_dec % pc

  # keep
  lf = f
  for k in kp:
    st = get_bin(k)
    outf[st] = lf
    lf -= 1

  if x[i] == '0':
    x = x[:i] + '1' + x[i+1:]
  else:
    x = x[:i] + '0' + x[i+1:]


for i in res:
  st = get_bin(i)
  print(outf[st])

Buggy submission (verdict: Runtime Error):
n = int(input())
x = input()

outf = {}
res = []

def get_dec(bin):
  s = 0
  seed = 2 ** (len(bin)-1)
  for el in bin:
    if el == '1':
      s += seed
    seed = seed // 2
  return s

def get_bin(dec):
  s = ''
  while dec > 0:
    if dec % 2 == 1:
      s = s + '1'
    else:
      s = s + '0'
    dec = dec // 2
  return s

def popcount(n):
  out = 0
  while n > 0:
    if n % 2 == 1:
      out += 1
    n = n // 2
  return out


for i in range(n):
  if x[i] == '0':
    x = x[:i] + '1' + x[i+1:]
  else:
    x = x[:i] + '0' + x[i+1:]
  x_dec = get_dec(x)
  res.append(x_dec)

  # calc f
  kp = []
  f = 0
  while x_dec > 0:
    st = get_bin(x_dec)
    if st in outf.items():
      f += outf[st]
      break
    kp.append(x_dec)
    f += 1
    pc = popcount(x_dec)
    x_dec = x_dec % pc

  # keep
  lf = f
  for k in kp:
    st = get_bin(k)
    outf[st] = lf
    lf -= 1

  if x[i] == '0':
    x = x[:i] + '1' + x[i+1:]
  else:
    x = x[:i] + '0' + x[i+1:]


for i in res:
  st = get_bin(i)
  print(outf[st])