Submission #1026444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026444		caterpillow	Cubeword (CEOI19_cubeword)	C++17	84 / 100	1119 ms	11028 KiB

cubeword

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using db = long double;
using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<typename Tuple, size_t... Is>
void print_tuple(const Tuple& t, index_sequence<Is...>) {
    ((cerr << (Is == 0 ? "{" : ", ") << get<Is>(t)), ...);
    cerr << "}";
}

template<typename... Args>
ostream& operator<<(ostream& os, const tuple<Args...>& t) {
    print_tuple(t, index_sequence_for<Args...>{});
    return os;
}

ostream& operator<<(ostream& os, string& s) {
    for (char c : s) os << c; 
    return os;
}

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
    os << "{"; 
    int g = size(o); 
    for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
    os << "}";
    return os;
}

template<typename T, typename V>
ostream& operator<<(ostream& os, const pair<T, V> p) {
    os << "{" << p.f << ", " << p.s << "}";
    return os;
}

template <typename T, typename... V>
void printer(const char *names, T &&head, V &&...tail) {
    int i = 0;
    while (names[i] != '\0' && names[i] != ',') i++;
    constexpr bool is_str = is_same_v<decay_t<T>, const char*>;
    if constexpr (is_str) cerr << head; // ignore directly passed strings
    else cerr.write(names, i) << " = " << head; 
    if constexpr (sizeof...(tail)) cerr << (is_str ? "" : ","), printer(names + i + 1, tail...);
    else cerr << endl;
}

#ifdef LOCAL
#define dbg(...) std::cerr << __LINE__ << ": ", printer(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(x...)
#define cerr if (0) std::cerr
#endif

const ll mod = 998244353;

#define add(a, b) a += b; a -= (a >= mod) * mod;

/*

bucket by word lengths
only care about first and last characters
add both forwards and backwards versions

remove words that are the reverse of each other
dont add duplicates for palindromes

precompute the # of ways to colour a cell if its neighbours are values [a][b][c]


*/

const string alph = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
const ll m = 62;
int mp[1000];

ll triples[m][m][m]; // first index is the "sink", while next three are the sources
ll solve(vt<vt<ll>>& cnt) {
    memset(triples, 0, sizeof(triples));
    ll ans = 0;
    F0R (i, m) {
        F0R (a, m) {
            if (!cnt[a][i]) continue;
            F0R (b, m) {
                if (!cnt[b][i]) continue;
                F0R (c, m) {
                    if (!cnt[c][i]) continue;
                    add(triples[a][b][c], (((cnt[a][i] * cnt[b][i]) % mod) * cnt[c][i]) % mod);
                }
            }
        }
    }
    F0R (a, m) {
        F0R (b, m) {
            F0R (c, m) {
                F0R (d, m) {
                    add(ans, (((((triples[a][b][c] * triples[a][b][d]) % mod) * triples[a][c][d]) % mod) * triples[b][c][d]) % mod);
                }
            }
        }
    }
    return ans;
}

main() {
    cin.tie(0)->sync_with_stdio(0);

    assert(size(alph) == m);
    F0R (i, size(alph)) {
        mp[alph[i]] = i;
    }
    
    int n; cin >> n;
    unordered_set<string> pool;
    vt<vt<vt<ll>>> cnts(11, vt<vt<ll>>(m, vt<ll>(m)));
    F0R (i, n) {
        string st; cin >> st;
        string rst = st;
        reverse(all(rst));
        if (pool.count(rst)) continue;
        cnts[size(st)][mp[st[0]]][mp[st.back()]]++;
        if (st != rst) cnts[size(rst)][mp[rst[0]]][mp[rst.back()]]++;
        pool.insert(st);
    }
    ll ans = 0;
    FOR (i, 3, 11) {
        add(ans, solve(cnts[i]));
    }
    cout << ans << endl;
}

Compilation message (stderr)

cubeword.cpp:125:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  125 | main() {
      | ^~~~
cubeword.cpp: In function 'int main()':
cubeword.cpp:130:19: warning: array subscript has type 'char' [-Wchar-subscripts]
  130 |         mp[alph[i]] = i;
      |                   ^
cubeword.cpp:141:32: warning: array subscript has type 'char' [-Wchar-subscripts]
  141 |         cnts[size(st)][mp[st[0]]][mp[st.back()]]++;
      |                                ^
cubeword.cpp:141:45: warning: array subscript has type 'char' [-Wchar-subscripts]
  141 |         cnts[size(st)][mp[st[0]]][mp[st.back()]]++;
      |                                      ~~~~~~~^~
cubeword.cpp:142:49: warning: array subscript has type 'char' [-Wchar-subscripts]
  142 |         if (st != rst) cnts[size(rst)][mp[rst[0]]][mp[rst.back()]]++;
      |                                                 ^
cubeword.cpp:142:63: warning: array subscript has type 'char' [-Wchar-subscripts]
  142 |         if (st != rst) cnts[size(rst)][mp[rst[0]]][mp[rst.back()]]++;
      |                                                       ~~~~~~~~^~

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