Submission #904762

#	Time	Username	Problem	Language	Result	Execution time	Memory
904762		andrei_iorgulescu	Cubeword (CEOI19_cubeword)	C++14	84 / 100	307 ms	19916 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

const int S = 32;
const int modulo = 998244353;
vector<string>cuv[15];
int cst[S][S];
int cost[S][S][S];

int toint(char c)
{
    if (c >= 'a' and c <= 'p')
        return c - 'a';
    else if (c >= 'A' and c <= 'P')
        return 16 + c - 'A';
}

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

string inv(string s)
{
    reverse(s.begin(),s.end());
    return s;
}

map<string,bool>mp;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        cuv[s.size()].push_back(s);
    }
    int ans = 0;
    for (int l = 3; l <= 10; l++)
    {
        for (int i = 0; i < S; i++)
            for (int j = 0; j < S; j++)
                cst[i][j] = 0;
        for (int i = 0; i < S; i++)
            for (int j = 0; j < S; j++)
                for (int k = 0; k < S; k++)
                    cost[i][j][k] = 0;
        for (auto it : cuv[l])
        {
            if (mp[inv(it)] == true)
                continue;
            mp[it] = true;
            cst[toint(it[0])][toint(it[l - 1])]++;
            if (it[0] != it[l - 1])
                cst[toint(it[l - 1])][toint(it[0])]++;
            else if (palint(it) == false)
                cst[toint(it[0])][toint(it[l - 1])]++;
        }
        for (int i = 0; i < S; i++)
        {
            for (int j = 0; j < S; j++)
            {
                for (int k = 0; k < S; k++)
                {
                    for (int q = 0; q < S; q++)
                        cost[i][j][k] = (0ll + cost[i][j][k] + 1ll * cst[i][q] * cst[j][q] * cst[k][q]) % modulo;
                }
            }
        }
        for (int A = 0; A < S; A++)
        {
            for (int B = 0; B < S; B++)
            {
                for (int C = 0; C < S; C++)
                {
                    for (int D = 0; D < S; D++)
                    {
                        int adg = 1ll * cost[A][B][C] * cost[A][B][D] % modulo * cost[A][C][D] % modulo * cost[B][C][D] % modulo;
                        ans = (ans + adg) % modulo;
                    }
                }
            }
        }
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

cubeword.cpp: In function 'bool palint(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 = 1; i < s.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~
cubeword.cpp: In function 'int toint(char)':
cubeword.cpp:17:1: warning: control reaches end of non-void function [-Wreturn-type]
   17 | }
      | ^

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