— Dark mode

Datatähti 2025 alku

Niitty

  • Start: 2024-10-28 00:00:00
  • End: 2024-11-11 00:00:00
CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:nikke5
Submission time:2024-11-07 21:09:31 +0200
Language:C++ (C++11)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
#60
Test results
testverdicttimegroup
#10.17 s1, 2, 3, 4, 5, 6details
#2--1, 2, 3, 4, 5, 6details
#30.00 s1, 2, 3, 4, 5, 6details
#40.00 s1, 2, 3, 4, 5, 6details
#5ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#6--2, 3, 4, 5, 6details
#7--2, 3, 4, 5, 6details
#80.01 s2, 3, 4, 5, 6details
#90.35 s2, 3, 4, 5, 6details
#10--3, 4, 5, 6details
#110.00 s3, 4, 5, 6details
#120.00 s3, 4, 5, 6details
#130.00 s3, 4, 5, 6details
#14--4, 5, 6details
#15--4, 5, 6details
#16--4, 5, 6details
#17--4, 5, 6details
#180.01 s5, 6details
#190.01 s5, 6details
#200.01 s5, 6details
#210.01 s5, 6details
#220.01 s6details
#230.01 s6details
#240.02 s6details
#250.01 s6details

Compiler report

input/code.cpp: In function 'void createRects(int)':
input/code.cpp:57:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<flower> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     if (level == flist.size()){
      |         ~~~~~~^~~~~~~~~~~~~~~
input/code.cpp:74:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<flower>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i<flist[level].size(); i++){ // LOOP THE CURRENT LEVEL (FLOWER TYPE)
      |                     ~^~~~~~~~~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:201:9: warning: unused variable 'v' [-Wunused-variable]
  201 |     int v = 0;
      |         ^
input/code.cpp:202:9: warning: unused variable 'overlap' [-Wunused-variable]
  202 |     int overlap = 0;
      |         ^~~~~~~
input/code.cpp: In function 'int getMaxRectAmount(std::vector<int>, int)...

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;
    int listIt;

    
    char idC; //Remove later, its just to visualize


    
};

vector<vector<flower>> flist;

//cout << flist[0][i].x << ", " << flist[0][i].y << ", " << flist[0][i].idC << ", " << distLists[0][0][i].first << ", " << distLists[0][1][i].first << "\n";

int idList[200] = {0};

vector<vector<int>> rectList; 

vector<int> currentX, currentY;

void findSmallestRect(vector<int> X, vector<int> Y, vector<int> &p) 
{ 
    // find Xmax and Xmin 
    int Xmax = *max_element(X.begin(), X.end()); 
    int Xmin = *min_element(X.begin(), X.end()); 
  
    // find Ymax and Ymin 
    int Ymax = *max_element(Y.begin(), Y.end()); 
    int Ymin = *min_element(Y.begin(), Y.end()); 
  
    // print all four coordinates 
    p[0] = Xmin;
    p[1] = Xmax;
    p[2] = Ymin;
    p[3] = Ymax;
} 

void createRects(int level){

    if (level == flist.size()){
        vector<int> EndCoords(4); // Pienimmän mahdollisen suorakulmion koordinaatit järjestyksessä; XMax, Xmin, Ymax, Ymin.

        findSmallestRect(currentX, currentY, EndCoords);

        rectList.push_back(vector<int>());

        for (int i = 0; i < 4; i++)
        {
            rectList[rectList.size()-1].push_back(EndCoords[i]);
        }

        // cout << rectList[rectList.size() - 1][0] << ", " << rectList[rectList.size() - 1][1] << ", " << rectList[rectList.size() - 1][2] << ", " << rectList[rectList.size() - 1][3] << "\n";
        // cout << "\n";
        return;
    }

    for (int i = 0; i<flist[level].size(); i++){ // LOOP THE CURRENT LEVEL (FLOWER TYPE)
        currentX.push_back(flist[level][i].x);
        currentY.push_back(flist[level][i].y);

        // cout << flist[level][i].idC << ", ";

        createRects(level + 1);

        currentX.pop_back();
        currentY.pop_back();
    }

}


int getMaxRectAmount(vector<int> Coords, int n){
    int dirX1;
    int dirY1;

    dirX1 = Coords[1] - Coords[0];
    dirY1 = Coords[3] - Coords[2];

    int x1 = Coords[0];
    int y1 = Coords[2];

    int x2 = Coords[1];
    int y2 = Coords[3];

    if (dirX1 >= 0 && dirY1 >= 0)
    {
        return (n - y2) * (y1 + 1) * (n - x2) * (x1 + 1);
    }
}

