CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:OorigamiK
Submission time:2024-11-07 12:15:24 +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.00 s1, 2, 3, 4, 5, 6details
#4ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#5ACCEPTED0.01 s1, 2, 3, 4, 5, 6details
#6ACCEPTED0.00 s2, 3, 4, 5, 6details
#7ACCEPTED0.00 s2, 3, 4, 5, 6details
#8ACCEPTED0.00 s2, 3, 4, 5, 6details
#9ACCEPTED0.00 s2, 3, 4, 5, 6details
#10ACCEPTED0.01 s3, 4, 5, 6details
#11ACCEPTED0.01 s3, 4, 5, 6details
#12ACCEPTED0.01 s3, 4, 5, 6details
#13ACCEPTED0.01 s3, 4, 5, 6details
#14ACCEPTED0.04 s4, 5, 6details
#15ACCEPTED0.13 s4, 5, 6details
#16ACCEPTED0.04 s4, 5, 6details
#17ACCEPTED0.01 s4, 5, 6details
#18ACCEPTED0.28 s5, 6details
#19--5, 6details
#20ACCEPTED0.30 s5, 6details
#21ACCEPTED0.05 s5, 6details
#220.02 s6details
#230.08 s6details
#240.01 s6details
#250.07 s6details

Compiler report

input/code.cpp: In function 'bool recArea(int&, int&, int&, int&, std::vector<std::vector<std::vector<int> > >&)':
input/code.cpp:6:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 |     for (int color = 0; color < flowerSums.size(); color++) {
      |                         ~~~~~~^~~~~~~~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:74:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int color = 0; color < flowerSums.size(); color++) {
      |                         ~~~~~~^~~~~~~~~~~~~~~~~~~
input/code.cpp:91:17: warning: variable 'step1' set but not used [-Wunused-but-set-variable]
   91 |             int step1 = 1;
      |                 ^~~~~

Code

#include <iostream>
#include <string>
#include <vector>

bool recArea(int& x1, int& x2, int& y1, int& y2, std::vector<std::vector<std::vector<int>>>& flowerSums) {
    for (int color = 0; color < flowerSums.size(); color++) {
        int sum = 0;
        sum += flowerSums[color][x2][y2];
        sum += flowerSums[color][x1 - 1][y1 - 1];
        sum -= flowerSums[color][x1 - 1][y2];
        sum -= flowerSums[color][x2][y1 - 1];
        if (sum <= 0) {
            return false;
        }
    }
    return true;
}

int main()
{
    std::vector<std::string> flowers;
    int n;
    //n = 200;
    std::cin >> n;
    for (int i = 0; i < n; i++) {
        std::string s;
        std::cin >> s;
        //for (int r = 0; r < n; r++) {
        //    int k = rand()%26;
        //    s += char(int('A') + k);
        //}
        //s = "AAAAAAAAAABBAAAAAAAABAAAAAAAAABBBBBBBBBBAAAAAAAAAABBAAAAAAAABAAAAAAAAABBBBBBBBBBAAAAAAAAAABBAAAAAAAABAAAAAAAAABBBBBBBBBBAAAAAAAAAABBAAAAAAAABAAAAAAAAABBBBBBBBBBAAAAAAAAAABBAAAAAAAABAAAAAAAAABBBBBBBBBBAAAAAAAAAABBAAAAAAAABAAAAAAAAABBBBBBBBBBAAAAAAAAAABBAAAAAAAABAAAAAAAAABBBBBBBBBBAAAAAAAAAABBAAAAAAAABAAAAAAAAABBBBBBBBBBAAAAAAAAAABBAAAAAAAABAAAAAAAAABBBBBBBBBBAAAAAAAAAABBAAAAAAAABAAAAAAAAABBBBBBBBBBAAAAAAAAAABBAAAAAAAABAAAAAAAAABBBBBBBBBBAAAAAAAAAABBAAAAAAAABAAAAAAAAABBBBBBBBBBAAAAAAAAAABBAAAAAAAA";
        flowers.push_back(s);
    }
    std::vector<bool> theFlowers;
    for (int i = 0; i < 26; i++) {
        theFlowers.push_back(false);
    }
    for (std::string s : flowers) {
        for (int i = 0; i < n; i++) {
            int k = int(s[i]) - int('A');
            theFlowers[k] = true;
        }
    }
    std::vector<std::vector<std::vector<int>>> flowerSums;
    int y = 0;
    for (int j = 0; j < 26; j++) {
        if (theFlowers[j]) {
            flowerSums.push_back({});
            for (int i = 0; i <= n; i++) {
                flowerSums[y].push_back({});
                for (int k = 0; k <= n; k++) {
                    flowerSums[y][i].push_back(0);

                }
            }
            y++;
        }
    }

    y = 0;
    for (int color = 0; color < 26; color++) {
        if (theFlowers[color]) {
            for (int k = 1; k <= n; k++) {
                for (int t = 1; t <= n; t++) {
                    if (int(flowers[k - 1][t - 1]) - int('A') == color) {
                        flowerSums[y][k][t]++;
                    }
                }
            }
            y++;
        }
    }
    for (int color = 0; color < flowerSums.size(); color++) {
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                flowerSums[color][i][j] += flowerSums[color][i - 1][j];
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 2; j <= n; j++) {
                flowerSums[color][i][j] += flowerSums[color][i][j - 1];
            }
        }
    }
    long long numOfRec = 0;
    for (int x1 = 1; x1 <= n; x1++) {
        int ceils[201];
        std::fill(std::begin(ceils), std::end(ceils), n);
        for (int x2 = x1; x2 <= n; x2++) {
            int step1 = 1;
            int y1 = 1;
            while (y1 <= n) {
                int ceiling2 = ceils[y1];
                int flooring2 = y1;
                int step2 = (ceiling2 + flooring2) / 2;
                //std::cout << "hi" << std::endl;

                while (ceiling2 - flooring2 > 1) {
                    if (recArea(x1, x2, y1, step2, flowerSums)) {
                        ceiling2 = (ceiling2 + flooring2) / 2 + (ceiling2 + flooring2) % 2;
                    }
                    else {
                        flooring2 = (ceiling2 + flooring2) / 2;
                    }
                    step2 = (ceiling2 + flooring2) / 2;

                }
                if (recArea(x1, x2, y1, flooring2, flowerSums)) {
                    step2 = flooring2;
                }
                else if (recArea(x1, x2, y1, ceiling2, flowerSums)) {
                    step2 = ceiling2;
                }
                else {
                    step2 = n + 1;
                }
                step1 = y1;
                int ceiling1 = step2;
                int flooring1 = y1;
                int step1 = (ceiling1 + flooring1) / 2;
                while (ceiling1 - flooring1 > 1) {
                    if (recArea(x1, x2, step1, step2, flowerSums)) {
                        flooring1 = (ceiling1 + flooring1) / 2;
                    }
                    else {
                        ceiling1 = (ceiling1 + flooring1) / 2 + (ceiling1 + flooring1) % 2;
                    }
                    step1 = (ceiling1 + flooring1) / 2;

                }
                if (recArea(x1, x2, flooring1, step2, flowerSums)) {
                    step1 = flooring1;
                }
                else if (recArea(x1, x2, ceiling1, step2, flowerSums)) {
                    step1 = ceiling1;
                }
                else {
                    step1 = n + 1;
                }
                std::fill(std::begin(ceils) + y1, std::begin(ceils) + step1, step2);
                //std::cout << 1 + step1 - y1 << " " << n+1 - step2<<" "<<x1<<" "<<x2<<" "<< (1 + step1 - y1) * (n - step2)<<" "<<y1<<" "<<step1<<" "<<step2 << std::endl;
                numOfRec += (1 + step1 - y1) * (n + 1 - step2);
                y1 = step1 + 1;
            }
        }
    }
    std::cout << numOfRec << std::endl;
}

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

input
200
NAANANMMKNKKAKMKMAKNKMNKMMNNAA...

correct output
403292767

user output
403292767

Test 19

Group: 5, 6

Verdict:

input
200
OMYWATTLURKQPTKEFMGGYAOONXWVSC...

correct output
388111321

user output
(empty)

Test 20

Group: 5, 6

Verdict: ACCEPTED

input
200
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...

correct output
404010000

user output
404010000

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)