CSES - HIIT Open 2016 - Results
Submission details
Task:Bit strings
Sender:Ace of Spades
Submission time:2016-05-28 13:18:36 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.06 sdetails
#2ACCEPTED0.90 sdetails
#3ACCEPTED0.90 sdetails
#4ACCEPTED0.83 sdetails
#5ACCEPTED0.87 sdetails
#6ACCEPTED0.90 sdetails

Compiler report

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();
                 ^

Code

#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 details

Test 1

Verdict: ACCEPTED

input
20
00011000100111001100
00001001111111100010
10110011110101111101
01111011010010100111
...

correct output
21 33 39 30 23 20 25 7 12 0 0 ...

user output
21 33 39 30 23 20 25 7 12 0 0 ...

Test 2

Verdict: ACCEPTED

input
1
001010110001110001110000110011...

correct output
99028 198023 199224 198569 199...

user output
99028 198023 199224 198569 199...

Test 3

Verdict: ACCEPTED

input
1
111010111001001100100101011110...

correct output
99270 199585 198291 199812 198...

user output
99270 199585 198291 199812 198...

Test 4

Verdict: ACCEPTED

input
20
001001010011101100110111110010...

correct output
5022 10235 10021 9985 10019 99...

user output
5022 10235 10021 9985 10019 99...

Test 5

Verdict: ACCEPTED

input
10
110101000110110101011011101010...

correct output
9955 20073 20158 19923 20014 1...

user output
9955 20073 20158 19923 20014 1...

Test 6

Verdict: ACCEPTED

input
1
111111111111111111111111111111...

correct output
968 100966 100967 100965 10096...

user output
968 100966 100967 100965 10096...