int getOverlapRectAmount(vector<int> rect1, vector<int> rect2, int n){
    vector<int> XCoords;
    vector<int> YCoords;

    XCoords.push_back(rect1[0]);
    XCoords.push_back(rect1[1]);

    YCoords.push_back(rect1[2]);
    YCoords.push_back(rect1[3]);

    XCoords.push_back(rect2[0]);
    XCoords.push_back(rect2[1]);

    YCoords.push_back(rect2[2]);
    YCoords.push_back(rect2[3]);

    vector<int> EndCoords(4);

    findSmallestRect(XCoords, YCoords, EndCoords); // Tehdään suorakulmien yhdistelmästä pienin suorakulmio ja lisätään se overlappiin

    int currentOverlap = getMaxRectAmount(EndCoords, n);
    return currentOverlap;
}

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;
            f.idC = s[x];

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

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

            f.listIt = flist[f.id].size();
            flist[f.id].push_back(f);
        }
    }

    sort(flist.begin(), flist.end(), [](const vector<flower> & a, const vector<flower> & b){ return a.size() < b.size(); }); // JÄRJESTÄ LISTA HARVINAISIMMASTA YLEISIMPÄÄN

    
    createRects(0);



    sort(rectList.begin(), rectList.end());

    auto it
        = unique(rectList.begin(), rectList.end());


    rectList.erase(it, rectList.end());


    int v = 0;
    int overlap = 0;

    // for (int i = 0; i<rectList.size(); i++){ // LISÄÄ KAIKKIEN SUORAKULMIEN VASTAUKSET VASTAUKSEEN
    //     for (int j = 0; j < 4; j++)
    //     {
    //         cout << rectList[i][j] << ", ";
    //     }

    //     int rectAmount = getMaxRectAmount(rectList[i], n);

    //     cout << "rectAmount: " << rectAmount << "\n";
    //     v += rectAmount;
    // }



    // vector<vector<int>> overlapRects;

    // int rectAmount = getMaxRectAmount(rectList[0], n);
    // v += rectAmount;

    // for (int k = 0; k < 4; k++)
    // {
    //     cout << rectList[0][k] << ", ";
    // }

    // cout << " RECT AMOUNT: " << rectAmount << "\n";

    // for(int i = 1; i<rectList.size(); i++){ // LOOPATAAN KAIKKI, JA KATSOTAAN OVERLAPIT EDELLISEEN

    //     for (int k = 0; k < 4; k++)
    //     {
    //         cout << rectList[i-1][k] << ", ";
    //     }

    //     cout << " -> ";

    //     for (int k = 0; k < 4; k++)
    //     {
    //         cout << rectList[i][k] << ", ";
    //     }

    //     int rectAmount = getMaxRectAmount(rectList[i], n);
    //     v += rectAmount;

    //     cout << " RECT AMOUNT: " << rectAmount;

    //     vector<int> XCoords;
    //     vector<int> YCoords;

    //     XCoords.push_back(rectList[i-1][0]);
    //     XCoords.push_back(rectList[i-1][1]);

    //     YCoords.push_back(rectList[i-1][2]);
    //     YCoords.push_back(rectList[i-1][3]);

    //     XCoords.push_back(rectList[i][0]);
    //     XCoords.push_back(rectList[i][1]);

    //     YCoords.push_back(rectList[i][2]);
    //     YCoords.push_back(rectList[i][3]);

    //     int EndCoords[4];

    //     findSmallestRect(XCoords, YCoords, EndCoords); // Tehdään suorakulmien yhdistelmästä pienin suorakulmio ja lisätään se overlappiin

    //     overlapRects.push_back(vector<int>());
    //     overlapRects[overlapRects.size() - 1].insert(overlapRects[overlapRects.size() - 1].begin(), EndCoords, EndCoords + 4);

    //     // for (int k = 0; k < 4; k++)
    //     // {
    //     //     cout << overlapRects[overlapRects.size() - 1][k] << ", ";
    //     // }

    //     int currentOverlap = getMaxRectAmount(overlapRects[overlapRects.size()-1], n);
    //     overlap += currentOverlap;

    //     cout << " Overlap:" << currentOverlap << "\n";

    //     // int currentOverlap = getMaxRectAmount(overlapRects[overlapRects.size()-1], n);
    //     // v -= currentOverlap;

    //     // cout << "- Overlap:" << currentOverlap << "\n";

    //     // for (int j = i+1; j < rectList.size(); j++) // LASKETAAN KAIKKIEN RECTIEN OVERLAPIT VERRATTUNA KAIKKIIN MUIHIN
    //     // {

    //     //     for (int k = 0; k < 4; k++)
    //     //     {
    //     //         cout << rectList[i][k] << ", ";
    //     //     }

    //     //     cout << " -> ";

    //     //     for (int k = 0; k < 4; k++)
    //     //     {
    //     //         cout << rectList[j][k] << ", ";
    //     //     }

            
    //     //     int rectAmount = getMaxRectAmount(rectList[j], n);

    //     //     cout << " RECT AMOUNT: " << rectAmount; 

    //     //     vector<int> XCoords;
    //     //     vector<int> YCoords;

    //     //     XCoords.push_back(rectList[j][0]);
    //     //     XCoords.push_back(rectList[j][1]);

    //     //     YCoords.push_back(rectList[j][2]);
    //     //     YCoords.push_back(rectList[j][3]);

    //     //     XCoords.push_back(rectList[i][0]);
    //     //     XCoords.push_back(rectList[i][1]);

    //     //     YCoords.push_back(rectList[i][2]);
    //     //     YCoords.push_back(rectList[i][3]);

    //     //     int EndCoords[4]; 

    //     //     findSmallestRect(XCoords, YCoords, EndCoords); // Tehdään suorakulmien yhdistelmästä pienin suorakulmio ja lisätään se overlappiin

    //     //     overlapRects.push_back(vector<int>());
    //     //     overlapRects[overlapRects.size()-1].insert(overlapRects[overlapRects.size()-1].begin(), EndCoords, EndCoords + 4);

    //     //     // for (int k = 0; k < 4; k++)
    //     //     // {
    //     //     //     cout << overlapRects[overlapRects.size() - 1][k] << ", ";
    //     //     // }

    //     //     // int currentOverlap = getMaxRectAmount(overlapRects[overlapRects.size()-1], n);
    //     //     // overlap += currentOverlap;

    //     //     // cout << " Overlap:" << currentOverlap << "\n";

    //     //     // int currentOverlap = getMaxRectAmount(overlapRects[overlapRects.size()-1], n);
    //     //     // v -= currentOverlap;


    //     //     // cout << "- Overlap:" << currentOverlap << "\n";

    //     // }

    //     // cout << "\n";
        
    // }

    // sort(overlapRects.begin(), overlapRects.end());

    // auto it2 = unique(overlapRects.begin(), overlapRects.end());

    // overlapRects.erase(it2, overlapRects.end());

    // cout << "--- \n\n";

    // vector<vector<int>> wentOverOverlaps;

    // for (int i = 0; i<overlapRects.size(); i++){
    //     // for (int k = 0; k < 4; k++)
    //     // {
    //     //     cout << overlapRects[i][k] << ", ";
    //     // }

    //     int currentOverlap = getMaxRectAmount(overlapRects[i], n);

    //     for (int j = 0; j<wentOverOverlaps.size(); j++){
    //         vector<int> XCoords;
    //         vector<int> YCoords;

    //         XCoords.push_back(overlapRects[i][0]);
    //         XCoords.push_back(overlapRects[i][1]);

    //         YCoords.push_back(overlapRects[i][2]);
    //         YCoords.push_back(overlapRects[i][3]);

    //         XCoords.push_back(wentOverOverlaps[j][0]);
    //         XCoords.push_back(wentOverOverlaps[j][1]);

    //         YCoords.push_back(wentOverOverlaps[j][2]);
    //         YCoords.push_back(wentOverOverlaps[j][3]);

    //         int EndCoords[4];

    //         findSmallestRect(XCoords, YCoords, EndCoords);

    //         currentOverlap -= getMaxRectAmount(vector<int>({EndCoords[0],EndCoords[1],EndCoords[2],EndCoords[3]}), n);
    //     }

    //     overlap += currentOverlap;

    //     cout << "Overlap:" << currentOverlap << "\n";

    //     wentOverOverlaps.push_back(overlapRects[i]);
    // }



    // for (int i = 0; i<rectList.size(); i++){ // LISÄÄ KAIKKIEN SUORAKULMIEN VASTAUKSET VASTAUKSEEN
    //     for (int j = 0; j < 4; j++)
    //     {
    //         cout << rectList[i][j] << ", ";
    //     }

    //     int rectAmount = getMaxRectAmount(rectList[i], n);

    //     cout << "rectAmount: " << rectAmount << "\n";
    //     v += rectAmount;
    // }

    // for (int i = 0; i < rectList.size(); i++)
    // {
    //     int rectAmount = getMaxRectAmount(rectList[i], n);

    //     int overlapRects = 0;

    //     for (int j = 0; j < i; j++)
    //     {
    //         overlapRects += getOverlapRectAmount(rectList[i], rectList[i - j], n);

    //         int overlappingOverlaps =;

    //     }

    //     v += rectAmount - overlapRects;
    // }

    // cout << "V: " << v << " Overlap: " << overlap << " VASTAUS:" << rectList.size() << "\n";

    cout << rectList.size();


}

