HIIT Open 2016

 Start: 2016-05-28 11:00:00 End: 2016-05-28 16:00:00

CSES - HIIT Open 2016 - Results
History
2016-05-28 15:10:35
 Task: Bit strings Sender: Noname 01 Submission time: 2016-05-28 15:10:35 Language: C++ Status: READY Result: ACCEPTED

Test results

 test verdict time (s) #1 ACCEPTED 0.05 / 1.00 details #2 ACCEPTED 0.95 / 1.00 details #3 ACCEPTED 0.94 / 1.00 details #4 ACCEPTED 0.42 / 1.00 details #5 ACCEPTED 0.44 / 1.00 details #6 ACCEPTED 0.95 / 1.00 details

Code

```// NONAME-01

#include <bits/stdc++.h>

using namespace std;

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

{
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++) {
Solve();
}
return 0;
}```

Test details

Test 1

Verdict: ACCEPTED

input
```20 00011000100111001100 00001001111111100010 10110011110101111101 01111011010010100111 11000011001100111001 10110000100010000001 01010110010000010110 00000010111100110011 11011010110110100000 00011011110110011011 01011010001001101010 10011110110011100111 10111000001100000011 01111001000010001000 01011110110010000111 01111000111011001001 01011100100001110010 11011001101100111001 00010111001111111111 ...```
view   save

correct output
```21 33 39 30 23 20 25 7 12 0 0 ... 20 36 19 18 17 16 15 14 19 26 ... 7 27 25 22 21 21 19 16 12 10 1... 10 33 32 29 24 21 17 15 11 9 4... 19 30 39 26 29 20 15 18 9 4 1 ... 38 64 54 25 19 9 1 0 0 0 0 0 0... 23 47 34 37 29 20 10 6 4 0 0 0... 28 31 27 20 21 28 15 24 9 7 0 ... 20 31 26 28 20 24 19 13 15 8 6... 12 25 31 21 22 17 21 13 19 9 1... 15 41 32 33 33 22 12 10 8 4 0 ... 10 27 26 27 22 21 21 14 11 13 ... 37 32 60 28 22 17 10 3 1 0 0 0... 26 58 43 26 19 18 12 8 0 0 0 0... 16 37 28 29 21 18 17 19 14 5 4... 14 32 27 27 24 22 21 15 9 10 7... 19 40 25 34 37 22 9 10 10 4 0 ... 11 28 31 27 27 19 18 17 12 9 6... 10 26 21 22 25 16 15 14 13 12 ... 25 35 29 22 24 19 14 ...```
view   save

user output
```21 33 39 30 23 20 25 7 12 0 0 ... 20 36 19 18 17 16 15 14 19 26 ... 7 27 25 22 21 21 19 16 12 10 1... 10 33 32 29 24 21 17 15 11 9 4... 19 30 39 26 29 20 15 18 9 4 1 ... 38 64 54 25 19 9 1 0 0 0 0 0 0... 23 47 34 37 29 20 10 6 4 0 0 0... 28 31 27 20 21 28 15 24 9 7 0 ... 20 31 26 28 20 24 19 13 15 8 6... 12 25 31 21 22 17 21 13 19 9 1... 15 41 32 33 33 22 12 10 8 4 0 ... 10 27 26 27 22 21 21 14 11 13 ... 37 32 60 28 22 17 10 3 1 0 0 0... 26 58 43 26 19 18 12 8 0 0 0 0... 16 37 28 29 21 18 17 19 14 5 4... 14 32 27 27 24 22 21 15 9 10 7... 19 40 25 34 37 22 9 10 10 4 0 ... 11 28 31 27 27 19 18 17 12 9 6... 10 26 21 22 25 16 15 14 13 12 ... 25 35 29 22 24 19 14 ...```
view   save

Test 2

Verdict: ACCEPTED

input
```1 001010110001110001110000110011...```
view   save

correct output
`99028 198023 199224 198569 199...`
view   save

user output
`99028 198023 199224 198569 199...`
view   save

Test 3

Verdict: ACCEPTED

input
```1 111010111001001100100101011110...```
view   save

correct output
`99270 199585 198291 199812 198...`
view   save

user output
`99270 199585 198291 199812 198...`
view   save

Test 4

Verdict: ACCEPTED

input
```20 001001010011101100110111110010...```
view   save

correct output
`5022 10235 10021 9985 10019 99...`
view   save

user output
`5022 10235 10021 9985 10019 99...`
view   save

Test 5

Verdict: ACCEPTED

input
```10 110101000110110101011011101010...```
view   save

correct output
`9955 20073 20158 19923 20014 1...`
view   save

user output
`9955 20073 20158 19923 20014 1...`
view   save

Test 6

Verdict: ACCEPTED

input
```1 111111111111111111111111111111...```
view   save

correct output
`968 100966 100967 100965 10096...`
view   save

user output
`968 100966 100967 100965 10096...`
view   save