CSES - Datatähti 2025 alku - Results
Submission details
Task:Niitty
Sender:Vludo
Submission time:2024-10-28 21:30:10 +0200
Language:C++ (C++20)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
#60
Test results
testverdicttimegroup
#10.01 s1, 2, 3, 4, 5, 6details
#20.00 s1, 2, 3, 4, 5, 6details
#30.01 s1, 2, 3, 4, 5, 6details
#4ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#5ACCEPTED0.00 s1, 2, 3, 4, 5, 6details
#60.01 s2, 3, 4, 5, 6details
#70.01 s2, 3, 4, 5, 6details
#80.01 s2, 3, 4, 5, 6details
#90.01 s2, 3, 4, 5, 6details
#100.04 s3, 4, 5, 6details
#110.03 s3, 4, 5, 6details
#120.04 s3, 4, 5, 6details
#130.01 s3, 4, 5, 6details
#140.29 s4, 5, 6details
#150.35 s4, 5, 6details
#160.30 s4, 5, 6details
#170.01 s4, 5, 6details
#18--5, 6details
#19--5, 6details
#20--5, 6details
#210.25 s5, 6details
#22--6details
#23--6details
#24--6details
#25--6details

Code

#include<bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define forN(i,k,n) for(int i=k;i<n;++i)
#define pb push_back
#define F first
#define S second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define inf ((int)(1.01e9))
#define N ((int)(505))

int n, letters, L, counter;
char a[N][N];
int z[26][N][N], K[26];
// bool vis[N][N][N][N];

unordered_map<ll, bool> mem;

ll hashed(pii l, pii r) {
    return l.F+l.S*32157+r.F*32094280+r.S*283242473;
}

bool check(pii l, pii r) {
    int c;
    forn(h,26) if (K[h]) {
        c = z[h][r.F+1][r.S+1] - z[h][l.F][r.S+1] 
            - z[h][r.F+1][l.S] + z[h][l.F][l.S];
        if (!c) return false;
    }
    return true;
}


void haku() {
    queue<pair<pii,pii>> bfs;
    bfs.push({{0, 0}, {n-1, n-1}});
    //mem[hashed({0,0},{n-1,n-1})]=1;
    //vis[0][0][n-1][n-1]=1;

    while (bfs.size()) {
        auto [l, r] = bfs.front();
        bfs.pop();

        //if (mem.find(l.F+l.S*32157+r.F*32094280+r.S*283242473) != mem.end()) 
         //   return;
        if (!check(l, r)) continue;

        counter++;
        //mem[l.F+l.S*32157+r.F*32094280+r.S*283242473]=1;
        

        //cout<<l.F<<' '<<l.S<<endl<<r.F<<' '<<r.S<<endl<<endl;

        // 0
        if (l.F < r.F && mem.find(hashed({l.F+1,l.S},{r.F,r.S}))==mem.end()) {
            mem[hashed({l.F+1,l.S},{r.F,r.S})]=true;
            bfs.push({{l.F+1,l.S}, r});
        }
        // 1
        if (l.S < r.S && mem.find(hashed({l.F,l.S+1},{r.F,r.S}))==mem.end()) {
            mem[hashed({l.F,l.S+1},{r.F,r.S})]=true;
            bfs.push({{l.F,l.S+1}, r});
        }
        // 2
        if (l.F < r.F && mem.find(hashed({l.F,l.S},{r.F-1,r.S}))==mem.end()) {
            mem[hashed({l.F,l.S},{r.F-1,r.S})]=true;
            bfs.push({l, {r.F-1, r.S}});
        }
        // 3
        if (l.S < r.S && mem.find(hashed({l.F,l.S},{r.F,r.S-1}))==mem.end()) {
            mem[hashed({l.F,l.S},{r.F,r.S-1})]=true;
            bfs.push({l, {r.F, l.S-1}});
        }
    }
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);
    
    cin >> n;
    forn(i,n) forn(j,n) {
        char ina;
        cin >> ina;
        a[i][j] = ina;
        K[ina-'A']++;
    }

    forn(k, 26) forn(i,n) forn(j,n) {
        z[k][i+1][j+1] = z[k][i][j+1] + z[k][i+1][j] - z[k][i][j];
        z[k][i + 1][j + 1] += (a[i][j] == 'A'+k);
    }

    forn(i,26) if (K[i]) letters++; 
    L = letters;
    counter = 0;

    haku();
    
    cout << counter << endl;
}

Test details

Test 1

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

Verdict:

input
10
TNCTNPNTPC
NPPNTNTPTP
NTNTTCNTCT
NPCPNPPNTT
...

correct output
2035

user output
389

Test 2

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

Verdict:

input
10
NFWQLWNWYS
DZOQJVXFPJ
CNHXPXMCQD
QRTBVNLTQC
...

correct output
9

user output
3

Test 3

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

Verdict:

input
10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
...

correct output
3025

user output
550

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
3896

Test 7

Group: 2, 3, 4, 5, 6

Verdict:

input
20
CBGLSHGZHYZDWBNDBJUG
SMUXOJQYPXZDTMJUIWOJ
XIDSTNBGHKRKOVUVMINB
MTQGCFRUHQKALXRNCQGS
...

correct output
8334

user output
1163

Test 8

Group: 2, 3, 4, 5, 6

Verdict:

input
20
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
KKKKKKKKKKKKKKKKKKKK
...

correct output
44100

user output
4200

Test 9

Group: 2, 3, 4, 5, 6

Verdict:

input
20
AAAAAAAAXAAAAAAAAAAA
AAAWAAAAAAAAAAAAAOAA
AAAAAAAAAAAAAAAAAPAA
AAAAAAAAKAAAAAAAAAAZ
...

correct output
18

user output
12

Test 10

Group: 3, 4, 5, 6

Verdict:

input
50
GRGREEEGREGXRXXEGXXREXGRRRGRRR...

correct output
1584665

user output
62930

Test 11

Group: 3, 4, 5, 6

Verdict:

input
50
AITIISJUHCCRZNKSDCNQKYSQRINFWJ...

correct output
1077746

user output
49371

Test 12

Group: 3, 4, 5, 6

Verdict:

input
50
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOO...

correct output
1625625

user output
63750

Test 13

Group: 3, 4, 5, 6

Verdict:

input
50
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF...

correct output
1680

user output
336

Test 14

Group: 4, 5, 6

Verdict:

input
100
NNCMDCDDCCNNNDNCMMNCDCDCCDCDNM...

correct output
25325366

user output
503387

Test 15

Group: 4, 5, 6

Verdict:

input
100
LIMQQIHASECROEVILNVULGWZJPPKOG...

correct output
22342463

user output
467959

Test 16

Group: 4, 5, 6

Verdict:

input
100
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTT...

correct output
25502500

user output
505000

Test 17

Group: 4, 5, 6

Verdict:

input
100
QXQQQQQQQQQQQQQQQQQQQQQQQQQQQQ...

correct output
25650

user output
2169

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
332349

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)