oj.uz

Submission #1025516

# Submission time Handle Problem Language Result Execution time Memory
1025516 2024-07-17T05:54:30 Z 변재우(#10944) Cubeword (CEOI19_cubeword) C++17
0 / 100
 1100 ms 9884 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int Nmax=100010, M=62, Mod=998244353;
int N, ans, cnt[M][M], val[M][M][M];
string S[Nmax];

int f(char x) {
    if('a'<=x && x<='z') return x-'a';
    else if('A'<=x && x<='Z') return x-'A'+26;
    else return x-'0'+52;
}

void solve(vector<string> V) {
    map<string, bool> chk;
    for(int i=0; i<V.size(); i++) {
        string tmp=V[i];
        reverse(tmp.begin(), tmp.end());
        if(chk[tmp]) {
            swap(V[i], V.back()); V.pop_back();
            i--; continue;
        }
        chk[V[i]]=true;
    }
    for(int i=0; i<M; i++) for(int j=0; j<M; j++) cnt[i][j]=0;
    for(int i=0; i<V.size(); i++) {
        int l=f(V[i][0]), r=f(V[i].back());
        cnt[l][r]++;
        string t=V[i]; reverse(t.begin(), t.end());
        if(l!=r || V[i]!=t) cnt[r][l]++;
    }
    for(int i=0; i<M; i++) for(int j=0; j<M; j++) for(int k=0; k<M; k++) {
        val[i][j][k]=0;
        for(int l=0; l<M; l++) val[i][j][k]=(val[i][j][k]+((cnt[i][l]*cnt[j][l])%Mod)*cnt[k][l])%Mod;
    }
    for(int a=0; a<M; a++) for(int b=0; b<M; b++) for(int c=0; c<M; c++) for(int d=0; d<M; d++)
        ans=(ans+((val[a][b][c]*val[a][b][d])%Mod)*((val[a][c][d]*val[b][c][d])%Mod))%Mod;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N;
    for(int i=1; i<=N; i++) cin>>S[i];
    for(int i=3; i<=10; i++) {
        vector<string> v;
        for(int j=1; j<=N; j++) if(S[j].size()==i) v.push_back(S[j]);
        solve(v);
    }
    cout<<ans;
    return 0;
}

Compilation message

cubeword.cpp: In function 'void solve(std::vector<std::__cxx11::basic_string<char> >)':
cubeword.cpp:17:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0; i<V.size(); i++) {
      |                  ~^~~~~~~~~
cubeword.cpp:27:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0; i<V.size(); i++) {
      |                  ~^~~~~~~~~
cubeword.cpp: In function 'int main()':
cubeword.cpp:47:47: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   47 |         for(int j=1; j<=N; j++) if(S[j].size()==i) v.push_back(S[j]);
      |                                    ~~~~~~~~~~~^~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1119 ms 9884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1119 ms 9884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1119 ms 9884 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1119 ms 9884 KB Time limit exceeded
2 Halted 0 ms 0 KB -