Bit strings

input/code.cpp: In function 'int main()':
input/code.cpp:104:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(a.size() <= n) {
                           ^
input/code.cpp:112:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int64_t i=0;i<a.size();i++) {
                                  ^
input/code.cpp:103:17: warning: unused variable 'tmp' [-Wunused-variable]
         int64_t tmp=a.size();
                 ^

#include<bits/stdc++.h>
 
using namespace std;
 
typedef long double ld;
typedef long long ll;
typedef complex<ld> co;
const ld PI=atan2(0, -1);
 
vector<co> fft(vector<co> x, int d) {
    int n=x.size();
    for(int i=0;i<n;i++) {
        int u=0;
        for(int j=1;j<n;j*=2) {
            u*=2;
            if(i&j) u++;
        }
        if(i<u) {
            swap(x[i], x[u]);
        }
    }
    for(int m=2;m<=n;m*=2) {
        co wm=exp(co{0, d*2*PI/m});
        for(int k=0;k<n;k+=m) {
            co w=1;
            for(int j=0;j<m/2;j++) {
                co t=w*x[k+j+m/2];
                co u=x[k+j];
                x[k+j]=u+t;
                x[k+j+m/2]=u-t;
                w*=wm;
            }
        }
    }
    if(d==-1) {
        for(int i=0;i<n;i++) {
            x[i]/=n;
        }
    }
    return x;
}
 
vector<ll> conv(vector<ll> a, vector<ll> b) {
    int as=a.size();
    int bs=b.size();
    vector<co> aa(as);
    vector<co> bb(bs);
    for(int i=0;i<as;i++) {
        aa[i]=a[i];
    }
    for(int i=0;i<bs;i++) {
        bb[i]=b[i];
    }
    int n=1;
    while(n<as+bs+1) n*=2;
    aa.resize(n*2);
    bb.resize(n*2);
    aa=fft(aa,1);
    bb=fft(bb,1);
    vector<co> c(2*n);
    for(int i=0;i<2*n;i++) {
        c[i]=aa[i]*bb[i];
    }
    c=fft(c,-1);
    c.resize(as+bs-1);
    vector<ll> r(as+bs-1);
    for(int i=0;i<as+bs-1;i++) {
        r[i]=(ll)round(c[i].real());
    }
    return r;
}
 
 
int main(void) {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(12);
 
    int64_t t;
    cin >> t;
    for(;t>0;t--) {
        string s;
        cin >> s;
        int64_t n=s.size();
 
        int64_t bs=0;
        int64_t zeros=0;
 
 
        bs=1;
        vector<ll> a;
        for(int64_t i=0;i<n;i++) {
            if(s[i] == '0') {
                bs++;
            } else {
                zeros+=(bs-1)*bs/2;
                a.push_back(bs);
                bs=1;
            }
        }
        zeros+=(bs-1)*bs/2;
        a.push_back(bs);
        int64_t tmp=a.size();
        while(a.size() <= n) {
            a.push_back(0);
        }
        /*for(int64_t i=0;i<tmp;i++) {
            a.push_back(0);
        }*/
 
        vector<ll> b(a.size());
        for(int64_t i=0;i<a.size();i++) {
            b[i]=a[a.size()-1-i];
        }
        /*for(auto aa: a) {
            cout << aa << " ";
        }
        cout << endl;
        for(auto bb: b) {
            cout << bb << " ";
        }
        cout << endl;*/
 
        cout << zeros << " ";
 
 
        vector<ll> c=conv(a,b);
 
        for(int64_t k=n;k>=1;k--) {
            cout << c[c.size()-k] << " ";
        }
        cout << "\n";
 
    }
 
    return 0;
}
 
 

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED