oj.uz

Submission #445673

# Submission time Handle Problem Language Result Execution time Memory
445673 2021-07-19T08:44:19 Z Haruto810198 Cubeword (CEOI19_cubeword) C++17
0 / 100
 1100 ms 6680 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 = 16; /// Subtask 2

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 half_cnt[4097];

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, 4095, 1){
            half_cnt[i] = 0;
        }

        FOR(i, 0, 4095, 1){

            int B = (i>>8) & 15;
            int D = (i>>4) & 15;
            int E = i & 15;

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

        }

        /// another half

        FOR(i, 0, 4095, 1){
            FOR(j, 0, 4095, 1){

                int B = ((i>>8) & 15);
                int D = ((i>>4) & 15);
                int E = (i & 15);

                int H = ((j>>8) & 15);
                int F = ((j>>4) & 15);
                int C = (j & 15);

                //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 AAA = (edge_cnt[B][F] * edge_cnt[D][H] * edge_cnt[E][H]) % mod;
                int BBB = (edge_cnt[B][C] * edge_cnt[D][C] * edge_cnt[E][F]) % mod;

                int BDEHFC = (AAA * BBB) % mod;

                res += (((half_cnt[i] * half_cnt[j]) % mod) * BDEHFC) % mod;

            }

            res %= mod;

        }

    }

    cout<<res<<'\n';

    return 0;

}

Subtask #1
0 / 21.0

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