CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:DLPS
Submission time:2024-11-10 22:54:33 +0200
Language:C++ (C++20)
Status:READY
Result:33
Feedback
groupverdictscore
#1ACCEPTED4
#2ACCEPTED6
#3ACCEPTED10
#4ACCEPTED13
#50
#60
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#2ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#3ACCEPTED0.01 s1, 2, 3, 4, 5, 6details
#4ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#5ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#6ACCEPTED0.01 s2, 3, 4, 5, 6details
#7ACCEPTED0.01 s2, 3, 4, 5, 6details
#8ACCEPTED0.01 s2, 3, 4, 5, 6details
#9ACCEPTED0.01 s2, 3, 4, 5, 6details
#10ACCEPTED0.02 s3, 4, 5, 6details
#11ACCEPTED0.02 s3, 4, 5, 6details
#12ACCEPTED0.02 s3, 4, 5, 6details
#13ACCEPTED0.01 s3, 4, 5, 6details
#14ACCEPTED0.14 s4, 5, 6details
#15ACCEPTED0.16 s4, 5, 6details
#16ACCEPTED0.16 s4, 5, 6details
#17ACCEPTED0.01 s4, 5, 6details
#18--5, 6details
#19--5, 6details
#20--5, 6details
#21ACCEPTED0.09 s5, 6details
#22--6details
#23--6details
#24--6details
#25--6details

Compiler report

input/code.cpp:3:25: warning: extra tokens at end of #include directive
    3 | #include "bits/stdc++.h";
      |                         ^
input/code.cpp:4:25: warning: extra tokens at end of #include directive
    4 | #include "unordered_map";
      |                         ^
input/code.cpp: In function 'int main()':
input/code.cpp:121:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |                 for (int x = 0; x < row.size(); ++x)
      |                                 ~~^~~~~~~~~~~~

Code

#pragma GCC optimize("O3")
#include "bits/stdc++.h";
#include "unordered_map";
using namespace std;
int preCalcMap[6526026];
int flowerCounts[26] = { 0 };
// Debug
int CALLS = 0;
int fieldSize = 0;
const unordered_map<char, int> flowerIndecies = { {'A',0},{'B',1},{'C',2},{'D',3},{'E',4},{'F',5},{'G',6},{'H',7},{'I',8},{'J',9},{'K',10},{'L',11},{'M',12},{'N',13},{'O',14},{'P',15},{'Q',16},{'R',17},{'S',18},{'T',19},{'U',20},{'V',21},{'W',22},{'X',23},{'Y',24},{'Z',25} };
static bool ContainsAllFlowers(int x1, int x2, int y1, int y2)
{
++CALLS;
int i1 = (y2 + 1) * 501 + x2 + 1;
int i2 = y1 * 501 + x2 + 1;
int i3 = (y2 + 1) * 501 + x1;
int i4 = y1 * 501 + x1;
for (int i = 0; i < 26; ++i)
{
if (flowerCounts[i] == 0)
{
continue;
}
//auto& flower = preCalcMap[i];
int a = preCalcMap[i1 + i * 251001];
int b = preCalcMap[i2 + i * 251001];
int c = preCalcMap[i3 + i * 251001];
int d = preCalcMap[i4 + i * 251001];
if (a - b - c + d == 0)
{
return false;
}
}
return true;
}
int lastSolution = -1;
static int Y2Solver(int min, int max, int x1, int x2, int y1)
{
int localMin = min;
int localMax = max;
if (lastSolution != -1 && ContainsAllFlowers(x1, x2, y1, lastSolution))
{
return (max - lastSolution + 1);
}
int current = (min + max) / 2;
bool first = true;
int change = 0;
bool wasSuccess = false;
while (true)
{
if (ContainsAllFlowers(x1, x2, y1, current))
{
if (change == 1 && !wasSuccess)
{
break;
}
if (change == 0 && wasSuccess)
{
break;
}
localMax = current;
change = (localMin + current) / 2 - current;
current += change;
wasSuccess = true;
}
else
{
if (change == -1 && wasSuccess)
{
++current;
break;
}
if (change == 0 && !first)
{
return 0;
}
localMin = current;
change = ceil((current + localMax) / 2.0f) - current;
current += change;
wasSuccess = false;
}
first = false;
}
lastSolution = current;
return (max - current + 1);
}
int main()
{
cin >> fieldSize;
for (int y = 0; y < fieldSize; ++y)
{
string row;
cin >> row;
for (int x = 0; x < row.size(); ++x)
{
int flowerType = flowerIndecies.at(row[x]);
++flowerCounts[flowerType];
int curI = (y + 1) * 501 + x + 1;
int lI = (y + 1) * 501 + x;
int tI = y * 501 + x + 1;
int tlI = y * 501 + x;
for (int i = 0; i < 26; ++i)
{
preCalcMap[curI + 251001 * i] = preCalcMap[lI + 251001 * i] + preCalcMap[tI + 251001 * i] - preCalcMap[tlI + 251001 * i] + (flowerType == i);
}
}
}
int count = 0;
for (int x1 = 0; x1 < fieldSize; ++x1)
{
bool hadSuccessX2 = false;
for (int x2 = fieldSize - 1; x2 >= x1; x2--)
{
lastSolution = -1;
bool hadSuccessY1 = false;
for (int y1 = 0; y1 < fieldSize; ++y1)
{
int ans = Y2Solver(y1, fieldSize - 1, x1, x2, y1);
if (ans == 0)
{
break;
}
else
{
count += ans;
hadSuccessY1 = true;
}
}
if (!hadSuccessY1)
{
break;
}
else
{
hadSuccessX2 = true;
}
}
if (!hadSuccessX2)
{
break;
}
}
cout << count;
}

