oj.uz

Submission #546572

# Submission time Handle Problem Language Result Execution time Memory
546572 2022-04-07T20:36:23 Z LucaDantas Cubeword (CEOI19_cubeword) C++17
21 / 100
 1100 ms 15432 KB 
#pragma GCC optimize("Ofast") 
#pragma GCC optimize("unroll-loops") 
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") 
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 16, mod = 998244353; // subtasks 1-2

int ans;

int edge[11][maxn][maxn];

int value_triad[11][maxn][maxn][maxn];

int id(char c) { return c-'a'; } // subtaks 1-2

set<string> mark;

void add(int& a, int b) { a += b; if(a >= mod) a -= mod; }

int main() {
    int n; cin >> n;
    string s;
    for(int i = 0; i < n; i++) {
        cin >> s;
        for(int rep = 0; rep < 2; rep++, reverse(s.begin(), s.end())) if(!mark.count(s)) {
            edge[s.size()][id(s[0])][id(s.back())]++;
            mark.insert(s);
        }
    }

    // vector<array<int,3>> triad;
    // for(int a = 0; a < maxn; a++) for(int b = 0; b < maxn; b++) for(int c = 0; c < maxn; c++)
    //             triad.push_back({a, b, c});


    for(int sz = 3; sz <= 10; sz++) {
        // for(auto [a, b, c] : triad)
        for(int a = 0; a < maxn; a++) for(int b = 0; b < maxn; b++) for(int c = 0; c < maxn; c++)
            for(int x = 0; x < maxn; x++)
                add(value_triad[sz][a][b][c], 1ll * edge[sz][x][a] * edge[sz][x][b] * edge[sz][x][c] % mod);

        for(int a1 = 0; a1 < maxn; a1++) for(int b1 = 0; b1 < maxn; b1++) for(int c1 = 0; c1 < maxn; c1++) if(value_triad[sz][a1][b1][c1])
        for(int a2 = 0; a2 < maxn; a2++) for(int b2 = 0; b2 < maxn; b2++) for(int c2 = 0; c2 < maxn; c2++) {
        // for(auto [a1, b1, c1] : triad) for(auto [a2, b2, c2] : triad) {
            long long aq = 1ll * value_triad[sz][a1][b1][c1] * value_triad[sz][a2][b2][c2] % mod;
            if(!aq) continue;
            aq *= 1ll * edge[sz][a1][b2] * edge[sz][a1][c2] % mod; aq %= mod;
            aq *= 1ll * edge[sz][b1][a2] * edge[sz][b1][c2] % mod; aq %= mod;
            aq *= 1ll * edge[sz][c1][a2] * edge[sz][c1][b2] % mod; aq %= mod;
            
            add(ans, aq);
        }
    }

    printf("%d\n", ans);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 14800 KB Output is correct
2 Correct 207 ms 14972 KB Output is correct
3 Correct 199 ms 14796 KB Output is correct
4 Correct 217 ms 14796 KB Output is correct
5 Correct 220 ms 14920 KB Output is correct
6 Correct 197 ms 14812 KB Output is correct
7 Correct 197 ms 14920 KB Output is correct
8 Correct 199 ms 14920 KB Output is correct
9 Correct 194 ms 14880 KB Output is correct
10 Correct 198 ms 14984 KB Output is correct
11 Correct 197 ms 14820 KB Output is correct
12 Correct 198 ms 14884 KB Output is correct
13 Correct 202 ms 14908 KB Output is correct
14 Correct 195 ms 14796 KB Output is correct
15 Correct 205 ms 14984 KB Output is correct
16 Correct 197 ms 14900 KB Output is correct
17 Correct 202 ms 14872 KB Output is correct
18 Correct 197 ms 15004 KB Output is correct
19 Correct 197 ms 14888 KB Output is correct
20 Correct 196 ms 14872 KB Output is correct
21 Correct 199 ms 14808 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 14800 KB Output is correct
2 Correct 207 ms 14972 KB Output is correct
3 Correct 199 ms 14796 KB Output is correct
4 Correct 217 ms 14796 KB Output is correct
5 Correct 220 ms 14920 KB Output is correct
6 Correct 197 ms 14812 KB Output is correct
7 Correct 197 ms 14920 KB Output is correct
8 Correct 199 ms 14920 KB Output is correct
9 Correct 194 ms 14880 KB Output is correct
10 Correct 198 ms 14984 KB Output is correct
11 Correct 197 ms 14820 KB Output is correct
12 Correct 198 ms 14884 KB Output is correct
13 Correct 202 ms 14908 KB Output is correct
14 Correct 195 ms 14796 KB Output is correct
15 Correct 205 ms 14984 KB Output is correct
16 Correct 197 ms 14900 KB Output is correct
17 Correct 202 ms 14872 KB Output is correct
18 Correct 197 ms 15004 KB Output is correct
19 Correct 197 ms 14888 KB Output is correct
20 Correct 196 ms 14872 KB Output is correct
21 Correct 199 ms 14808 KB Output is correct
22 Execution timed out 1186 ms 15432 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 14800 KB Output is correct
2 Correct 207 ms 14972 KB Output is correct
3 Correct 199 ms 14796 KB Output is correct
4 Correct 217 ms 14796 KB Output is correct
5 Correct 220 ms 14920 KB Output is correct
6 Correct 197 ms 14812 KB Output is correct
7 Correct 197 ms 14920 KB Output is correct
8 Correct 199 ms 14920 KB Output is correct
9 Correct 194 ms 14880 KB Output is correct
10 Correct 198 ms 14984 KB Output is correct
11 Correct 197 ms 14820 KB Output is correct
12 Correct 198 ms 14884 KB Output is correct
13 Correct 202 ms 14908 KB Output is correct
14 Correct 195 ms 14796 KB Output is correct
15 Correct 205 ms 14984 KB Output is correct
16 Correct 197 ms 14900 KB Output is correct
17 Correct 202 ms 14872 KB Output is correct
18 Correct 197 ms 15004 KB Output is correct
19 Correct 197 ms 14888 KB Output is correct
20 Correct 196 ms 14872 KB Output is correct
21 Correct 199 ms 14808 KB Output is correct
22 Execution timed out 1186 ms 15432 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 14800 KB Output is correct
2 Correct 207 ms 14972 KB Output is correct
3 Correct 199 ms 14796 KB Output is correct
4 Correct 217 ms 14796 KB Output is correct
5 Correct 220 ms 14920 KB Output is correct
6 Correct 197 ms 14812 KB Output is correct
7 Correct 197 ms 14920 KB Output is correct
8 Correct 199 ms 14920 KB Output is correct
9 Correct 194 ms 14880 KB Output is correct
10 Correct 198 ms 14984 KB Output is correct
11 Correct 197 ms 14820 KB Output is correct
12 Correct 198 ms 14884 KB Output is correct
13 Correct 202 ms 14908 KB Output is correct
14 Correct 195 ms 14796 KB Output is correct
15 Correct 205 ms 14984 KB Output is correct
16 Correct 197 ms 14900 KB Output is correct
17 Correct 202 ms 14872 KB Output is correct
18 Correct 197 ms 15004 KB Output is correct
19 Correct 197 ms 14888 KB Output is correct
20 Correct 196 ms 14872 KB Output is correct
21 Correct 199 ms 14808 KB Output is correct
22 Execution timed out 1186 ms 15432 KB Time limit exceeded
23 Halted 0 ms 0 KB -