oj.uz

Submission #924820

# Submission time Handle Problem Language Result Execution time Memory
924820 2024-02-09T19:35:55 Z Camillus Cubeword (CEOI19_cubeword) C++17
100 / 100
 1084 ms 9588 KB 
/// @author Camillus
#include "bits/stdc++.h"
#pragma GCC optimize("O3")

using ll = long long;
using namespace std;

static constexpr ll mod = 998'244'353;

static constexpr int SIGMA = 26 + 26 + 10;
ll cnt2[SIGMA][SIGMA];
ll cnt3[SIGMA][SIGMA][SIGMA];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    map<int, vector<string>> b;

    map<int, int> ord;

    int sigma = 0;

    for (char x = 'a'; x <= 'z'; x++) {
        ord[x] = sigma++;
    }
    
    for (char x = 'A'; x <= 'Z'; x++) {
        ord[x] = sigma++;
    }

    for (char x = '0'; x <= '9'; x++) {
        ord[x] = sigma++;
    }

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;

        b[s.size()].push_back(s);
    }

    ll ans = 0;

    for (const auto &[x, y] : b) {
        memset(cnt2, 0, sizeof(cnt2));
        memset(cnt3, 0, sizeof(cnt3));

        set<string> z;
        for (const string &s : y) {
            string t = s;
            reverse(t.begin(), t.end());
            z.insert(t);
            z.insert(s);
        }

        for (const string &s : z) {
            int a = ord[s.front()];
            int b = ord[s.back()];
            cnt2[a][b] += 1;
        }

        for (int a = 0; a < SIGMA; a++) {
            for (int b = 0; b < SIGMA; b++) {
                for (int c = 0; c < SIGMA; c++) {
                    for (int d = 0; d < SIGMA; d++) {
                        cnt3[a][b][c] += cnt2[a][d] * cnt2[b][d] % mod * cnt2[c][d] % mod;
                        if (cnt3[a][b][c] >= mod) {
                            cnt3[a][b][c] -= mod;
                        }
                    }
                }
            }
        }

        for (int a = 0; a < SIGMA; a++) {
            for (int b = 0; b < SIGMA; b++) {
                for (int c = 0; c < SIGMA; c++) {
                    for (int d = 0; d < SIGMA; d++) {
                        ans += cnt3[a][b][d] * cnt3[a][b][c] % mod * cnt3[c][b][d] % mod * cnt3[a][c][d] % mod;
                        if (ans >= mod) {
                            ans -= mod;
                        }
                    }
                }
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1033 ms 8528 KB Output is correct
2 Correct 1055 ms 8488 KB Output is correct
3 Correct 1057 ms 8744 KB Output is correct
4 Correct 1034 ms 8520 KB Output is correct
5 Correct 1024 ms 8328 KB Output is correct
6 Correct 1084 ms 8736 KB Output is correct
7 Correct 1024 ms 8264 KB Output is correct
8 Correct 1031 ms 8544 KB Output is correct
9 Correct 1062 ms 8528 KB Output is correct
10 Correct 1028 ms 8380 KB Output is correct
11 Correct 1049 ms 9148 KB Output is correct
12 Correct 1051 ms 9484 KB Output is correct
13 Correct 1034 ms 9560 KB Output is correct
14 Correct 1050 ms 9372 KB Output is correct
15 Correct 1037 ms 9388 KB Output is correct
16 Correct 1024 ms 9552 KB Output is correct
17 Correct 1032 ms 9260 KB Output is correct
18 Correct 1024 ms 9588 KB Output is correct
19 Correct 1069 ms 9428 KB Output is correct
20 Correct 1028 ms 9584 KB Output is correct
21 Correct 1038 ms 9432 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1033 ms 8528 KB Output is correct
2 Correct 1055 ms 8488 KB Output is correct
3 Correct 1057 ms 8744 KB Output is correct
4 Correct 1034 ms 8520 KB Output is correct
5 Correct 1024 ms 8328 KB Output is correct
6 Correct 1084 ms 8736 KB Output is correct
7 Correct 1024 ms 8264 KB Output is correct
8 Correct 1031 ms 8544 KB Output is correct
9 Correct 1062 ms 8528 KB Output is correct
10 Correct 1028 ms 8380 KB Output is correct
11 Correct 1049 ms 9148 KB Output is correct
12 Correct 1051 ms 9484 KB Output is correct
13 Correct 1034 ms 9560 KB Output is correct
14 Correct 1050 ms 9372 KB Output is correct
15 Correct 1037 ms 9388 KB Output is correct
16 Correct 1024 ms 9552 KB Output is correct
17 Correct 1032 ms 9260 KB Output is correct
18 Correct 1024 ms 9588 KB Output is correct
19 Correct 1069 ms 9428 KB Output is correct
20 Correct 1028 ms 9584 KB Output is correct
21 Correct 1038 ms 9432 KB Output is correct
22 Correct 1043 ms 8492 KB Output is correct
23 Correct 1025 ms 8560 KB Output is correct
24 Correct 1033 ms 8656 KB Output is correct
25 Correct 1058 ms 8612 KB Output is correct
26 Correct 1066 ms 8616 KB Output is correct
27 Correct 1039 ms 8440 KB Output is correct
28 Correct 1072 ms 8576 KB Output is correct
29 Correct 1027 ms 8596 KB Output is correct
30 Correct 1026 ms 8704 KB Output is correct
31 Correct 1027 ms 8604 KB Output is correct
32 Correct 1024 ms 8304 KB Output is correct
33 Correct 1049 ms 8448 KB Output is correct
34 Correct 1026 ms 8588 KB Output is correct
35 Correct 1045 ms 8472 KB Output is correct
36 Correct 1069 ms 8664 KB Output is correct
37 Correct 1029 ms 8396 KB Output is correct
38 Correct 1026 ms 8392 KB Output is correct
39 Correct 1028 ms 8628 KB Output is correct
40 Correct 1029 ms 8568 KB Output is correct
41 Correct 1030 ms 8572 KB Output is correct
42 Correct 1056 ms 8640 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1033 ms 8528 KB Output is correct
2 Correct 1055 ms 8488 KB Output is correct
3 Correct 1057 ms 8744 KB Output is correct
4 Correct 1034 ms 8520 KB Output is correct
5 Correct 1024 ms 8328 KB Output is correct
6 Correct 1084 ms 8736 KB Output is correct
7 Correct 1024 ms 8264 KB Output is correct
8 Correct 1031 ms 8544 KB Output is correct
9 Correct 1062 ms 8528 KB Output is correct
10 Correct 1028 ms 8380 KB Output is correct
11 Correct 1049 ms 9148 KB Output is correct
12 Correct 1051 ms 9484 KB Output is correct
13 Correct 1034 ms 9560 KB Output is correct
14 Correct 1050 ms 9372 KB Output is correct
15 Correct 1037 ms 9388 KB Output is correct
16 Correct 1024 ms 9552 KB Output is correct
17 Correct 1032 ms 9260 KB Output is correct
18 Correct 1024 ms 9588 KB Output is correct
19 Correct 1069 ms 9428 KB Output is correct
20 Correct 1028 ms 9584 KB Output is correct
21 Correct 1038 ms 9432 KB Output is correct
22 Correct 1043 ms 8492 KB Output is correct
23 Correct 1025 ms 8560 KB Output is correct
24 Correct 1033 ms 8656 KB Output is correct
25 Correct 1058 ms 8612 KB Output is correct
26 Correct 1066 ms 8616 KB Output is correct
27 Correct 1039 ms 8440 KB Output is correct
28 Correct 1072 ms 8576 KB Output is correct
29 Correct 1027 ms 8596 KB Output is correct
30 Correct 1026 ms 8704 KB Output is correct
31 Correct 1027 ms 8604 KB Output is correct
32 Correct 1024 ms 8304 KB Output is correct
33 Correct 1049 ms 8448 KB Output is correct
34 Correct 1026 ms 8588 KB Output is correct
35 Correct 1045 ms 8472 KB Output is correct
36 Correct 1069 ms 8664 KB Output is correct
37 Correct 1029 ms 8396 KB Output is correct
38 Correct 1026 ms 8392 KB Output is correct
39 Correct 1028 ms 8628 KB Output is correct
40 Correct 1029 ms 8568 KB Output is correct
41 Correct 1030 ms 8572 KB Output is correct
42 Correct 1056 ms 8640 KB Output is correct
43 Correct 1056 ms 8268 KB Output is correct
44 Correct 1046 ms 8368 KB Output is correct
45 Correct 1032 ms 8368 KB Output is correct
46 Correct 1033 ms 8100 KB Output is correct
47 Correct 1028 ms 8120 KB Output is correct
48 Correct 1029 ms 8292 KB Output is correct
49 Correct 1076 ms 8164 KB Output is correct
50 Correct 1026 ms 8268 KB Output is correct
51 Correct 1052 ms 8472 KB Output is correct
52 Correct 1025 ms 8584 KB Output is correct
53 Correct 1037 ms 8384 KB Output is correct
54 Correct 1032 ms 8572 KB Output is correct
55 Correct 1064 ms 8256 KB Output is correct
56 Correct 1047 ms 8444 KB Output is correct
57 Correct 1032 ms 8232 KB Output is correct
58 Correct 1070 ms 8396 KB Output is correct
59 Correct 1027 ms 8272 KB Output is correct
60 Correct 1033 ms 8296 KB Output is correct
61 Correct 1034 ms 8532 KB Output is correct
62 Correct 1052 ms 8268 KB Output is correct
63 Correct 1032 ms 8164 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1033 ms 8528 KB Output is correct
2 Correct 1055 ms 8488 KB Output is correct
3 Correct 1057 ms 8744 KB Output is correct
4 Correct 1034 ms 8520 KB Output is correct
5 Correct 1024 ms 8328 KB Output is correct
6 Correct 1084 ms 8736 KB Output is correct
7 Correct 1024 ms 8264 KB Output is correct
8 Correct 1031 ms 8544 KB Output is correct
9 Correct 1062 ms 8528 KB Output is correct
10 Correct 1028 ms 8380 KB Output is correct
11 Correct 1049 ms 9148 KB Output is correct
12 Correct 1051 ms 9484 KB Output is correct
13 Correct 1034 ms 9560 KB Output is correct
14 Correct 1050 ms 9372 KB Output is correct
15 Correct 1037 ms 9388 KB Output is correct
16 Correct 1024 ms 9552 KB Output is correct
17 Correct 1032 ms 9260 KB Output is correct
18 Correct 1024 ms 9588 KB Output is correct
19 Correct 1069 ms 9428 KB Output is correct
20 Correct 1028 ms 9584 KB Output is correct
21 Correct 1038 ms 9432 KB Output is correct
22 Correct 1043 ms 8492 KB Output is correct
23 Correct 1025 ms 8560 KB Output is correct
24 Correct 1033 ms 8656 KB Output is correct
25 Correct 1058 ms 8612 KB Output is correct
26 Correct 1066 ms 8616 KB Output is correct
27 Correct 1039 ms 8440 KB Output is correct
28 Correct 1072 ms 8576 KB Output is correct
29 Correct 1027 ms 8596 KB Output is correct
30 Correct 1026 ms 8704 KB Output is correct
31 Correct 1027 ms 8604 KB Output is correct
32 Correct 1024 ms 8304 KB Output is correct
33 Correct 1049 ms 8448 KB Output is correct
34 Correct 1026 ms 8588 KB Output is correct
35 Correct 1045 ms 8472 KB Output is correct
36 Correct 1069 ms 8664 KB Output is correct
37 Correct 1029 ms 8396 KB Output is correct
38 Correct 1026 ms 8392 KB Output is correct
39 Correct 1028 ms 8628 KB Output is correct
40 Correct 1029 ms 8568 KB Output is correct
41 Correct 1030 ms 8572 KB Output is correct
42 Correct 1056 ms 8640 KB Output is correct
43 Correct 1056 ms 8268 KB Output is correct
44 Correct 1046 ms 8368 KB Output is correct
45 Correct 1032 ms 8368 KB Output is correct
46 Correct 1033 ms 8100 KB Output is correct
47 Correct 1028 ms 8120 KB Output is correct
48 Correct 1029 ms 8292 KB Output is correct
49 Correct 1076 ms 8164 KB Output is correct
50 Correct 1026 ms 8268 KB Output is correct
51 Correct 1052 ms 8472 KB Output is correct
52 Correct 1025 ms 8584 KB Output is correct
53 Correct 1037 ms 8384 KB Output is correct
54 Correct 1032 ms 8572 KB Output is correct
55 Correct 1064 ms 8256 KB Output is correct
56 Correct 1047 ms 8444 KB Output is correct
57 Correct 1032 ms 8232 KB Output is correct
58 Correct 1070 ms 8396 KB Output is correct
59 Correct 1027 ms 8272 KB Output is correct
60 Correct 1033 ms 8296 KB Output is correct
61 Correct 1034 ms 8532 KB Output is correct
62 Correct 1052 ms 8268 KB Output is correct
63 Correct 1032 ms 8164 KB Output is correct
64 Correct 1031 ms 8356 KB Output is correct
65 Correct 1051 ms 8336 KB Output is correct
66 Correct 1048 ms 8172 KB Output is correct
67 Correct 1033 ms 8208 KB Output is correct
68 Correct 1038 ms 8376 KB Output is correct
69 Correct 1049 ms 8444 KB Output is correct
70 Correct 1044 ms 8436 KB Output is correct
71 Correct 1042 ms 8364 KB Output is correct
72 Correct 1049 ms 8240 KB Output is correct
73 Correct 1047 ms 8236 KB Output is correct
74 Correct 1033 ms 8468 KB Output is correct
75 Correct 1033 ms 8320 KB Output is correct
76 Correct 1027 ms 8220 KB Output is correct
77 Correct 1029 ms 8224 KB Output is correct
78 Correct 1064 ms 8356 KB Output is correct
79 Correct 1022 ms 8244 KB Output is correct
80 Correct 1038 ms 8224 KB Output is correct
81 Correct 1043 ms 8340 KB Output is correct
82 Correct 1035 ms 8272 KB Output is correct
83 Correct 1025 ms 8216 KB Output is correct
84 Correct 1026 ms 8480 KB Output is correct