Test details

Test 1

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...

correct output
2035

user output
2035

Test 2

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
NFWQLWNWYS
DZOQJVXFPJ
CNHXPXMCQD
QRTBVNLTQC
...

correct output
9

user output
9

Test 3

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
...

correct output
3025

user output
3025

Test 4

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
10
FFFFFFFFFF
FFFFFCFFFF
FFFFFFJFFF
FFFFFFFFFF
...

correct output
12

user output
12

Test 5

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
1
X

correct output
1

user output
1

Test 6

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
BBCBUBOUOBBCUUBBCOUO
BOUCOOCUBCOOOCOBOCUO
UCCUUUOBCOCBCBUBUCOO
BUOBUCUCUOOBCOOUBUOO
...

correct output
38724

user output
38724

Test 7

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
CBGLSHGZHYZDWBNDBJUG
SMUXOJQYPXZDTMJUIWOJ
XIDSTNBGHKRKOVUVMINB
MTQGCFRUHQKALXRNCQGS
...

correct output
8334

user output
8334

Test 8

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
...

correct output
44100

user output
44100

Test 9

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...

correct output
18

user output
18

Test 10

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...

correct output
1584665

user output
1584665

Test 11

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...

correct output
1077746

user output
1077746

Test 12

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

correct output
1625625

user output
1625625

Test 13

Group: 3, 4, 5, 6

Verdict: ACCEPTED

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

correct output
1680

user output
1680

Test 14

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...

correct output
25325366

user output
25325366

Test 15

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...

correct output
22342463

user output
22342463

Test 16

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...

correct output
25502500

user output
25502500

Test 17

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
25650

user output
25650

Test 18

Group: 5, 6

Verdict:

input
200
NAANANMMKNKKAKMKMAKNKMNKMMNNAA...

correct output
403292767

user output
(empty)

Test 19

Group: 5, 6

Verdict:

input
200
OMYWATTLURKQPTKEFMGGYAOONXWVSC...

correct output
388111321

user output
(empty)

Test 20

Group: 5, 6

Verdict:

input
200
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...

correct output
404010000

user output
(empty)

Test 21

Group: 5, 6

Verdict: ACCEPTED

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...

correct output
14159445

user output
14159445

Test 22

Group: 6

Verdict:

input
500
VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW...

correct output
15683003812

user output
(empty)

Test 23

Group: 6

Verdict:

input
500
OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE...

correct output
15575906951

user output
(empty)

Test 24

Group: 6

Verdict:

input
500
IIIIIIIIIIIIIIIIIIIIIIIIIIIIII...

correct output
15687562500

user output
(empty)

Test 25

Group: 6

Verdict:

input
500
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...

correct output
3058970930

user output
(empty)