Test details

Test 1

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

Verdict:

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...
view save

correct output
2035
view save

user output
78
view save

Test 2

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

Verdict:

input
10
NFWQLWNWYS
DZOQJVXFPJ
CNHXPXMCQD
QRTBVNLTQC
...
view save

correct output
9
view save

user output
(empty)

Test 3

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

Verdict:

input
10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
...
view save

correct output
3025
view save

user output
99
view save

Test 4

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

Verdict:

input
10
FFFFFFFFFF
FFFFFCFFFF
FFFFFFJFFF
FFFFFFFFFF
...
view save

correct output
12
view save

user output
1
view save

Test 5

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

Verdict: ACCEPTED

input
1
X
view save

correct output
1
view save

user output
1
view save

Test 6

Group: 2, 3, 4, 5, 6

Verdict:

input
20
BBCBUBOUOBBCUUBBCOUO
BOUCOOCUBCOOOCOBOCUO
UCCUUUOBCOCBCBUBUCOO
BUOBUCUCUOOBCOOUBUOO
...
view save

correct output
38724
view save

user output
(empty)

Test 7

Group: 2, 3, 4, 5, 6

Verdict:

input
20
CBGLSHGZHYZDWBNDBJUG
SMUXOJQYPXZDTMJUIWOJ
XIDSTNBGHKRKOVUVMINB
MTQGCFRUHQKALXRNCQGS
...
view save

