oj.uz

Submission #658578

# Submission time Handle Problem Language Result Execution time Memory
658578 2022-11-13T15:04:06 Z mychecksedad Cubeword (CEOI19_cubeword) C++17
0 / 100
 1100 ms 9112 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD1 (1000000000+7)
#define MOD (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;

int n, S = 63;
ll dp[100][100], d[70][70][70];
vector<string> s[15];
bool is_palindrome(string &a){
    bool ok = 1;
    int x = a.length();
    for(int i = 0; i < x / 2; ++i) ok &= (a[i] == a[x - i - 1]);

    return ok;
}
void solve(){
    cin >> n;
    for(int i = 0; i < n; ++i){
        string a; cin >> a;
        for(char &c: a){
            if(c >= '0' && c <= '9'){
                c = 'z' + 26 + (c - '0') + 1;
            }
            else if(!(c >= 'a' && c <= 'z')){
                c = 'z' + (c - 'A') + 1;
            }
        }
        s[a.length()].pb(a);
    }
    ll ans = 0;
    for(int i = 1; i < 15; ++i){
        if(s[i].empty()) continue;
        for(int j = 0; j < S; ++j) for(int k = 0; k < S; ++k) dp[j][k] = 0;
        
        map<string, bool> used;
        for(auto a: s[i]){
            if(used[a]) continue;
            if(is_palindrome(a)){
                dp[a[0] - 'a'][a[0] - 'a']++;
            }else{
                dp[a[0] - 'a'][a.back() - 'a']++;
                dp[a.back() - 'a'][a[0] - 'a']++;
            }
            reverse(all(a));
            used[a] = 1;
        }


        for(int a = 0; a < S; ++a){
            for(int b = 0; b < S; ++b){
                for(int c = 0; c < S; ++c){
                    d[a][b][c] = 0;
                    for(int l = 0; l < S; ++l){
                        (d[a][b][c] += dp[a][l] * dp[b][l] * dp[c][l]) %= MOD;
                    }   
                }
            }
        }

        for(int a = 0; a < S; ++a){
            for(int b = 0; b < S; ++b){
                for(int c = 0; c < S; ++c){
                    for(int e = 0; e < S; ++e){
                        (ans += (d[a][b][c] * d[a][b][e] % MOD) * (d[a][c][e] * d[b][c][e] % MOD)) %= MOD;
                    }   
                }
            }
        }

    }
    cout << ans;
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
    }
    return 0;
 
}

Compilation message

cubeword.cpp: In function 'int main()':
cubeword.cpp:91:16: warning: unused variable 'aa' [-Wunused-variable]
   91 |     int T = 1, aa;
      |                ^~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1059 ms 9072 KB Output is correct
2 Correct 1082 ms 9068 KB Output is correct
3 Correct 1053 ms 8984 KB Output is correct
4 Correct 1062 ms 9112 KB Output is correct
5 Correct 1077 ms 9008 KB Output is correct
6 Correct 1076 ms 8944 KB Output is correct
7 Correct 1077 ms 9096 KB Output is correct
8 Correct 1078 ms 9004 KB Output is correct
9 Correct 1094 ms 8928 KB Output is correct
10 Correct 1073 ms 9064 KB Output is correct
11 Correct 1067 ms 8900 KB Output is correct
12 Correct 1062 ms 9048 KB Output is correct
13 Execution timed out 1107 ms 9008 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1059 ms 9072 KB Output is correct
2 Correct 1082 ms 9068 KB Output is correct
3 Correct 1053 ms 8984 KB Output is correct
4 Correct 1062 ms 9112 KB Output is correct
5 Correct 1077 ms 9008 KB Output is correct
6 Correct 1076 ms 8944 KB Output is correct
7 Correct 1077 ms 9096 KB Output is correct
8 Correct 1078 ms 9004 KB Output is correct
9 Correct 1094 ms 8928 KB Output is correct
10 Correct 1073 ms 9064 KB Output is correct
11 Correct 1067 ms 8900 KB Output is correct
12 Correct 1062 ms 9048 KB Output is correct
13 Execution timed out 1107 ms 9008 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1059 ms 9072 KB Output is correct
2 Correct 1082 ms 9068 KB Output is correct
3 Correct 1053 ms 8984 KB Output is correct
4 Correct 1062 ms 9112 KB Output is correct
5 Correct 1077 ms 9008 KB Output is correct
6 Correct 1076 ms 8944 KB Output is correct
7 Correct 1077 ms 9096 KB Output is correct
8 Correct 1078 ms 9004 KB Output is correct
9 Correct 1094 ms 8928 KB Output is correct
10 Correct 1073 ms 9064 KB Output is correct
11 Correct 1067 ms 8900 KB Output is correct
12 Correct 1062 ms 9048 KB Output is correct
13 Execution timed out 1107 ms 9008 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1059 ms 9072 KB Output is correct
2 Correct 1082 ms 9068 KB Output is correct
3 Correct 1053 ms 8984 KB Output is correct
4 Correct 1062 ms 9112 KB Output is correct
5 Correct 1077 ms 9008 KB Output is correct
6 Correct 1076 ms 8944 KB Output is correct
7 Correct 1077 ms 9096 KB Output is correct
8 Correct 1078 ms 9004 KB Output is correct
9 Correct 1094 ms 8928 KB Output is correct
10 Correct 1073 ms 9064 KB Output is correct
11 Correct 1067 ms 8900 KB Output is correct
12 Correct 1062 ms 9048 KB Output is correct
13 Execution timed out 1107 ms 9008 KB Time limit exceeded
14 Halted 0 ms 0 KB -