Code Submission Evaluation System Login

CSES - HIIT Open 2016

HIIT Open 2016

Contest start:2016-05-28 11:00:00
Contest end:2016-05-28 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


History
2016-05-28 13:15:21
2016-05-28 13:04:03
2016-05-28 12:55:38
Task:Bit strings
Sender:Game of Nolife
Submission time:2016-05-28 13:15:21
Status:READY
Result:ACCEPTED

Show test data

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:79:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &tcs);
                   ^
input/code.cpp:81:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
                 ^

Code

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> co;
const ld PI=atan2(0, -1);

vector<co> fft(vector<co> x, int d){
	int n=(int)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();
	int n=1;
	while (n<as+bs-1) n*=2;
	vector<co> aa(n*2);
	vector<co> bb(n*2);
	for (int i=0;i<as;i++){
		aa[i]=a[i];
	}
	for (int i=0;i<bs;i++){
		bb[i]=b[i];
	}
	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;
}

char s[101010];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int tcs;
	scanf("%d", &tcs);
	for (int tc=0;tc<tcs;tc++){
		scanf("%s", s);
		//string s;
		/*
		for (int i=0;i<100000;i++){
			s+='1';
		}*/
		
		int n=strlen(s);
		//int n=s.size();
		vector<ll> ct(n+1);
		ct[0]=1;
		int t=0;
		ll v0=0;
		ll c0=0;
		for (int i=0;i<n;i++){
			if (s[i]=='1') {
				t++;
				c0=0;
			}
			else{
				c0++;
				v0+=c0;
			}
			ct[t]++;
		}
		vector<ll> lol=ct;
		reverse(lol.begin(), lol.end());
		vector<ll> cv=conv(ct, lol);
		printf("%lld ", v0);
		for (int i=n-1;i>=0;i--){
			printf("%lld ", cv[i]);
		}
		printf("\n");
	}
}