Guest User

Untitled

a guest
Jul 14th, 2020
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.45 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6.  
  7.  
  8. int mypower(int a, int b, int mod)
  9. {
  10.     int ans = 1;
  11.     while(b)
  12.     {
  13.         if(b%2 == 1)
  14.             ans = ans*a%mod;
  15.         b=b/2;
  16.         a=a*a%mod;
  17.     }
  18.     return ans;
  19. }
  20. signed main() {
  21.     ios_base::sync_with_stdio(false);
  22.     cin.tie(0);
  23.     int i;
  24.     int n;
  25.     cin >> n;
  26.     int pre[n+5];
  27.     pre[0] = 0;
  28.     for(i=1;i<(n+5);i++)
  29.     {
  30.         int j = i, cnt = 0;
  31.         while(j)
  32.         {
  33.             int x = __builtin_popcount(j);
  34.             j=j%x;
  35.             cnt++;
  36.         }
  37.         pre[i] = cnt;
  38.     }
  39.     string x;
  40.     cin >> x;
  41.     int cnt1 = 0;
  42.     for(i=0;i<n;i++)
  43.         if(x[i] == '1')
  44.             cnt1++;
  45.     if(cnt1 == 0)
  46.     {
  47.        // assert(false);
  48.         for(i=0;i<n;i++)
  49.             cout << 1 << '\n';
  50.         return 0;
  51.     }
  52.     if(cnt1 == 1)
  53.     {
  54.         //assert(false);
  55.         if(x[n-1] == '1')
  56.         {
  57.             for(i=0;i<n-1;i++)
  58.                 cout << 2 << '\n';
  59.             cout << 0 << '\n';
  60.         }
  61.         else
  62.         {
  63.             for(i=0;i<n-1;i++)
  64.             {
  65.                 if(x[i] == '0')
  66.                     cout << 1 << '\n';
  67.                 else
  68.                     cout << 0 << '\n';
  69.             }
  70.             cout << 2 << '\n';
  71.         }
  72.         return 0;
  73.     }
  74.     // cnt1 > 1
  75.     int rem = 0, remf = 0, remb = 0;
  76.     int pw = 1;
  77.     for(i=n-1;i>=0;i--)
  78.     {
  79.         rem = (rem + (x[i] - '0')*pw)%cnt1;
  80.         pw = pw*2%cnt1;
  81.     }
  82.     pw = 1;
  83.     for(i=n-1;i>=0;i--)
  84.     {
  85.         remf = (remf + (x[i] - '0')*pw)%(cnt1+1);
  86.         pw = pw*2%(cnt1+1);
  87.     }
  88.     pw = 1;
  89.     for(i=n-1;i>=0;i--)
  90.     {
  91.         remb = (remb + (x[i] - '0')*pw)%(cnt1-1);
  92.         pw = pw*2%(cnt1-1);
  93.     }
  94.     vector<int> pos_idx[n+5];
  95.     for(i=0;i<n;i++)
  96.     {
  97.         if(x[i] == '0')
  98.         {
  99.             int nrem = (remf + mypower(2, n-1-i, cnt1+1))%(cnt1+1);
  100.             nrem = (nrem + cnt1+1)%(cnt1+1);
  101.             pos_idx[nrem].push_back(i);
  102.         }
  103.         else if(x[i] == '1')
  104.         {
  105.             int nrem = (remb - mypower(2, n-1-i, cnt1-1))%(cnt1-1);
  106.             nrem = (nrem + cnt1-1)%(cnt1-1);
  107.             pos_idx[nrem].push_back(i);
  108.         }
  109.     }
  110.     int ans[n];
  111.     for(i=0;i<n+5;i++)
  112.     {
  113.         for(auto j : pos_idx[i])
  114.         {
  115.             ans[j] = 1 + pre[i];
  116.         }
  117.     }
  118.     for(i=0;i<n;i++)
  119.         cout << ans[i] << '\n';
  120. }
Add Comment
Please, Sign In to add comment