oj.uz

Submission #541279

# Submission time Handle Problem Language Result Execution time Memory
541279 2022-03-22T22:00:48 Z Deepesson Cubeword (CEOI19_cubeword) C++17
50 / 100
 403 ms 23160 KB 
#include <bits/stdc++.h>
#define MAX 105000
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
std::vector<std::string> words[MAX];
int N;
const long long MOD = 998244353;
long long tabela[300][300];
typedef std::array<std::array<long long,2>,2> matriz;
matriz mul(matriz a,matriz b){
    matriz c={};
    for(int i=0;i!=2;++i){
        for(int j=0;j!=2;++j){
            for(int k=0;k!=2;++k){
                c[i][j]=(c[i][j]+(a[i][j]*b[j][k]))%MOD;
            }
        }
    }
}
matriz gera(long long delta){
    matriz a={};
    a[0][0]=1;
    a[1][1]=1;
    a[1][0]=delta;
    return a;
}
int letra(char ch){
    if(ch>='a'&&ch<='p'){
        return ch-'a';
    }else {
        return (ch-'A')+('p'-'a'+1);
    }
}
void iniciar(int x){
    std::map<std::string,bool> mapa;
    memset(&tabela[0][0],0,sizeof(tabela));
    for(auto&z:words[x]){
        mapa[z]=true;
        std::reverse(z.begin(),z.end());
        mapa[z]=true;
    }
    for(auto&x:mapa){
        tabela[letra(x.first[0])][letra(x.first.back())]++;
    }
}
#define TOT 20
long long tab[TOT][TOT][TOT][TOT][10];

matriz neutro;
long long solve(void){
    ///Fase 6 O(N^4)
    for(int i=0;i!=TOT;++i){
        for(int j=0;j!=TOT;++j){
            for(int k=0;k!=TOT;++k){
                tab[0][i][j][k][6]=0;
                for(int u=0;u!=TOT;++u){
                    tab[0][i][j][k][6]=(tab[0][i][j][k][6]+((tabela[i][u]*tabela[j][u])%MOD)*tabela[k][u])%MOD;
                }
            }
        }
    }
    ///Fase 5 O(N^5)
    for(int i=0;i!=TOT;++i){
        for(int j=0;j!=TOT;++j){
            for(int k=0;k!=TOT;++k){
                for(int u=0;u!=TOT;++u){
                    tab[i][j][k][u][5]=0;
                    for(int v=0;v!=TOT;++v){
                        tab[i][j][k][u][5]=(
                                            tab[i][j][k][u][5]+
                                            ((tab[0][v][k][u][6]*(
                                                                     (tabela[i][v]*tabela[j][v])%MOD
                                                                     ))
                                             %MOD))
                                            %MOD;
                    }
                }
            }
        }
    }

    ///Fase 4 O(N^5)
    for(int i=0;i!=TOT;++i){
        for(int j=0;j!=TOT;++j){
            for(int k=0;k!=TOT;++k){
                for(int u=0;u!=TOT;++u){
                    tab[i][j][k][u][4]=0;
                    for(int v=0;v!=TOT;++v){
                        tab[i][j][k][u][4]=(
                                            tab[i][j][k][u][4]+
                                            ((tab[i][j][v][u][5]*(
                                                                     (tabela[i][v]*tabela[k][v])%MOD
                                                                     ))
                                             %MOD))
                                            %MOD;
                    }
                }
            }
        }
    }

    ///Fase 3 O(N^4)
    for(int i=0;i!=TOT;++i){
        for(int j=0;j!=TOT;++j){
            for(int k=0;k!=TOT;++k){
                tab[i][j][k][0][3]=0;
                for(int v=0;v!=TOT;++v){
                    tab[i][j][k][0][3]=(
                                        tab[i][j][k][0][3]+
                                        ((tab[i][j][k][v][4]*(
                                                                    (tabela[j][v]*tabela[k][v])%MOD
                                                                    ))
                                             %MOD))
                                            %MOD;
                }
            }
        }
    }
    ///Fase 2 O(N^4)
    for(int i=0;i!=TOT;++i){
        for(int j=0;j!=TOT;++j){
            for(int k=0;k!=TOT;++k){
                tab[i][j][k][0][2]=0;
                for(int v=0;v!=TOT;++v){
                    tab[i][j][k][0][2]=(
                                        tab[i][j][k][0][2]+
                                        ((tab[v][j][k][0][3]*(
                                                                    (tabela[i][v])%MOD
                                                                    ))
                                             %MOD))
                                            %MOD;
                }
            }
        }
    }
    ///Fase 1 O(N^3)
        for(int i=0;i!=TOT;++i){
            for(int j=0;j!=TOT;++j){
                tab[i][j][0][0][1]=0;
                for(int v=0;v!=TOT;++v){
                    tab[i][j][0][0][1]=(
                                        tab[i][j][0][0][1]+
                                        ((tab[i][j][v][0][2]*(
                                                                    (tabela[i][v])%MOD
                                                                    ))
                                             %MOD))
                                            %MOD;
                }
            }
        }
    ///Fase 0 O(N^2)
        for(int i=0;i!=TOT;++i){
                tab[i][0][0][0][0]=0;
                for(int v=0;v!=TOT;++v){
                    tab[i][0][0][0][0]=(
                                        tab[i][0][0][0][0]+
                                        ((tab[i][v][0][0][1]*(
                                                                    (tabela[i][v])%MOD
                                                                    ))
                                             %MOD))
                                            %MOD;
                }
            }
    long long resp=0;
    for(int i=0;i!=TOT;++i)resp=(resp+tab[i][0][0][0][0])%MOD;
    return resp;
}
int main()
{
    neutro[0][0]=neutro[1][1]=1;
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>N;
    for(int i=0;i!=N;++i){
        std::string k;
        std::cin>>k;
        words[k.size()].push_back(k);
    }
    long long tot = 0;
    for(int i=3;i!=11;++i){
        iniciar(i);
        tot = (tot+solve())%MOD;
    }
    std::cout<<tot<<"\n";
}

