oj.uz

Submission #658497

# Submission time Handle Problem Language Result Execution time Memory
658497 2022-11-13T10:45:20 Z mychecksedad Cubeword (CEOI19_cubeword) C++17
21 / 100
 97 ms 6640 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 = 6;
ll dp[100][100];
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 >= 'a' && c <= 'p')) c = 'p' + (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 left = 0; left < S*S; ++left){
            int x = left / S, y = left % S;
            for(int right = 0; right < S*S; ++right){
                int z = right / S, w = right % S;

                ll p = (dp[x][y] * dp[z][w]) % MOD;

                ll P = 0;

                for(int middle = 0; middle < S*S; ++middle){
                    int k = middle / S, l = middle % S;

                    ll pp = (dp[k][l] * dp[x][k] * dp[y][l]) % MOD;
                    ll ppp = (dp[z][k] * dp[w][l]) % MOD;
                    (P += ppp * pp) %= MOD;
                }
                (P *= P) %= MOD;
                (ans += P * p) %= 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:80:16: warning: unused variable 'aa' [-Wunused-variable]
   80 |     int T = 1, aa;
      |                ^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 6492 KB Output is correct
2 Correct 82 ms 6420 KB Output is correct
3 Correct 91 ms 6464 KB Output is correct
4 Correct 77 ms 6436 KB Output is correct
5 Correct 77 ms 6524 KB Output is correct
6 Correct 77 ms 6444 KB Output is correct
7 Correct 84 ms 6500 KB Output is correct
8 Correct 97 ms 6496 KB Output is correct
9 Correct 82 ms 6444 KB Output is correct
10 Correct 77 ms 6532 KB Output is correct
11 Correct 78 ms 6396 KB Output is correct
12 Correct 80 ms 6484 KB Output is correct
13 Correct 92 ms 6640 KB Output is correct
14 Correct 85 ms 6468 KB Output is correct
15 Correct 78 ms 6464 KB Output is correct
16 Correct 81 ms 6464 KB Output is correct
17 Correct 81 ms 6488 KB Output is correct
18 Correct 92 ms 6480 KB Output is correct
19 Correct 83 ms 6484 KB Output is correct
20 Correct 80 ms 6404 KB Output is correct
21 Correct 79 ms 6480 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 6492 KB Output is correct
2 Correct 82 ms 6420 KB Output is correct
3 Correct 91 ms 6464 KB Output is correct
4 Correct 77 ms 6436 KB Output is correct
5 Correct 77 ms 6524 KB Output is correct
6 Correct 77 ms 6444 KB Output is correct
7 Correct 84 ms 6500 KB Output is correct
8 Correct 97 ms 6496 KB Output is correct
9 Correct 82 ms 6444 KB Output is correct
10 Correct 77 ms 6532 KB Output is correct
11 Correct 78 ms 6396 KB Output is correct
12 Correct 80 ms 6484 KB Output is correct
13 Correct 92 ms 6640 KB Output is correct
14 Correct 85 ms 6468 KB Output is correct
15 Correct 78 ms 6464 KB Output is correct
16 Correct 81 ms 6464 KB Output is correct
17 Correct 81 ms 6488 KB Output is correct
18 Correct 92 ms 6480 KB Output is correct
19 Correct 83 ms 6484 KB Output is correct
20 Correct 80 ms 6404 KB Output is correct
21 Correct 79 ms 6480 KB Output is correct
22 Incorrect 88 ms 5688 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 6492 KB Output is correct
2 Correct 82 ms 6420 KB Output is correct
3 Correct 91 ms 6464 KB Output is correct
4 Correct 77 ms 6436 KB Output is correct
5 Correct 77 ms 6524 KB Output is correct
6 Correct 77 ms 6444 KB Output is correct
7 Correct 84 ms 6500 KB Output is correct
8 Correct 97 ms 6496 KB Output is correct
9 Correct 82 ms 6444 KB Output is correct
10 Correct 77 ms 6532 KB Output is correct
11 Correct 78 ms 6396 KB Output is correct
12 Correct 80 ms 6484 KB Output is correct
13 Correct 92 ms 6640 KB Output is correct
14 Correct 85 ms 6468 KB Output is correct
15 Correct 78 ms 6464 KB Output is correct
16 Correct 81 ms 6464 KB Output is correct
17 Correct 81 ms 6488 KB Output is correct
18 Correct 92 ms 6480 KB Output is correct
19 Correct 83 ms 6484 KB Output is correct
20 Correct 80 ms 6404 KB Output is correct
21 Correct 79 ms 6480 KB Output is correct
22 Incorrect 88 ms 5688 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 6492 KB Output is correct
2 Correct 82 ms 6420 KB Output is correct
3 Correct 91 ms 6464 KB Output is correct
4 Correct 77 ms 6436 KB Output is correct
5 Correct 77 ms 6524 KB Output is correct
6 Correct 77 ms 6444 KB Output is correct
7 Correct 84 ms 6500 KB Output is correct
8 Correct 97 ms 6496 KB Output is correct
9 Correct 82 ms 6444 KB Output is correct
10 Correct 77 ms 6532 KB Output is correct
11 Correct 78 ms 6396 KB Output is correct
12 Correct 80 ms 6484 KB Output is correct
13 Correct 92 ms 6640 KB Output is correct
14 Correct 85 ms 6468 KB Output is correct
15 Correct 78 ms 6464 KB Output is correct
16 Correct 81 ms 6464 KB Output is correct
17 Correct 81 ms 6488 KB Output is correct
18 Correct 92 ms 6480 KB Output is correct
19 Correct 83 ms 6484 KB Output is correct
20 Correct 80 ms 6404 KB Output is correct
21 Correct 79 ms 6480 KB Output is correct
22 Incorrect 88 ms 5688 KB Output isn't correct
23 Halted 0 ms 0 KB -