oj.uz

Submission #445665

# Submission time Handle Problem Language Result Execution time Memory
445665 2021-07-19T08:28:01 Z Haruto810198 Cubeword (CEOI19_cubeword) C++17
21 / 100
 161 ms 17764 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i,l,r,d) for(int i=(l);i<=(r);i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int,int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 65;
int SZ = 6; /// Subtask 1

int n;
map<char, int> char_id;

vector<string> strings[11];

set<string> edges[MAX][MAX];

int edge_cnt[MAX][MAX];
int half_cnt[MAX][MAX][MAX];

int res;

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    /// a~p -> 0~15
    for(char i='a'; i<='p'; i++){
        char_id[i] = i - 'a';
    }

    /// A~P -> 16~31
    for(char i='A'; i<='P'; i++){
        char_id[i] = i - 'A' + 16;
    }

    /// q~z -> 32~41
    for(char i='q'; i<='z'; i++){
        char_id[i] = i - 'a' + 16;
    }

    /// Q~Z -> 42~51
    for(char i='Q'; i<='Z'; i++){
        char_id[i] = i - 'A' + 26;
    }

    /// 0~9 -> 52~61
    for(char i='0'; i<='9'; i++){
        char_id[i] = i - '0' + 52;
    }

    cin>>n;

    FOR(i, 1, n, 1){
        string str;
        cin>>str;
        strings[szof(str)].pb(str);
    }

    /// L = len. of strings
    FOR(L, 3, 10, 1){

        FOR(i, 0, SZ-1, 1){
            FOR(j, 0, SZ-1, 1){
                edges[i][j].clear();
            }
        }

        for(string S : strings[L]){
            int u = char_id[ S[0] ];
            int v = char_id[ S[L-1] ];
            edges[u][v].insert(S);
            reverse(S.begin(), S.end());
            edges[v][u].insert(S);
        }

        FOR(i, 0, SZ-1, 1){
            FOR(j, 0, SZ-1, 1){
                edge_cnt[i][j] = szof(edges[i][j]);
            }
        }

        /// one half

        FOR(i, 0, SZ-1, 1){
            FOR(j, 0, SZ-1, 1){
                FOR(k, 0, SZ-1, 1){
                    half_cnt[i][j][k] = 0;
                }
            }
        }

        FOR(A, 0, SZ-1, 1){
            FOR(B, 0, SZ-1, 1){
                FOR(D, 0, SZ-1, 1){
                    FOR(E, 0, SZ-1, 1){
                        half_cnt[B][D][E] += edge_cnt[A][B] * edge_cnt[A][D] * edge_cnt[A][E];
                        half_cnt[B][D][E] %= mod;
                    }
                }
            }
        }

        /// another half

        FOR(B, 0, SZ-1, 1){
            FOR(D, 0, SZ-1, 1){
                FOR(E, 0, SZ-1, 1){
                    FOR(H, 0, SZ-1, 1){
                        FOR(F, 0, SZ-1, 1){
                            FOR(C, 0, SZ-1, 1){

                                int BFC = (edge_cnt[B][F] * edge_cnt[B][C]) % mod;
                                int DHC = (edge_cnt[D][H] * edge_cnt[D][C]) % mod;
                                int EHF = (edge_cnt[E][H] * edge_cnt[E][F]) % mod;

                                int BDEHFC = (((BFC * DHC) % mod) * EHF) % mod;

                                res += (((half_cnt[B][D][E] * half_cnt[F][H][C]) % mod) * BDEHFC) % mod;
                                res %= mod;

                            }
                        }
                    }
                }
            }
        }

    }

    cout<<res<<'\n';

    return 0;

}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 6704 KB Output is correct
2 Correct 85 ms 7528 KB Output is correct
3 Correct 83 ms 7612 KB Output is correct
4 Correct 84 ms 7636 KB Output is correct
5 Correct 88 ms 7600 KB Output is correct
6 Correct 88 ms 7568 KB Output is correct
7 Correct 83 ms 7492 KB Output is correct
8 Correct 86 ms 7584 KB Output is correct
9 Correct 84 ms 7556 KB Output is correct
10 Correct 111 ms 7568 KB Output is correct
11 Correct 85 ms 7524 KB Output is correct
12 Correct 82 ms 7588 KB Output is correct
13 Correct 95 ms 7576 KB Output is correct
14 Correct 87 ms 7620 KB Output is correct
15 Correct 115 ms 7724 KB Output is correct
16 Correct 94 ms 7576 KB Output is correct
17 Correct 83 ms 7596 KB Output is correct
18 Correct 90 ms 7532 KB Output is correct
19 Correct 86 ms 7500 KB Output is correct
20 Correct 84 ms 7484 KB Output is correct
21 Correct 86 ms 7584 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 6704 KB Output is correct
2 Correct 85 ms 7528 KB Output is correct
3 Correct 83 ms 7612 KB Output is correct
4 Correct 84 ms 7636 KB Output is correct
5 Correct 88 ms 7600 KB Output is correct
6 Correct 88 ms 7568 KB Output is correct
7 Correct 83 ms 7492 KB Output is correct
8 Correct 86 ms 7584 KB Output is correct
9 Correct 84 ms 7556 KB Output is correct
10 Correct 111 ms 7568 KB Output is correct
11 Correct 85 ms 7524 KB Output is correct
12 Correct 82 ms 7588 KB Output is correct
13 Correct 95 ms 7576 KB Output is correct
14 Correct 87 ms 7620 KB Output is correct
15 Correct 115 ms 7724 KB Output is correct
16 Correct 94 ms 7576 KB Output is correct
17 Correct 83 ms 7596 KB Output is correct
18 Correct 90 ms 7532 KB Output is correct
19 Correct 86 ms 7500 KB Output is correct
20 Correct 84 ms 7484 KB Output is correct
21 Correct 86 ms 7584 KB Output is correct
22 Incorrect 161 ms 17764 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 6704 KB Output is correct
2 Correct 85 ms 7528 KB Output is correct
3 Correct 83 ms 7612 KB Output is correct
4 Correct 84 ms 7636 KB Output is correct
5 Correct 88 ms 7600 KB Output is correct
6 Correct 88 ms 7568 KB Output is correct
7 Correct 83 ms 7492 KB Output is correct
8 Correct 86 ms 7584 KB Output is correct
9 Correct 84 ms 7556 KB Output is correct
10 Correct 111 ms 7568 KB Output is correct
11 Correct 85 ms 7524 KB Output is correct
12 Correct 82 ms 7588 KB Output is correct
13 Correct 95 ms 7576 KB Output is correct
14 Correct 87 ms 7620 KB Output is correct
15 Correct 115 ms 7724 KB Output is correct
16 Correct 94 ms 7576 KB Output is correct
17 Correct 83 ms 7596 KB Output is correct
18 Correct 90 ms 7532 KB Output is correct
19 Correct 86 ms 7500 KB Output is correct
20 Correct 84 ms 7484 KB Output is correct
21 Correct 86 ms 7584 KB Output is correct
22 Incorrect 161 ms 17764 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 6704 KB Output is correct
2 Correct 85 ms 7528 KB Output is correct
3 Correct 83 ms 7612 KB Output is correct
4 Correct 84 ms 7636 KB Output is correct
5 Correct 88 ms 7600 KB Output is correct
6 Correct 88 ms 7568 KB Output is correct
7 Correct 83 ms 7492 KB Output is correct
8 Correct 86 ms 7584 KB Output is correct
9 Correct 84 ms 7556 KB Output is correct
10 Correct 111 ms 7568 KB Output is correct
11 Correct 85 ms 7524 KB Output is correct
12 Correct 82 ms 7588 KB Output is correct
13 Correct 95 ms 7576 KB Output is correct
14 Correct 87 ms 7620 KB Output is correct
15 Correct 115 ms 7724 KB Output is correct
16 Correct 94 ms 7576 KB Output is correct
17 Correct 83 ms 7596 KB Output is correct
18 Correct 90 ms 7532 KB Output is correct
19 Correct 86 ms 7500 KB Output is correct
20 Correct 84 ms 7484 KB Output is correct
21 Correct 86 ms 7584 KB Output is correct
22 Incorrect 161 ms 17764 KB Output isn't correct
23 Halted 0 ms 0 KB -