Submission #1026448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026448		caterpillow	Cubeword (CEOI19_cubeword)	C++17	100 / 100	1086 ms	10956 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;

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) {
            F0R (b, m) {
                F0R (c, m) {
                    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:71:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   71 | main() {
      | ^~~~
cubeword.cpp: In function 'int main()':
cubeword.cpp:76:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   76 |         mp[alph[i]] = i;
      |                   ^
cubeword.cpp:87:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   87 |         cnts[size(st)][mp[st[0]]][mp[st.back()]]++;
      |                                ^
cubeword.cpp:87:45: warning: array subscript has type 'char' [-Wchar-subscripts]
   87 |         cnts[size(st)][mp[st[0]]][mp[st.back()]]++;
      |                                      ~~~~~~~^~
cubeword.cpp:88:49: warning: array subscript has type 'char' [-Wchar-subscripts]
   88 |         if (st != rst) cnts[size(rst)][mp[rst[0]]][mp[rst.back()]]++;
      |                                                 ^
cubeword.cpp:88:63: warning: array subscript has type 'char' [-Wchar-subscripts]
   88 |         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: 16 / 16