oj.uz

Submission #448652

# Submission time Handle Problem Language Result Execution time Memory
448652 2021-07-31T11:33:33 Z marcipan5000 Cubeword (CEOI19_cubeword) C++14
0 / 100
 1100 ms 7592 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

const long long int mo=998244353;
int n;
ll t[100][100][100];
ll g[100][100];

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

void eval(string z) {
    if (z[0]!=z[z.size()-1]) {
        g[turn(z[0])][turn(z[z.size()-1])]=(g[turn(z[0])][turn(z[z.size()-1])]+1)%mo;
        g[turn(z[z.size()-1])][turn(z[0])]=(g[turn(z[z.size()-1])][turn(z[0])]+1)%mo;
        return;
    }
    bool isPal=1;
    for (int i=0;i<z.size();i++) {
        if (z[i]!=z[z.size()-1-i]) {
            isPal=0;
            break;
        }
    }
    if (isPal==0) {
        g[turn(z[0])][turn(z[z.size()-1])]=(g[turn(z[0])][turn(z[z.size()-1])]+2)%mo;
    } else {
        g[turn(z[0])][turn(z[z.size()-1])]=(g[turn(z[0])][turn(z[z.size()-1])]+1)%mo;
    }
    return;
}

vector<string> f;

bool kis(string a,string b) {
    return((a.size()<b.size())||((a.size()==b.size())&&(a<b)));
}

ll solve(int u,int v) {
    for (int i=0;i<62;i++) {
        for (int j=0;j<62;j++) {
            g[i][j]=0;
            for (int k=0;k<62;k++) {
                t[i][j][k]=0;
            }
        }
    }
    for (int i=u;i<v;i++) {
        if ((i==u)||(f[i]!=f[i-1])) {
            eval(f[i]);
        }
    }
    for (int i=0;i<62;i++) {
        for (int j=0;j<62;j++) {
            for (int k=0;k<62;k++) {
                for (int mid=0;mid<62;mid++) {
                    t[i][j][k]=(t[i][j][k]+(((g[i][mid]*g[j][mid])%mo)*g[k][mid])%mo)%mo;
                }
            }
        }
    }
    ll ans=0;
    for (int i=0;i<62;i++) {
        for (int j=0;j<62;j++) {
            for (int k=0;k<62;k++) {
                for (int l=0;l<62;l++) {
                    ans=(ans+(((((t[i][j][k]*t[i][j][l])%mo)*t[i][k][l])%mo)*t[j][k][l])%mo)%mo;
                }
            }
        }
    }
    return(ans);
}

string flip(string a) {
    string b=a;
    for (int i=0;i<a.size();i++) {
        b[a.size()-i-1]=a[i];
    }
    if (a<b) {
        return(a);
    } else {
        return(b);
    }
}

int main()
{
    cin >> n;
    string a;
    for (int i=0;i<n;i++) {
        cin >> a;
        f.push_back(flip(a));
    }
    sort(f.begin(),f.end(),kis);
    int l=0,r=0;
    ll finAns=0;
    while (r<n) {
        while ((r<n)&&(f[l].size()==f[r].size())) {
            r++;
        }
        finAns=(finAns+solve(l,r))%mo;
        l=r;
    }
    cout << finAns << endl;
    return 0;
}

/*
for (int i=0;i<62;i++) {
    for (int j=0;j<62;j++) {
        if (g[i][j]!=0) {
            cout << i << " " << j << " " << g[i][j] << endl;
        }
    }
}
*/

Compilation message

cubeword.cpp: In function 'void eval(std::string)':
cubeword.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i=0;i<z.size();i++) {
      |                  ~^~~~~~~~~
cubeword.cpp: In function 'std::string flip(std::string)':
cubeword.cpp:87:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for (int i=0;i<a.size();i++) {
      |                  ~^~~~~~~~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1187 ms 7592 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 1187 ms 7592 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 1187 ms 7592 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 1187 ms 7592 KB Time limit exceeded
2 Halted 0 ms 0 KB -