Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define int long long
- int mypower(int a, int b, int mod)
- {
- int ans = 1;
- while(b)
- {
- if(b%2 == 1)
- ans = ans*a%mod;
- b=b/2;
- a=a*a%mod;
- }
- return ans;
- }
- signed main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- int i;
- int n;
- cin >> n;
- int pre[n+5];
- pre[0] = 0;
- for(i=1;i<(n+5);i++)
- {
- int j = i, cnt = 0;
- while(j)
- {
- int x = __builtin_popcount(j);
- j=j%x;
- cnt++;
- }
- pre[i] = cnt;
- }
- string x;
- cin >> x;
- int cnt1 = 0;
- for(i=0;i<n;i++)
- if(x[i] == '1')
- cnt1++;
- if(cnt1 == 0)
- {
- // assert(false);
- for(i=0;i<n;i++)
- cout << 1 << '\n';
- return 0;
- }
- if(cnt1 == 1)
- {
- //assert(false);
- if(x[n-1] == '1')
- {
- for(i=0;i<n-1;i++)
- cout << 2 << '\n';
- cout << 0 << '\n';
- }
- else
- {
- for(i=0;i<n-1;i++)
- {
- if(x[i] == '0')
- cout << 1 << '\n';
- else
- cout << 0 << '\n';
- }
- cout << 2 << '\n';
- }
- return 0;
- }
- // cnt1 > 1
- int rem = 0, remf = 0, remb = 0;
- int pw = 1;
- for(i=n-1;i>=0;i--)
- {
- rem = (rem + (x[i] - '0')*pw)%cnt1;
- pw = pw*2%cnt1;
- }
- pw = 1;
- for(i=n-1;i>=0;i--)
- {
- remf = (remf + (x[i] - '0')*pw)%(cnt1+1);
- pw = pw*2%(cnt1+1);
- }
- pw = 1;
- for(i=n-1;i>=0;i--)
- {
- remb = (remb + (x[i] - '0')*pw)%(cnt1-1);
- pw = pw*2%(cnt1-1);
- }
- vector<int> pos_idx[n+5];
- for(i=0;i<n;i++)
- {
- if(x[i] == '0')
- {
- int nrem = (remf + mypower(2, n-1-i, cnt1+1))%(cnt1+1);
- nrem = (nrem + cnt1+1)%(cnt1+1);
- pos_idx[nrem].push_back(i);
- }
- else if(x[i] == '1')
- {
- int nrem = (remb - mypower(2, n-1-i, cnt1-1))%(cnt1-1);
- nrem = (nrem + cnt1-1)%(cnt1-1);
- pos_idx[nrem].push_back(i);
- }
- }
- int ans[n];
- for(i=0;i<n+5;i++)
- {
- for(auto j : pos_idx[i])
- {
- ans[j] = 1 + pre[i];
- }
- }
- for(i=0;i<n;i++)
- cout << ans[i] << '\n';
- }
Add Comment
Please, Sign In to add comment