oj.uz

Submission #201058

# Submission time Handle Problem Language Result Execution time Memory
201058 2020-02-09T09:00:04 Z georgerapeanu Cubeword (CEOI19_cubeword) C++11
0 / 100
 1100 ms 7860 KB 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 998244353;

int char_to_int(char c){
    if('a' <= c && c <= 'z'){
        return c - 'a'; 
    }
    else if('A' <= c && c <= 'Z'){
        return c - 'A' + 'z' - 'a' + 1;
    }
    else{
        return c - '0' + 'Z' - 'A' + 'z' - 'a' + 2;
    }
}

int n;
string s;
vector<string> stuff[15];


int words[62][62];
int cnt[62][62][62];

int solve(vector<string> &stuff){

    if(stuff.empty()){
        return 0;
    }

    sort(stuff.begin(),stuff.end());
    stuff.resize(unique(stuff.begin(),stuff.end()) - stuff.begin());

    for(int i = 0;i < 62;i++){
        for(int j = 0;j < 62;j++){
            words[i][j] = 0;
            for(int k = 0;k < 62;k++){
                cnt[i][j][k] = 0;
            }
        }
    }

    for(auto it:stuff){
        words[char_to_int(it[0])][char_to_int(it.back())]++;
    }

    for(int a = 0;a < 62;a++){
        for(int b = 0;b < 62;b++){
            for(int c = 0;c < 62;c++){
                for(int d = 0;d < 62;d++){
                    cnt[a][b][c] = (cnt[a][b][c] + 1LL * words[a][d] * words[b][d] * words[c][d]) % MOD;
                }
            }
        }
    }

    int ans = 0;

    for(int a = 0;a < 62;a++){
        for(int b = 0;b < 62;b++){
            for(int c = 0;c < 62;c++){
                for(int d = 0;d < 62;d++){
                    ans = (ans + 1LL * (1LL * cnt[a][b][c] * cnt[a][b][d] % MOD) * (1LL * cnt[a][c][d] * cnt[b][c][d] % MOD)) % MOD;
                }
            }
        }
    }

    return ans;
}

int main(){

    cin >> n;

    for(int i = 1;i <= n;i++){
        cin >> s;
        stuff[s.size()].push_back(s);
        reverse(s.begin(),s.end());
        stuff[s.size()].push_back(s);
    }

    int ans = 0;

    for(int i = 3;i <= 10;i++){
        ans += solve(stuff[i]);
        if(ans >= MOD){
            ans -= MOD;
        }
    }

    cout << ans;

    return 0;
}

Subtask #1
0 / 21.0

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