Compilation message

cubeword.cpp: In function 'matriz mul(matriz, matriz)':
cubeword.cpp:19:1: warning: no return statement in function returning non-void [-Wreturn-type]
   19 | }
      | ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 22292 KB Output is correct
2 Correct 388 ms 23040 KB Output is correct
3 Correct 392 ms 22996 KB Output is correct
4 Correct 386 ms 23044 KB Output is correct
5 Correct 403 ms 23144 KB Output is correct
6 Correct 399 ms 22920 KB Output is correct
7 Correct 384 ms 23076 KB Output is correct
8 Correct 385 ms 23160 KB Output is correct
9 Correct 384 ms 23016 KB Output is correct
10 Correct 386 ms 23120 KB Output is correct
11 Correct 381 ms 23060 KB Output is correct
12 Correct 382 ms 23068 KB Output is correct
13 Correct 390 ms 22964 KB Output is correct
14 Correct 381 ms 23068 KB Output is correct
15 Correct 387 ms 23032 KB Output is correct
16 Correct 383 ms 23040 KB Output is correct
17 Correct 395 ms 23064 KB Output is correct
18 Correct 392 ms 22972 KB Output is correct
19 Correct 379 ms 23064 KB Output is correct
20 Correct 388 ms 23132 KB Output is correct
21 Correct 385 ms 22992 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 22292 KB Output is correct
2 Correct 388 ms 23040 KB Output is correct
3 Correct 392 ms 22996 KB Output is correct
4 Correct 386 ms 23044 KB Output is correct
5 Correct 403 ms 23144 KB Output is correct
6 Correct 399 ms 22920 KB Output is correct
7 Correct 384 ms 23076 KB Output is correct
8 Correct 385 ms 23160 KB Output is correct
9 Correct 384 ms 23016 KB Output is correct
10 Correct 386 ms 23120 KB Output is correct
11 Correct 381 ms 23060 KB Output is correct
12 Correct 382 ms 23068 KB Output is correct
13 Correct 390 ms 22964 KB Output is correct
14 Correct 381 ms 23068 KB Output is correct
15 Correct 387 ms 23032 KB Output is correct
16 Correct 383 ms 23040 KB Output is correct
17 Correct 395 ms 23064 KB Output is correct
18 Correct 392 ms 22972 KB Output is correct
19 Correct 379 ms 23064 KB Output is correct
20 Correct 388 ms 23132 KB Output is correct
21 Correct 385 ms 22992 KB Output is correct
22 Correct 383 ms 22092 KB Output is correct
23 Correct 387 ms 22216 KB Output is correct
24 Correct 400 ms 22108 KB Output is correct
25 Correct 390 ms 22128 KB Output is correct
26 Correct 380 ms 22200 KB Output is correct
27 Correct 384 ms 22084 KB Output is correct
28 Correct 381 ms 22164 KB Output is correct
29 Correct 391 ms 22144 KB Output is correct
30 Correct 388 ms 22080 KB Output is correct
31 Correct 374 ms 22164 KB Output is correct
32 Correct 374 ms 22212 KB Output is correct
33 Correct 376 ms 22232 KB Output is correct
34 Correct 379 ms 22148 KB Output is correct
35 Correct 382 ms 22132 KB Output is correct
36 Correct 374 ms 22148 KB Output is correct
37 Correct 389 ms 22196 KB Output is correct
38 Correct 402 ms 22164 KB Output is correct
39 Correct 384 ms 22120 KB Output is correct
40 Correct 377 ms 22112 KB Output is correct
41 Correct 382 ms 22316 KB Output is correct
42 Correct 378 ms 22184 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 22292 KB Output is correct
2 Correct 388 ms 23040 KB Output is correct
3 Correct 392 ms 22996 KB Output is correct
4 Correct 386 ms 23044 KB Output is correct
5 Correct 403 ms 23144 KB Output is correct
6 Correct 399 ms 22920 KB Output is correct
7 Correct 384 ms 23076 KB Output is correct
8 Correct 385 ms 23160 KB Output is correct
9 Correct 384 ms 23016 KB Output is correct
10 Correct 386 ms 23120 KB Output is correct
11 Correct 381 ms 23060 KB Output is correct
12 Correct 382 ms 23068 KB Output is correct
13 Correct 390 ms 22964 KB Output is correct
14 Correct 381 ms 23068 KB Output is correct
15 Correct 387 ms 23032 KB Output is correct
16 Correct 383 ms 23040 KB Output is correct
17 Correct 395 ms 23064 KB Output is correct
18 Correct 392 ms 22972 KB Output is correct
19 Correct 379 ms 23064 KB Output is correct
20 Correct 388 ms 23132 KB Output is correct
21 Correct 385 ms 22992 KB Output is correct
22 Correct 383 ms 22092 KB Output is correct
23 Correct 387 ms 22216 KB Output is correct
24 Correct 400 ms 22108 KB Output is correct
25 Correct 390 ms 22128 KB Output is correct
26 Correct 380 ms 22200 KB Output is correct
27 Correct 384 ms 22084 KB Output is correct
28 Correct 381 ms 22164 KB Output is correct
29 Correct 391 ms 22144 KB Output is correct
30 Correct 388 ms 22080 KB Output is correct
31 Correct 374 ms 22164 KB Output is correct
32 Correct 374 ms 22212 KB Output is correct
33 Correct 376 ms 22232 KB Output is correct
34 Correct 379 ms 22148 KB Output is correct
35 Correct 382 ms 22132 KB Output is correct
36 Correct 374 ms 22148 KB Output is correct
37 Correct 389 ms 22196 KB Output is correct
38 Correct 402 ms 22164 KB Output is correct
39 Correct 384 ms 22120 KB Output is correct
40 Correct 377 ms 22112 KB Output is correct
41 Correct 382 ms 22316 KB Output is correct
42 Correct 378 ms 22184 KB Output is correct
43 Incorrect 378 ms 22036 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 22292 KB Output is correct
2 Correct 388 ms 23040 KB Output is correct
3 Correct 392 ms 22996 KB Output is correct
4 Correct 386 ms 23044 KB Output is correct
5 Correct 403 ms 23144 KB Output is correct
6 Correct 399 ms 22920 KB Output is correct
7 Correct 384 ms 23076 KB Output is correct
8 Correct 385 ms 23160 KB Output is correct
9 Correct 384 ms 23016 KB Output is correct
10 Correct 386 ms 23120 KB Output is correct
11 Correct 381 ms 23060 KB Output is correct
12 Correct 382 ms 23068 KB Output is correct
13 Correct 390 ms 22964 KB Output is correct
14 Correct 381 ms 23068 KB Output is correct
15 Correct 387 ms 23032 KB Output is correct
16 Correct 383 ms 23040 KB Output is correct
17 Correct 395 ms 23064 KB Output is correct
18 Correct 392 ms 22972 KB Output is correct
19 Correct 379 ms 23064 KB Output is correct
20 Correct 388 ms 23132 KB Output is correct
21 Correct 385 ms 22992 KB Output is correct
22 Correct 383 ms 22092 KB Output is correct
23 Correct 387 ms 22216 KB Output is correct
24 Correct 400 ms 22108 KB Output is correct
25 Correct 390 ms 22128 KB Output is correct
26 Correct 380 ms 22200 KB Output is correct
27 Correct 384 ms 22084 KB Output is correct
28 Correct 381 ms 22164 KB Output is correct
29 Correct 391 ms 22144 KB Output is correct
30 Correct 388 ms 22080 KB Output is correct
31 Correct 374 ms 22164 KB Output is correct
32 Correct 374 ms 22212 KB Output is correct
33 Correct 376 ms 22232 KB Output is correct
34 Correct 379 ms 22148 KB Output is correct
35 Correct 382 ms 22132 KB Output is correct
36 Correct 374 ms 22148 KB Output is correct
37 Correct 389 ms 22196 KB Output is correct
38 Correct 402 ms 22164 KB Output is correct
39 Correct 384 ms 22120 KB Output is correct
40 Correct 377 ms 22112 KB Output is correct
41 Correct 382 ms 22316 KB Output is correct
42 Correct 378 ms 22184 KB Output is correct
43 Incorrect 378 ms 22036 KB Output isn't correct
44 Halted 0 ms 0 KB -