CSES - Datatähti 2016 alku - Results
Submission details
Task:Tontti
Sender:6502
Submission time:2015-10-02 17:40:25 +0300
Language:C++
Status:READY
Result:47
Feedback
groupverdictscore
#1ACCEPTED14
#2ACCEPTED33
#30
Test results
testverdicttimegroup
#1ACCEPTED0.06 s1details
#2ACCEPTED0.05 s1details
#3ACCEPTED0.06 s1details
#4ACCEPTED0.05 s1details
#5ACCEPTED0.06 s1details
#6ACCEPTED0.31 s2details
#7ACCEPTED0.31 s2details
#8ACCEPTED0.19 s2details
#9ACCEPTED0.21 s2details
#10ACCEPTED0.23 s2details
#11--3details
#12--3details
#13--3details
#14--3details
#15--3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (s = c; s <= mx-1; s++) {
                ^
input/code.cpp:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (o = 1; o <= s; o++)
                   ^
input/code.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (o = 0; o < s; o++, q++, w++)
                    ^
input/code.cpp:71:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (o = 0; o < s; o++, p+=mf) {
                     ^
input/code.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for (w = 0; w < s; w++) {
                      ^
input/code.cpp:96:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (i = n - 1; i >= z;...

Code

#include <iostream>
#include <iterator>
#include <math.h>
#include <stdio.h>
using namespace std;
int main() {
cin.sync_with_stdio(false);
int i, j, n, m, k, x, q, w, o, p, nn, mm, mf;
unsigned sz, s;
cin >> n >> m >> k;
char input[n][m];
nn = 1;
mm = 1;
int v;
v = n;
while (v >>= 1)
{
nn++;
}
v = m;
while (v >>= 1)
{
mm++;
}
mf = 1 << mm;
int kq = mf*(1<<nn);
char a[kq];
int f[kq];
short ag[kq];
short ah[n];
for (i = 0; i < n; i++)
cin >> input[i];
sz = (int)ceil(sqrt((double)k));
x = 0;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++) {
a[(i<<mm)+j] = !(input[i][j]=='.');
f[(i<<mm)+j] = 0;
if(k<2)
x += a[(i<<mm)+j]^k^1;
}
int mx = min(m,n);
unsigned c = max(sz,2u);
int g = 0, h = 0, d, first = 1, scale = 1;
unsigned z;
for (s = c; s <= mx-1; s++) {
//printf("%d ",s);
z = s - 1;
first = 1;
if (s == c) {
for (i = z; i < n; i++) {
w = 0;
q = (i<<mm)+m-1;
for (o = 1; o <= s; o++)
w += a[q-o];
ah[i] = w;
if (i > 0) {
q = i << mm;
w = q - (s << mm);
for (o = 0; o < s; o++, q++, w++)
h += (a[q] - a[w]);
g = h;
}
scale = 0;
for (j = z; j < m; j++) {
d = (i<<mm)+j;
if (scale) {
p = ((i-z)<<mm)+j;
for (o = 0; o < s; o++, p+=mf) {
g += (a[p] - a[p-s]);
}
} else if (first) {
first = 0;
g = f[d];
o = s<<mm;
for (q = 0; q < o; q+=mf) {
for (w = 0; w < s; w++) {
g += a[q+w];
}
}
h = g;
scale = 1;
} else
scale = 1;
f[d] = g;
//printf("s:%d\ti:%d\tj:%d\tn:%d\tm:%d\tf:%d\n",s,i,j,n,m,f[d]);
x += (g == k);
}
}
} else {
int v = (n - 1) << mm;
g = 0;
h = 0;
for (i = n - 1; i >= z; i--) {
j = m - 1;
int d = v+j;
w = f[d-mf-1] + a[d];
g = 0;
h = ah[i];
p = mf;
if (s > c + 1) {
h += a[d-z];
}
for (o = 1; o < s; o++, p+=mf) {
g += a[d-p];
}
ag[d] = g;
ah[i] = h;
w += g + h;
x += (w == k);
f[d] = w;
d--;
j--;
for (; j >= z; j--) {
char ad = a[d];
p = d - mf;
w = f[p-1] + ad;
q = d - (z << mm);
if (i == n - 1) {
g = 0;
for (o = p; o >= q; o -= mf) {
g += a[o];
}
} else {
g = ag[d+mf] + a[q] - ad;
}
h += a[d-z] - ad;
w += g + h;
x += (w == k);
ag[d] = g;
f[d] = w;
d--;
}
v -= mf;
}
/*for (i = n - 1; i >= z; i--) {
q = (i*m);
for (j = m - 1; j >= z; j--)
ag[q+j] = ah[q+j];
}*/
}
/*for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
printf("%d",f[i*m+j]);
}
printf("\n");
}
printf("\n");*/
}
cout << x << "\n";
return 0;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
10 10 1
......*...
.......*..
*..*....*.
*....*....
...

correct output
94

user output
94

Test 2

Group: 1

Verdict: ACCEPTED

input
10 10 5
**********
**********
**********
**********
...

correct output
0

user output
0

Test 3

Group: 1

Verdict: ACCEPTED

input
10 10 10
**...*...*
*..*.**.*.
...**.*..*
*...**.*..
...

correct output
4

user output
4

Test 4

Group: 1

Verdict: ACCEPTED

input
10 10 5
****......
*.*.**..**
....*.*..*
...*.***..
...

correct output
16

user output
16

Test 5

Group: 1

Verdict: ACCEPTED

input
10 10 2
**.***..*.
...*.*....
.***.*...*
***.***..*
...

correct output
30

user output
30

Test 6

Group: 2

Verdict: ACCEPTED

input
500 500 1
.................................

correct output
9552040

user output
9552040

Test 7

Group: 2

Verdict: ACCEPTED

input
500 500 5
.................................

correct output
1536063

user output
1536063

Test 8

Group: 2

Verdict: ACCEPTED

input
500 500 25000
**...*...**..*.*..*.**.*..*.*....

correct output
288

user output
288

Test 9

Group: 2

Verdict: ACCEPTED

input
500 500 12500
**.**.*..*...*.**...*.***........

correct output
786

user output
786

Test 10

Group: 2

Verdict: ACCEPTED

input
500 500 5000
.*.*.**..*.*.**.**..*..**...*....

correct output
1763

user output
1763

Test 11

Group: 3

Verdict:

input
2000 2000 1
.................................

correct output
489611392

user output
(empty)

Test 12

Group: 3

Verdict:

input
2000 2000 5
.................................

correct output
120725884

user output
(empty)

Test 13

Group: 3

Verdict:

input
2000 2000 400000
..*..**.**.**.*.***...**.*..**...

correct output
1849

user output
(empty)

Test 14

Group: 3

Verdict:

input
2000 2000 200000
***.*....*.*..*....**..*..*.*....

correct output
2665

user output
(empty)

Test 15

Group: 3

Verdict:

input
2000 2000 80000
**.**...*.***.**....**.*....*....

correct output
5587

user output
(empty)