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 15:10:35
Task:Bit strings
Sender:Noname 01
Submission time:2016-05-28 15:10:35
Status:READY
Result:ACCEPTED

Show test data

Code

// NONAME-01

#include <bits/stdc++.h>


using namespace std;


vector <int> z, w;
string s;
int n;
int nn;
long long zeros; 

void Load()
{
  cin >> s;
  zeros = 0;
  z.resize(0);
  w.resize(0);
  int cur = 0;
  for (int i = 0; i < (int)s.length(); i++) {
	  if (s[i] == '1') {
		  z.push_back(cur+1);
		  zeros += cur * (cur+1)/2;
		  cur = 0;
	  } else cur++;
  }
  z.push_back(cur+1);
  zeros += cur * (cur+1)/2;
  n = z.size();
  nn = s.length();
  n += nn;  
  z.resize(n, 0);

}

#define Complex complex<long double>

const long double PI = 3.1415926535897932384626433832795;

int Rev(int i, int l) {
 int res = 0;
 int j;
 for (j = 0; j < l; j++) {
  res <<= 1;
  if (i & (1 << j)) res++;
 }
 return res;
}

void FFT(Complex *a, int n, bool inv) {
 int i, j, k;
 int logn = 0;
 while ((1 << logn) < n) logn++;
 for (int i = 0; i < n; i++) {
  j = Rev(i, logn);
  if (j > i) {
	Complex t = a[i];
	a[i] = a[j];
	a[j] = t;
  }
 }
 Complex u, v;
 for (int i = 1; i <= logn; i++) {
  long double ang = 2 * PI / (1 << i);
  if (inv) ang= -ang;
  Complex w(cos(ang), sin(ang));
  for (j = 0; j < n; j += (1 << i)) {
	Complex wk(1, 0);
	for (k = j; k < j + (1 << (i-1)); k++) {
	 u = a[k];
	 v = a[k + (1 << (i-1))] * wk;
	 a[k] = u+v;
	 a[k + (1 << (i-1))] = u-v;
	 wk *= w;
	}
    wk *= w;
  }
 }
 if (inv) {
  for (i = 0; i < n; i++) a[i] /= n;
 }
}


void Solve()
{
  int k = 1;
  while (k < n) k *= 2;
  k *= 2;
  Complex *a = new Complex[k];
  Complex *b = new Complex[k];  
  int i;
  for (i = 0; i < k; i++) {
	if (i < n) {
	  a[i] = Complex(z[i], 0);
	  b[i] = Complex(z[n-1-i], 0);	  
	}
	else {
	  a[i] = b[i] = Complex(0, 0);  
	}
  }
  FFT(a, k, false);
  FFT(b, k, false);  
  for (i = 0; i < k; i++) {
	  a[i] *= b[i];
  }
  FFT(a, k, true);
  cout << zeros << " ";
  for (i = n-2; i >= 0; i--) {
	if (nn == 0) break;
	nn--;
	cout << ((int)(a[i].real()+0.5)) << " ";
  }
  cout << "\n";
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int nt, tt;
  cin >> nt;
  for (tt = 0; tt < nt; tt++) {
  Load();
  Solve();
  }
  return 0;
}