CSES - Datatähti 2016 alku - Results
Submission details
Task:Tontti
Sender:Destroy();
Submission time:2015-10-10 22:59:29 +0300
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED14
#2ACCEPTED33
#3ACCEPTED53
Test results
testverdicttimegroup
#1ACCEPTED0.05 s1details
#2ACCEPTED0.06 s1details
#3ACCEPTED0.05 s1details
#4ACCEPTED0.06 s1details
#5ACCEPTED0.05 s1details
#6ACCEPTED0.08 s2details
#7ACCEPTED0.07 s2details
#8ACCEPTED0.07 s2details
#9ACCEPTED0.07 s2details
#10ACCEPTED0.07 s2details
#11ACCEPTED0.90 s3details
#12ACCEPTED0.90 s3details
#13ACCEPTED0.71 s3details
#14ACCEPTED0.76 s3details
#15ACCEPTED0.82 s3details

Code

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int korkeus, leveys, puut;
int summataulukko[2000][2000];
int vakio;
void readInput(int x, int y);
int lasku(int i, int j, int korkeus, int leveys, int puut);
int summataulukkolaske(int x1, int y1, int x2, int y2);
int binarysearch(int maksimi, int x1, int y1, int x2, int y2);
int main()
{
ios_base::sync_with_stdio(0);
cin >> korkeus >> leveys >> puut;
readInput(leveys, korkeus);
int lkm = 0;
for (int j = 0; j < korkeus; j++)
{
for (int i = 0; i < leveys; i++)
{
lkm = lkm + lasku(i, j, korkeus, leveys, puut);
}
}
cout << lkm;
cin.get();
cin.get();
}
void readInput(int x, int y)
{
for (int j = 0; j < y; j++)
{
for (int i = 0; i < x; i++)
{
char a;
cin >> a;
vakio = 0;
if (a == '*')
{
vakio = 1;
}
if (i == 0 && j == 0)
{
summataulukko[i][j] = vakio;
}
else if (i == 0)
{
summataulukko[i][j] = summataulukko[i][j - 1] + vakio;
}
else if (j == 0)
{
summataulukko[i][j] = summataulukko[i - 1][j] + vakio;
}
else
{
summataulukko[i][j] = summataulukko[i - 1][j] + summataulukko[i][j - 1] + vakio - summataulukko[i - 1][j - 1];
}
}
}
}
int lasku(int i, int j, int korkeus, int leveys, int puut)
{
int maksimi = min(korkeus - j, leveys - i);
int pituus = 0;
//int nykyisetpuut = 0;
//int lasku = 0;
int maxhyppy = 0;
int minhyppy = 0;
bool maxfound = false;
for (int b = maksimi / 2; b >= 1; b /= 2)
{
while (pituus + b < maksimi && summataulukkolaske(i + pituus + b, j + pituus + b, i, j) <= puut) pituus += b;
}
if (summataulukkolaske(i + pituus, j + pituus, i, j) == puut)
{
maxhyppy = pituus;
maxfound = true;
}
//cout << pituus << '\n';
for (int b = maksimi / 2; b >= 1; b /= 2)
{
while (pituus - b >= 0 && summataulukkolaske(i+pituus-b, j+pituus-b, i, j) >= puut) pituus -= b;
}
if (summataulukkolaske(i + pituus, j + pituus, i, j) == puut)
{
minhyppy = pituus;
}
//cout << pituus << '\n';
/*while (nykyisetpuut <= puut && pituus < maksimi)
{
int lkm2 = summataulukkolaske(i + pituus, j + pituus, i, j);
if (lkm2 == puut)
lasku += 1;
nykyisetpuut = lkm2;
pituus++;
}
int x1 = binarysearch(maksimi, i, j, i, j);
int y1 = x1;
int max = x1;
while (summataulukkolaske(x1 + 1, y1 + 1, i, j) == puut)
{
x1 += 1;
y1 += 1;
max += 1;
}
int min = x1;
while (summataulukkolaske(x1 - 1, y1 - 1, i, j) == puut)
{
x1 -= 1;
y1 -= 1;
min -= 1;
}*/
if (maxfound)
return maxhyppy - minhyppy + 1;
else
return 0;
}
int summataulukkolaske(int x1, int y1, int x2, int y2)
{
int i = x2 - 1;
int j = y2 - 1;
int vastaus = 0;
if (i < 0 && j < 0)
{
vastaus = summataulukko[x1][y1];
}
else if (i < 0)
{
vastaus = summataulukko[x1][y1] - summataulukko[x1][j];
}
else if (j < 0)
{
vastaus = summataulukko[x1][y1] - summataulukko[i][y1];
}
else
{
vastaus = summataulukko[x1][y1] - summataulukko[i][y1] - summataulukko[x1][j] + summataulukko[i][j];
}
return vastaus;
}
/*int binarysearch(int maksimi, int x1, int y1, int x2, int y2)
{
int laskutulos = summataulukkolaske(x1, y1, x2, y2);
if (laskutulos == puut)
{
return x1, y1;
}
else
{
if (laskutulos < puut)
{
x1 = x2 + int((maksimi - x1) / 2);
y1 = y2 + int((maksimi - x1) / 2);
}
if (laskutulos > puut)
{
x1 = x2 - int((maksimi - int(x1 / 2)) / 2);
y1 = y2 - int((maksimi - int(y1 / 2)) / 2);
}
binarysearch(maksimi, x1, y1, x2, y2);
}
}*/

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: ACCEPTED

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

correct output
489611392

user output
489611392

Test 12

Group: 3

Verdict: ACCEPTED

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

correct output
120725884

user output
120725884

Test 13

Group: 3

Verdict: ACCEPTED

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

correct output
1849

user output
1849

Test 14

Group: 3

Verdict: ACCEPTED

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

correct output
2665

user output
2665

Test 15

Group: 3

Verdict: ACCEPTED

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

correct output
5587

user output
5587