CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:Karjalanp11rakka
Submission time:2024-11-02 16:41:17 +0200
Language:C++ (C++20)
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.00 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.04 s3, 4, 5, 6details
#11ACCEPTED0.22 s3, 4, 5, 6details
#12ACCEPTED0.03 s3, 4, 5, 6details
#13ACCEPTED0.07 s3, 4, 5, 6details
#14ACCEPTED0.32 s4, 5, 6details
#15--4, 5, 6details
#16ACCEPTED0.30 s4, 5, 6details
#17--4, 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 'void search(bool, bool)':
input/code.cpp:32:32: warning: comparison of integer expressions of different signedness: 'std::unordered_set<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |         if(currentTypes.size() == typesN) ++result;
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~
input/code.cpp:61:32: warning: comparison of integer expressions of different signedness: 'std::unordered_set<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |         if(currentTypes.size() == typesN)
      |            ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~

Code

#include <bits/stdc++.h>
 
using namespace std;
 
vector<char> flowers {};
int typesN {};
int n {};
 
int currentPos {}, currentWidth {1}, currentHeight {1};
unordered_set<char> currentTypes {};
 
unsigned long result {};
 
void search(bool canRight, bool canDown)
{
    if((currentPos + 1) % n != 0 
        && canRight)
    {
        ++currentWidth;
        ++currentPos;
 
        vector<bool> typesToRemove {};
        typesToRemove.resize(currentHeight);
 
        for(int i {}; i < currentHeight; ++i)
            if(!currentTypes.contains(flowers[currentPos - i]))
            {
                currentTypes.insert(flowers[currentPos - (n * i)]);
                typesToRemove[i] = true;
            }
 
        if(currentTypes.size() == typesN) ++result;
 
        search(true, currentHeight == 1);
 
        for(int i {}; i < currentHeight; ++i)
            if(typesToRemove[i])
                currentTypes.erase(flowers[currentPos - (n * i)]);
 
        --currentWidth;
        --currentPos;
    }
    if((currentPos + n) < (n*n)
        && canDown)
    {
        ++currentHeight;
        currentPos += n;
 
        vector<bool> typesToRemove {};
        typesToRemove.resize(currentWidth);
 
        for(int i {}; i < currentWidth; ++i)
        {
            if(!currentTypes.contains(flowers[currentPos - i]))
            {
                currentTypes.insert(flowers[currentPos - i]);
                typesToRemove[i] = true;
            }
        }
 
        if(currentTypes.size() == typesN)
        {
            result += n - (currentPos / n);
        }
        else search(false, true);
 
        for(int i {}; i < currentWidth; ++i)
            if(typesToRemove[i])
                currentTypes.erase(flowers[currentPos - i]);
 
        --currentHeight;
        currentPos -= n;
    }
}
 
int main()
{
    cin >> n;
    flowers.reserve(n*n);
    unordered_set<char> types {};
    for(int i {}; i < (n*n); ++i)
    {
        char c {};
        cin >> c;
        flowers.push_back(c);
        types.insert(c);
    }
    typesN = types.size();
        
    vector<bool> ignore {};
    ignore.reserve(n*n);
 
    for(int i {}; i < (n*n); ++i)
    {
        if(typesN == 1) ++result;
        if(ignore[i]) continue;
        currentPos = i;
        currentTypes.insert(flowers[currentPos]);
        auto startResult {result};
        search(true, true);
        if(startResult == result)
        {
            for(int j {i + 1}; j < (n*n); ++j)
            {
                if(ignore[j]) continue;
                if((j % n) > (i % n)) ignore[j] = true;
            }
        }
        currentTypes.erase(flowers[currentPos]);
    }
    cout << result;
    return 0;
}

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:

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...

correct output
22342463

user output
(empty)

Test 16

Group: 4, 5, 6

Verdict: ACCEPTED

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...

correct output
25502500

user output
25502500

Test 17

Group: 4, 5, 6

Verdict:

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
25650

user output
(empty)

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)