oj.uz

Submission #742524

# Submission time Handle Problem Language Result Execution time Memory
742524 2023-05-16T11:26:50 Z Stickfish Cubeword (CEOI19_cubeword) C++17
0 / 100
 159 ms 9360 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cassert>
using namespace std;
using ll = long long;

const int MAXV = 33;
const ll MOD = 998244353;
ll f[MAXV][MAXV];
ll dp[MAXV][MAXV][MAXV];

int to_int(char c) {
    if ('a' <= c && c <= 'z')
        return c - 'a';
    assert(0);
    if ('A' <= c && c <= 'Z')
        return c - 'A' + 26;
    return c - '0' + 52;
}

void get_edg(vector<string> v) {
    for (int p = 0; p < MAXV; ++p) {
        for (int q = 0; q < MAXV; ++q) {
            f[p][q] = 0;
        }
    }
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    for (size_t i = 0; i < v.size(); ++i) {
        int p = to_int(v[i][0]);
        int q = to_int(v[i].back());
        ++f[p][q];
    }
}

void get_dp() {
    for (int a = 0; a < MAXV; ++a) for (int b = 0; b < MAXV; ++b) for (int c = 0; c < MAXV; ++c) {
        if (b > a) {
            dp[a][b][c] = dp[b][a][c];
            continue;
        }
        if (c > b) {
            dp[a][b][c] = dp[a][c][b];
            continue;
        }
        dp[a][b][c] = 0;
        for (int x = 0; x < MAXV; ++x) {
            dp[a][b][c] += 1ll * f[a][x] * f[b][x] % MOD * f[c][x];
            dp[a][b][c] %= MOD;
        }
    }
}

ll get_ans() {
    ll ans = 0;
    get_dp();
    for (int a = 0; a < MAXV; ++a) for (int b = 0; b < MAXV; ++b) for (int c = 0; c < MAXV; ++c) for (int d = 0; d < MAXV; ++d) {
        ans += dp[a][b][c] * dp[a][b][d] % MOD * dp[a][c][d] % MOD * dp[b][c][d] % MOD;
        ans %= MOD;
    }
    return ans;
}

signed main() {
    int n;
    cin >> n;
    vector<vector<string>> vals(11);
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        vals[s.size()].push_back(s);
        reverse(s.begin(), s.end());
        vals[s.size()].push_back(s);
    }
    ll ans = 0;
    for (int t = 0; t < 11; ++t) {
        if (vals[t].empty())
            continue;
        get_edg(vals[t]);
        ans += get_ans();
    }
    ans %= MOD;
    cout << ans << '\n';
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 9360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 9360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 9360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 159 ms 9360 KB Output isn't correct
2 Halted 0 ms 0 KB -