Submission #471810

#	Time	Username	Problem	Language	Result	Execution time	Memory
471810		Ozy	Cubeword (CEOI19_cubeword)	C++17	84 / 100	397 ms	17020 KiB

cubeword

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define abc 35
#define mod 998244353

lli n,a,b,res,MAX;
lli dp[abc+2][abc+2][abc+2], palabras[12][abc+2][abc+2];
string st,rev;
map<string, lli> mapa;

lli convierte(char car) {
    lli x;

    x = car;
    if (x > 96) x -= 96;
    else {
        x -= 65;
        x += 17;
    }
    return x;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    rep (i,1,n) {
        cin >> st;
        rev = st;
        reverse(st.begin(),st.end());
        if (st.size() > MAX) MAX = st.size();

        if (mapa.find(st) != mapa.end() || mapa.find(rev) != mapa.end()) continue;
        mapa[st] = 1;
        mapa[rev] = 1;

        a = convierte(st[0]);
        b = convierte(st[st.size()-1]);

        if (a == b) {
            palabras[st.size()][a][a]++;
            if (st != rev) palabras[st.size()][a][a]++;
        }
        else {
            palabras[st.size()][a][b]++;
            palabras[st.size()][b][a]++;
        }
    }

    rep (tam,3,MAX) {

        rep(i,1,abc) {
            rep(j,1,abc) {
                rep(k,1,abc) {
                    dp[i][j][k] = 0;

                    rep (num,1,abc) {
                        a = palabras[tam][i][num] * palabras[tam][j][num] * palabras[tam][k][num];
                        a %= mod;

                        dp[i][j][k] += a;
                        dp[i][j][k] %= mod;
                    }

                }
            }
        }

        rep(i,1,abc) {
            rep(j,1,abc) {
                rep(k,1,abc) {
                    rep(l,1,abc) {
                        a = dp[i][j][k] * dp[i][j][l];
                        a %= mod;
                        a *= dp[i][k][l];
                        a %= mod;
                        a *= dp[j][k][l];
                        a %= mod;

                        if (a) {
                            res += a;
                            res %= mod;
                        }
                    }
                }
            }
        }

    }

    cout << res;
}

Compilation message (stderr)

cubeword.cpp: In function 'int main()':
cubeword.cpp:40:23: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   40 |         if (st.size() > MAX) MAX = st.size();
      |             ~~~~~~~~~~^~~~~

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