Submission #346332

#	Time	Username	Problem	Language	Result	Execution time	Memory
346332		doowey	Cubeword (CEOI19_cubeword)	C++14	100 / 100	586 ms	35308 KiB

cubeword

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int AL = 62;
const int LEN = 11;
const int MOD = 998244353;

int cnt[AL][AL][LEN];

bool is_palin(string t){
    for(int i = 0 ; i < t.size() ; i ++ ){
        if(t[i] != t[(int)t.size() - 1 - i]){
            return false;
        }
    }
    return true;
}

int D[AL][AL][AL];

int mlt(int a, int b){
    return (a * 1ll * b) % MOD;
}

void add(int &a, int b){
    a = (a + b) % MOD;
}

int getid(char f){
    if(f >= 'a' && f <= 'z') return f - 'a';
    else if(f >= 'A' && f <= 'Z') return 26 + (f - 'A');
    return 52 + f - '0';
}

map<string, bool> dict;
int perm[AL][AL][AL][AL];

int calc(vector<int> q){
    sort(q.begin(), q.end());
    int cnt = 0;
    do{
        cnt ++ ;
    }while(next_permutation(q.begin(), q.end()));
    return cnt;
}

int main(){
    fastIO;
    int n;
    cin >> n;
    string t;
    int m;
    int fa, fb;
    for(int i = 0 ; i < n; i ++ ){
        cin >> t;
        m = t.size();
        if(dict.count(t)) continue;
        fa=getid(t[0]);
        fb=getid(t.back());
        cnt[fa][fb][m]++;
        if(!is_palin(t)) cnt[fb][fa][m]++;
        dict[t]=true;
        reverse(t.begin(), t.end());
        dict[t]=true;
    }
    for(int i = 0 ; i < AL; i ++ ){
        for(int j = i ; j < AL; j ++ ){
            for(int p = j ; p < AL; p ++ ){
                for(int t = p ; t < AL; t ++ ){
                    perm[i][j][p][t]=calc({i,j,p,t});
                }
            }
        }
    }
    int sol = 0;
    for(int len = 3; len <= 10; len ++ ){
        for(int i = 0 ; i < AL; i ++ ){
            for(int j = i ; j < AL; j ++ ){
                for(int k = j ; k < AL; k ++ ){
                    D[i][j][k]=0;
                    for(int q = 0; q < AL; q ++ ){
                        add(D[i][j][k],mlt(mlt(cnt[i][q][len],cnt[j][q][len]),cnt[k][q][len]));
                    }
                }
            }
        }
        for(int a = 0; a < AL; a ++ ){
            for(int d = a ; d < AL; d ++ ){
                for(int e = d; e < AL; e ++ ){
                    if(D[a][d][e] == 0) continue;
                    for(int h = e; h < AL; h ++ ){
                        add(sol,mlt(perm[a][d][e][h],mlt(mlt(D[a][d][e],D[a][d][h]),mlt(D[d][e][h],D[a][e][h]))));
                    }
                }
            }
        }
    }
    cout << sol << "\n";
    return 0;
}

Compilation message (stderr)

cubeword.cpp: In function 'bool is_palin(std::string)':
cubeword.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for(int i = 0 ; i < t.size() ; i ++ ){
      |                     ~~^~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 29 / 29
• Subtask 3: 34 / 34
• Subtask 4: 16 / 16