CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:nikke5
Submission time:2024-11-09 12:20:26 +0200
Language:C++ (C++11)
Status:READY
Result:20
Feedback
groupverdictscore
#1ACCEPTED4
#2ACCEPTED6
#3ACCEPTED10
#40
#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.02 s2, 3, 4, 5, 6details
#8ACCEPTED0.01 s2, 3, 4, 5, 6details
#9ACCEPTED0.00 s2, 3, 4, 5, 6details
#10ACCEPTED0.43 s3, 4, 5, 6details
#11ACCEPTED0.82 s3, 4, 5, 6details
#12ACCEPTED0.43 s3, 4, 5, 6details
#13ACCEPTED0.03 s3, 4, 5, 6details
#14--4, 5, 6details
#15--4, 5, 6details
#16--4, 5, 6details
#17ACCEPTED0.63 s4, 5, 6details
#18--5, 6details
#19--5, 6details
#20--5, 6details
#21--5, 6details
#22--6details
#23--6details
#24--6details
#25--6details

Compiler report

input/code.cpp: In function 'std::vector<bool> findLettersFromRect(int, int, int, int, int)':
input/code.cpp:48:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<flower> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |                     for (int i = 0; i < flist.size(); i++)
      |                                     ~~^~~~~~~~~~~~~~
input/code.cpp:59:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<flower> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |                     for (int i = 0; i < flist.size(); i++)
      |                                     ~~^~~~~~~~~~~~~~
input/code.cpp:72:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<flower> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |             for(int i = 0; i<flist.size(); i++){
      |...

Code

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <chrono>
#include <iomanip>
#include <algorithm>

typedef long long ll;
using namespace std;

struct flower{

    int x, y;

    int id;
};

vector<vector<flower>> flist;

vector<vector<vector<bool>>> FoundTracker;
bool FoundTrackerReset = true;

int idList[200] = {0};

int letterGrid[501][501];

vector<bool> findLettersFromRect(int minX, int maxX, int minY, int maxY, int n){

    vector<bool> foundLetters = vector<bool>(flist.size(), false);

    if (FoundTrackerReset)
    {

        FoundTrackerReset = false;

        for (int x = minX; x <= maxX; x++)
        {
            for (int y = minY; y <= maxY; y++)
            {
                foundLetters[letterGrid[x][y]] = true;
                FoundTracker[x][y][letterGrid[x][y]] = true;

                if (minX != maxX)
                {
                    for (int i = 0; i < flist.size(); i++)
                    {
                        if (FoundTracker[maxX - 1][maxY][i])
                        {
                            FoundTracker[maxX][maxY][i] = true;
                        }
                    }
                }

                if (minY != maxY)
                {
                    for (int i = 0; i < flist.size(); i++)
                    {
                        if (FoundTracker[maxX][maxY - 1][i])
                        {
                            FoundTracker[maxX][maxY][i] = true;
                        }
                    }
                }
            }
        }
    }
    else{
        if(minX != maxX){
            for(int i = 0; i<flist.size(); i++){
                if (FoundTracker[maxX-1][maxY][i]){
                    foundLetters[i] = true;
                    FoundTracker[maxX][maxY][i] = true;
                }
            }
        }

        if (minY != maxY)
        {
            for (int i = 0; i < flist.size(); i++)
            {
                if (FoundTracker[maxX][maxY-1][i])
                {
                    foundLetters[i] = true;
                    FoundTracker[maxX][maxY][i] = true;
                }
            }
        }

        foundLetters[letterGrid[maxX][maxY]] = true;
        FoundTracker[maxX][maxY][letterGrid[maxX][maxY]] = true;
    }

    return foundLetters;


}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    fill_n(idList, 200, -1);

    int n;

    cin >> n;
    cin.ignore(1,'\n');

    int id = 0;
    vector<string> sI;

    for (int y = n-1; y>=0; y--){

        
        sI.push_back(string());
        getline(cin, sI[sI.size()-1]);

    }

    int c = n-1;

    for (int y = n - 1; y >= 0; y--)
    {
        
        string s = sI[c];

        c--;

        for (int x = 0; x < n; x++)
        {
            flower f;
            f.x = x;
            f.y = y;

            if (idList[(int)s[x]] == -1)
            {
                idList[(int)s[x]] = id;
                flist.push_back(vector<flower>());
                id++;
            }

            f.id = idList[(int)s[x]];

            flist[f.id].push_back(f);

            letterGrid[x][y] = f.id;
        }
    }

    vector<vector<char>> visualization;

    

    for (int y = 0; y<n; y++){
        visualization.push_back(vector<char>());
        for(int x = 0; x<n; x++){
            visualization[y].push_back(sI[y][x]);
        }
    }

    int v = 0;
    int maxMinYIteration = 501;

    for(int minX = 0; minX<n; minX++){

        bool breakLevel3 = false;

        for(int minY = 0; minY<min(n,maxMinYIteration); minY++){

            bool breakLevel2 = false;

            FoundTrackerReset = true;
            FoundTracker = vector<vector<vector<bool>>>(n, vector<vector<bool>>(n, vector<bool>(flist.size(), false)));

            for(int maxX = minX; maxX<n; maxX++){

                bool breakLevel1 = false;

                for (int maxY = minY; maxY<n; maxY++){

                   

                    // for (int y = minY; y <= maxY; y++)
                    // {
                    //     for (int x = minX; x <= maxX; x++)
                    //     {
                    //         cout << visualization[y][x] << " ";
                    //     }
                    //     cout << "\n";
                    // }
                    // cout << "\n";


                    // cout << minX << ", " << maxX << ", " << minY << ", " << maxY << "\n";
                    int notFound = flist.size();
                    
                    vector<bool> currentRectLetters;

                    currentRectLetters = findLettersFromRect(minX, maxX, minY, maxY, n);

                    for (int i = 0; i<flist.size(); i++){
                        if (currentRectLetters[i]){
                            notFound--;
                        }
                    }

                    if (notFound == 0){
                        v += n - maxY; // Jos tästä lähtien kaikista suorakulmista löytyy kaikki kirjaimet, lisää niiden määrä vastaukseen ja mene seuraavaan maxX iteraatioon.

                        break;
                    }
                    else{
                        if (maxX == n-1 && maxY == n-1){
                            if (minY == 0){
                                breakLevel3 = true;
                            }
                            else{
                                breakLevel2 = true;
                                maxMinYIteration = minY;
                            }
                        }

                    }

                }

                if (breakLevel1 || breakLevel2 || breakLevel3){
                    break;
                }

            }

            if(breakLevel2 || breakLevel3){
                break;
            }

        }

        if(breakLevel3){
            break;
        }

    }


    cout << v;

}

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:

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...

correct output
25325366

user output
(empty)

Test 15

Group: 4, 5, 6

Verdict:

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...

correct output
22342463

user output
(empty)

Test 16

Group: 4, 5, 6

Verdict:

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...

correct output
25502500

user output
(empty)

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:

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...

correct output
14159445

user output
(empty)

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)