Advertisement
skaram

Untitled

Sep 17th, 2023
807
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.85 KB | None | 0 0
  1. n = int(input())
  2. s = input()
  3. x = int(s, 2)
  4. g = 0
  5. for i in s:
  6.     if i == '1':
  7.         g += 1
  8. if g == 1:
  9.     for i in s:
  10.         if i == '1':
  11.             print(0)
  12.         else:
  13.             print(1)
  14.     exit(0)
  15. if g == 0:
  16.     print("1\n" * n)
  17.     exit(0)
  18. a = x % (g - 1)
  19. ap = 1
  20. c = x % (g + 1)
  21. cp = 1
  22. ans = []
  23. shit = [0]
  24. for i in range(1, 200100):
  25.     shit.append(0)
  26.     k = 1
  27.     while k <= i:
  28.         if i & k:
  29.             shit[i] += 1
  30.         k *= 2
  31. for i in range(n - 1, -1, -1):
  32.     if s[i] == '0':
  33.         b = (c + cp) % (g + 1)
  34.     else:
  35.         b = (a - ap) % (g - 1)
  36.     cnt = 1
  37.     while True:
  38.         h = shit[b]
  39.         if h == 0:
  40.             ans.append(cnt)
  41.             break
  42.         cnt += 1
  43.         b %= h
  44.     ap = 2 * ap % (g - 1)
  45.     cp = 2 * cp % (g + 1)
  46. for i in range(len(ans) - 1, -1, -1):
  47.     print(ans[i])
  48.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement