oj.uz

Submission #201062

# Submission time Handle Problem Language Result Execution time Memory
201062 2020-02-09T09:20:05 Z georgerapeanu Cubeword (CEOI19_cubeword) C++11
0 / 100
 494 ms 7600 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 fact[] = {1,1,2,6,24};

int get_cnt(vector<int> v){
    int lst = -1;
    int cnt = 0;
    int ans = fact[4];

    for(auto it:v){
        if(lst == it){
            cnt++;
        }
        else{
            ans /= fact[cnt];
            lst = it;
            cnt = 1;
        }
    }
    
    ans /= fact[cnt];

    return ans;
}

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 = i;j < 62;j++){
            words[i][j] = 0;
            for(int k = j;k < 62;k++){
                cnt[i][j][k] = 0;
            }
        }
    }

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

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

    int ans = 0;

    for(int a = 0;a < 62;a++){
        for(int b = a;b < 62;b++){
            for(int c = b;c < 62;c++){
                for(int d = c;d < 62;d++){
                    int num = get_cnt({a,b,c,d});
                    ans = (ans + (num + 0LL) * (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 Incorrect 494 ms 7600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 494 ms 7600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 494 ms 7600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 494 ms 7600 KB Output isn't correct
2 Halted 0 ms 0 KB -