CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:Lytsky
Submission time:2024-10-31 16:57:13 +0200
Language:C++ (C++11)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
#60
Test results
testverdicttimegroup
#10.00 s1, 2, 3, 4, 5, 6details
#20.01 s1, 2, 3, 4, 5, 6details
#30.00 s1, 2, 3, 4, 5, 6details
#4ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#5ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#60.00 s2, 3, 4, 5, 6details
#70.01 s2, 3, 4, 5, 6details
#80.00 s2, 3, 4, 5, 6details
#90.01 s2, 3, 4, 5, 6details
#100.01 s3, 4, 5, 6details
#110.02 s3, 4, 5, 6details
#120.01 s3, 4, 5, 6details
#130.02 s3, 4, 5, 6details
#140.02 s4, 5, 6details
#150.08 s4, 5, 6details
#160.01 s4, 5, 6details
#170.09 s4, 5, 6details
#180.07 s5, 6details
#190.36 s5, 6details
#200.03 s5, 6details
#210.37 s5, 6details
#220.40 s6details
#23--6details
#240.16 s6details
#25--6details

Code

#include <bits/stdc++.h>

using namespace std;

map<char, long> setUnion(map<char, long> a, map<char, long> b) {
    for (auto x : a) { 
        b[x.first] += x.second;
    }
    return b;
}
map<char, long> setMinus(map<char, long> a, map<char, long> b) {
    for (auto x : b) { 
        a[x.first] -= x.second;
    }
    return a;
}

int main() {
    long n, answer = 0;
    char flower;
    cin >> n;
    map<char, long> plus, now, species;
    vector<map<char, long>> sums;

    for (long index = 0; index < n*n; index++) {
        plus.clear();
        cin >> flower;
        if (not species[flower]) species[flower] = 1;
        map<char, long> m;
        m[flower] = 1;
        sums.push_back(m);

        if (index != 0) {
            if (index%n > 0) sums[index] = setUnion(sums[index-1], sums[index]);
            if (index >= n) sums[index] = setUnion(sums[index-n], sums[index]);
            if (index%n > 0 and index >= n) sums[index] = setMinus(sums[index], sums[((index-n)/n)*n + (index-1)%n]);
        }
    }
    for (long index = 0; index < n*n; index++) {
        long lensumsi = 0;
        for (auto specie : species) { 
            if (sums[index][specie.first]) lensumsi++;
        }
        if (lensumsi == (long) species.size()) {
            map<char, long> big = sums[index];
            //vasen 
            for (long vasen = 0; vasen <= index % n; vasen++) {
                //ylä
                for (long yla = (index)/n + 1; yla > 0; yla--) {
                    if (index - yla*n >= 0) {
                        long plusi = index - yla*n - (n - ((index-vasen+1) % n));

                        map<char, long> s = sums[index];
                        if (vasen != 0) {
                            s = setMinus(s, sums[index - vasen]);
                            s = setUnion(sums[plusi], s);
                        }
                        s = setMinus(s, sums[index - yla*n]);
                        bool through = true;
                        for (auto x : species) {
                            if (s[x.first] <= 0) {
                                through = false;
                                break;
                            }
                        }
                        if (through and (long) s.size() == (long) sums[index].size()) {
                            answer++;
                        }
                    } else {
                        map<char, long> s = sums[index];
                        if (vasen != 0) s = setMinus(s, sums[index - vasen]);
                        bool through = true;
                        for (auto x : species) {
                            if (s[x.first] <= 0) {
                                through = false;
                                break;
                            }
                        }
                        if (through) {
                            answer++;
                        }
                    }
                }
            }
        }
    }
    cout << answer << endl; 
}

Test details

Test 1

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

Verdict:

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...

correct output
2035

user output
(empty)

Test 2

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

Verdict:

input
10
NFWQLWNWYS
DZOQJVXFPJ
CNHXPXMCQD
QRTBVNLTQC
...

correct output
9

user output
(empty)

Test 3

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

Verdict:

input
10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
...

correct output
3025

user output
(empty)

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:

input
20
BBCBUBOUOBBCUUBBCOUO
BOUCOOCUBCOOOCOBOCUO
UCCUUUOBCOCBCBUBUCOO
BUOBUCUCUOOBCOOUBUOO
...

correct output
38724

user output
(empty)

Test 7

Group: 2, 3, 4, 5, 6

Verdict:

input
20
CBGLSHGZHYZDWBNDBJUG
SMUXOJQYPXZDTMJUIWOJ
XIDSTNBGHKRKOVUVMINB
MTQGCFRUHQKALXRNCQGS
...

correct output
8334

user output
(empty)

Test 8

Group: 2, 3, 4, 5, 6

Verdict:

input
20
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
...

correct output
44100

user output
(empty)

Test 9

Group: 2, 3, 4, 5, 6

Verdict:

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...

correct output
18

user output
(empty)

Test 10

Group: 3, 4, 5, 6

Verdict:

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...

correct output
1584665

user output
(empty)

Test 11

Group: 3, 4, 5, 6

Verdict:

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...

correct output
1077746

user output
(empty)

Test 12

Group: 3, 4, 5, 6

Verdict:

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

correct output
1625625

user output
(empty)

Test 13

Group: 3, 4, 5, 6

Verdict:

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

correct output
1680

user output
(empty)

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:

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)