correct output
8334
view save

user output
(empty)

Test 8

Group: 2, 3, 4, 5, 6

Verdict:

input
20
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
...
view save

correct output
44100
view save

user output
440
view save

Test 9

Group: 2, 3, 4, 5, 6

Verdict:

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...
view save

correct output
18
view save

user output
6
view save

Test 10

Group: 3, 4, 5, 6

Verdict:

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...
view save

correct output
1584665
view save

user output
(empty)

Test 11

Group: 3, 4, 5, 6

Verdict:

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...
view save

correct output
1077746
view save

user output
(empty)

Test 12

Group: 3, 4, 5, 6

Verdict:

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...
view save

correct output
1625625
view save

user output
(empty)

Test 13

Group: 3, 4, 5, 6

Verdict:

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...
view save

correct output
1680
view save

user output
(empty)

Test 14

Group: 4, 5, 6

Verdict:

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...
view save

correct output
25325366
view save

user output
(empty)

Test 15

Group: 4, 5, 6

Verdict:

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...
view save

correct output
22342463
view save

user output
(empty)

Test 16

Group: 4, 5, 6

Verdict:

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...
view save

correct output
25502500
view save

user output
(empty)

Test 17

Group: 4, 5, 6

Verdict:

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...
view save

correct output
25650
view save

user output
(empty)

Test 18

Group: 5, 6

Verdict:

input
200
NAANANMMKNKKAKMKMAKNKMNKMMNNAA...
view save

correct output
403292767
view save

user output
(empty)

Test 19

Group: 5, 6

Verdict:

input
200
OMYWATTLURKQPTKEFMGGYAOONXWVSC...
view save

correct output
388111321
view save

user output
(empty)

Test 20

Group: 5, 6

Verdict:

input
200
CCCCCCCCCCCCCCCCCCCCCCCCCCCCCC...
view save

correct output
404010000
view save

user output
(empty)

Test 21

Group: 5, 6

Verdict:

input
200
LLLLLLLLLLLLLLLLLHLLLLLLLLLLLL...
view save

correct output
14159445
view save

user output
(empty)

Test 22

Group: 6

Verdict:

input
500
VVHWVUHVHUWWWVUUUWVUUHUUWHWUVW...
view save

correct output
15683003812
view save

user output
(empty)

Test 23

Group: 6

Verdict:

input
500
OIMZGEQSBMBDSDXSWRFNKSGFEBBTJE...
view save

correct output
15575906951
view save

user output
(empty)

Test 24

Group: 6

Verdict:

input
500
IIIIIIIIIIIIIIIIIIIIIIIIIIIIII...
view save

correct output
15687562500
view save

user output
(empty)

Test 25

Group: 6

Verdict:

input
500
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWW...
view save

correct output
3058970930
view save

user output
(empty)

Tasks

A Pizzat-B Robotti-C Kortit I-D Kortit II-E Niitty-F Tikut-

Submissions (nikke5)

2024-11-10 22:32:46 02024-11-10 22:32:21 02024-11-10 22:31:32 202024-11-10 22:31:00 02024-11-10 22:28:23 202024-11-10 22:27:47 02024-11-09 13:05:14 202024-11-09 12:20:26 202024-11-08 17:25:56 102024-11-08 17:09:10 102024-11-07 21:38:32 02024-11-07 21:32:42 02024-11-07 21:09:31 02024-11-07 21:07:24 02024-11-05 19:16:07 02024-11-05 19:15:38 0