Submission #1095920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095920		yoav_s	Cubeword (CEOI19_cubeword)	C++17	84 / 100	677 ms	16624 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<ll> v;
typedef vector<v> vv;
typedef vector<vv> vvv;
typedef pair<ll, ll> p;
typedef vector<p> vp;
typedef vector<vp> vvp;
typedef vector<vvp> vvvp;
typedef pair<ll, p> tri;
typedef vector<tri> vtri;
typedef vector<vtri> vvtri;
typedef vector<vvtri> vvvtri;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define all(v) (v).begin(),(v).end()

const ll INF = 1e18;
const ll mod = 998244353;

bool isPalindrome(string &str)
{
    for (ll i = 0; i < str.size() / 2; i++) if (str[i] != str[str.size() - i - 1]) return false;
    return true;
}

ll combinations(ll a, ll b, ll c, ll d)
{
    if (a == d) return 1;
    if (a == c || b == d) return 4;
    if (a == b && c == d) return 6;
    if (a == b || c == d) return 12;
    return 24;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll n;
    cin >> n;
    vector<string> words(n);
    for (ll i = 0; i < n; i++) cin >> words[i];
    vector<char> characters;
    for (ll i=  'a'; i <= 'z'; i++) characters.pb(i);
    for (ll i = 'A'; i <= 'Z'; i++) characters.pb(i);
    //for (ll i = '0'; i <= '9'; i++) characters.pb(i);
    map<char, char> charShrink;
    for (ll i = 0; i < characters.size(); i++) charShrink[characters[i]] = i;
    for (ll i = 0; i < n; i++) for (ll j = 0; j < words[i].size(); j++) words[i][j] = charShrink[words[i][j]];
    vector<vector<string>> byLength(11);
    set<string> exists;
    for (ll i = 0; i < n; i++)
    {
        reverse(all(words[i]));
        if (exists.count(words[i]) > 0) continue;
        reverse(all(words[i]));
        byLength[words[i].size()].pb(words[i]);
        exists.insert(words[i]);
    }
    ll c = characters.size();
    ll res = 0;
    for (ll i = 3; i <= 10; i++)
    {
        vv amt(c, v(c, 0));
        for (ll j = 0; j < byLength[i].size(); j++)
        {
            amt[byLength[i][j][0]][byLength[i][j].back()]++;
            if (!isPalindrome(byLength[i][j])) amt[byLength[i][j].back()][byLength[i][j][0]]++;
        }
        vvv possibilities(c, vv(c, v(c)));
        for (ll i = 0; i < c; i++)
        {
            for (ll j = 0; j < c; j++)
            {
                for (ll k = 0; k < c; k++)
                {
                    for (ll l = 0; l < c; l++)
                    {
                        possibilities[i][j][k] += ((amt[i][l] * amt[j][l]) % mod) * amt[k][l];
                        possibilities[i][j][k] %= mod;
                    }
                }
            }
        }
        for (ll corner1 = 0; corner1 < c; corner1++)
        {
            for (ll corner2 = 0; corner2 < c; corner2++)
            {
                for (ll corner3 = 0; corner3 < c; corner3++)
                {
                    for (ll corner4 = 0; corner4 < c; corner4++)
                    {
                        ll cur = possibilities[corner1][corner2][corner3];
                        cur = (cur * possibilities[corner1][corner2][corner4]) % mod;
                        cur = (cur * possibilities[corner1][corner3][corner4]) % mod;
                        cur = (cur * possibilities[corner2][corner3][corner4]) % mod;
                        res = (res + cur) % mod;
                    }
                }
            }
        }
    }
    cout << res << "\n";
    return 0;
}

Compilation message (stderr)

cubeword.cpp: In function 'bool isPalindrome(std::string&)':
cubeword.cpp:32:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (ll i = 0; i < str.size() / 2; i++) if (str[i] != str[str.size() - i - 1]) return false;
      |                    ~~^~~~~~~~~~~~~~~~
cubeword.cpp: In function 'int main()':
cubeword.cpp:57:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (ll i = 0; i < characters.size(); i++) charShrink[characters[i]] = i;
      |                    ~~^~~~~~~~~~~~~~~~~~~
cubeword.cpp:58:49: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for (ll i = 0; i < n; i++) for (ll j = 0; j < words[i].size(); j++) words[i][j] = charShrink[words[i][j]];
      |                                               ~~^~~~~~~~~~~~~~~~~
cubeword.cpp:74:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for (ll j = 0; j < byLength[i].size(); j++)
      |                        ~~^~~~~~~~~~~~~~~~~~~~

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