답안 #953620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
953620	2024-03-26T10:44:03 Z	LucaIlie	Cubeword (CEOI19_cubeword)	C++17	100 / 100	1070 ms	8368 KB

cubeword

#include <bits/stdc++.h>

using namespace std;

const int MAX_ID = 62;
const int MIN_LEN = 3;
const int MAX_LEN = 10;
const int MOD = 998244353;
vector<string> s[MAX_LEN + 1];
unordered_map<char, int> id;
int m;
int coef[MAX_ID][MAX_ID], prod[MAX_ID][MAX_ID][MAX_ID];

int solve() {
    int ans = 0;

    for ( int a = 0; a < m; a++ ) {
        for ( int b = 0; b < m; b++ ) {
            for ( int c = 0; c < m; c++ ) {
                prod[a][b][c] = 0;
                for ( int i = 0; i < m; i++ )
                    prod[a][b][c] = (prod[a][b][c] + (long long)coef[a][i] * coef[b][i] % MOD * coef[c][i]) % MOD;
            }
        }
    }


    for ( int a = 0; a < m; a++ ) {
        for ( int b = 0; b < m; b++ ) {
            for ( int c = 0; c < m; c++ ) {
                for ( int d = 0; d < m; d++ )
                    ans = (ans + prod[a][b][c] * (long long)prod[a][b][d] % MOD * prod[a][c][d] % MOD * prod[b][c][d]) % MOD;
            }
        }
    }

    return ans;
}

int main() {
    cin.tie( NULL );
    ios_base::sync_with_stdio( false );

    int n;

    cin >> n;
    for ( int i = 0; i < n; i++ ) {
        string t;
        cin >> t;
        s[t.size()].push_back( t );
        string w = t;
        reverse( w.begin(), w.end() );
        if ( w != t )
            s[t.size()].push_back( w );
        for ( int i = 0; i < t.size(); i++ )
            id[t[i]] = 1;
    }

    m = 0;
    for ( auto p: id )
        id[p.first] = m++;

    int ans = 0;
    for ( int l = MIN_LEN; l <= MAX_LEN; l++ ) {
        if ( s[l].size() == 0 )
            continue;

        for ( int i = 0; i < m; i++ ) {
            for ( int j = 0; j < m; j++ )
                coef[i][j] = 0;
        }
        sort( s[l].begin(), s[l].end() );
        for ( int i = 0; i < s[l].size(); i++ ) {
            if ( i == 0 || s[l][i] != s[l][i - 1])
                coef[id[s[l][i][0]]][id[s[l][i].back()]]++;
        }

        ans = (ans + solve()) % MOD;
    }

    cout << ans;

    return 0;
}

Compilation message

cubeword.cpp: In function 'int main()':
cubeword.cpp:55:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for ( int i = 0; i < t.size(); i++ )
      |                          ~~^~~~~~~~~~
cubeword.cpp:73:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |         for ( int i = 0; i < s[l].size(); i++ ) {
      |                          ~~^~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	7408 KB	Output is correct
2	Correct	48 ms	8368 KB	Output is correct
3	Correct	48 ms	7208 KB	Output is correct
4	Correct	47 ms	7504 KB	Output is correct
5	Correct	48 ms	7524 KB	Output is correct
6	Correct	47 ms	7456 KB	Output is correct
7	Correct	49 ms	7432 KB	Output is correct
8	Correct	50 ms	7356 KB	Output is correct
9	Correct	48 ms	7392 KB	Output is correct
10	Correct	46 ms	7468 KB	Output is correct
11	Correct	51 ms	7568 KB	Output is correct
12	Correct	47 ms	7344 KB	Output is correct
13	Correct	47 ms	7348 KB	Output is correct
14	Correct	59 ms	7136 KB	Output is correct
15	Correct	53 ms	7432 KB	Output is correct
16	Correct	52 ms	7308 KB	Output is correct
17	Correct	47 ms	7416 KB	Output is correct
18	Correct	47 ms	7324 KB	Output is correct
19	Correct	46 ms	7412 KB	Output is correct
20	Correct	50 ms	7340 KB	Output is correct
21	Correct	47 ms	7264 KB	Output is correct

Subtask #2
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	7408 KB	Output is correct
2	Correct	48 ms	8368 KB	Output is correct
3	Correct	48 ms	7208 KB	Output is correct
4	Correct	47 ms	7504 KB	Output is correct
5	Correct	48 ms	7524 KB	Output is correct
6	Correct	47 ms	7456 KB	Output is correct
7	Correct	49 ms	7432 KB	Output is correct
8	Correct	50 ms	7356 KB	Output is correct
9	Correct	48 ms	7392 KB	Output is correct
10	Correct	46 ms	7468 KB	Output is correct
11	Correct	51 ms	7568 KB	Output is correct
12	Correct	47 ms	7344 KB	Output is correct
13	Correct	47 ms	7348 KB	Output is correct
14	Correct	59 ms	7136 KB	Output is correct
15	Correct	53 ms	7432 KB	Output is correct
16	Correct	52 ms	7308 KB	Output is correct
17	Correct	47 ms	7416 KB	Output is correct
18	Correct	47 ms	7324 KB	Output is correct
19	Correct	46 ms	7412 KB	Output is correct
20	Correct	50 ms	7340 KB	Output is correct
21	Correct	47 ms	7264 KB	Output is correct
22	Correct	56 ms	6880 KB	Output is correct
23	Correct	55 ms	7016 KB	Output is correct
24	Correct	50 ms	7180 KB	Output is correct
25	Correct	63 ms	7216 KB	Output is correct
26	Correct	49 ms	7060 KB	Output is correct
27	Correct	49 ms	7208 KB	Output is correct
28	Correct	49 ms	6952 KB	Output is correct
29	Correct	49 ms	7004 KB	Output is correct
30	Correct	53 ms	6936 KB	Output is correct
31	Correct	57 ms	7268 KB	Output is correct
32	Correct	50 ms	7000 KB	Output is correct
33	Correct	49 ms	6996 KB	Output is correct
34	Correct	50 ms	7092 KB	Output is correct
35	Correct	49 ms	6964 KB	Output is correct
36	Correct	49 ms	7064 KB	Output is correct
37	Correct	50 ms	7020 KB	Output is correct
38	Correct	50 ms	6920 KB	Output is correct
39	Correct	49 ms	7344 KB	Output is correct
40	Correct	49 ms	7024 KB	Output is correct
41	Correct	50 ms	7076 KB	Output is correct
42	Correct	49 ms	6864 KB	Output is correct

Subtask #3
34.0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	7408 KB	Output is correct
2	Correct	48 ms	8368 KB	Output is correct
3	Correct	48 ms	7208 KB	Output is correct
4	Correct	47 ms	7504 KB	Output is correct
5	Correct	48 ms	7524 KB	Output is correct
6	Correct	47 ms	7456 KB	Output is correct
7	Correct	49 ms	7432 KB	Output is correct
8	Correct	50 ms	7356 KB	Output is correct
9	Correct	48 ms	7392 KB	Output is correct
10	Correct	46 ms	7468 KB	Output is correct
11	Correct	51 ms	7568 KB	Output is correct
12	Correct	47 ms	7344 KB	Output is correct
13	Correct	47 ms	7348 KB	Output is correct
14	Correct	59 ms	7136 KB	Output is correct
15	Correct	53 ms	7432 KB	Output is correct
16	Correct	52 ms	7308 KB	Output is correct
17	Correct	47 ms	7416 KB	Output is correct
18	Correct	47 ms	7324 KB	Output is correct
19	Correct	46 ms	7412 KB	Output is correct
20	Correct	50 ms	7340 KB	Output is correct
21	Correct	47 ms	7264 KB	Output is correct
22	Correct	56 ms	6880 KB	Output is correct
23	Correct	55 ms	7016 KB	Output is correct
24	Correct	50 ms	7180 KB	Output is correct
25	Correct	63 ms	7216 KB	Output is correct
26	Correct	49 ms	7060 KB	Output is correct
27	Correct	49 ms	7208 KB	Output is correct
28	Correct	49 ms	6952 KB	Output is correct
29	Correct	49 ms	7004 KB	Output is correct
30	Correct	53 ms	6936 KB	Output is correct
31	Correct	57 ms	7268 KB	Output is correct
32	Correct	50 ms	7000 KB	Output is correct
33	Correct	49 ms	6996 KB	Output is correct
34	Correct	50 ms	7092 KB	Output is correct
35	Correct	49 ms	6964 KB	Output is correct
36	Correct	49 ms	7064 KB	Output is correct
37	Correct	50 ms	7020 KB	Output is correct
38	Correct	50 ms	6920 KB	Output is correct
39	Correct	49 ms	7344 KB	Output is correct
40	Correct	49 ms	7024 KB	Output is correct
41	Correct	50 ms	7076 KB	Output is correct
42	Correct	49 ms	6864 KB	Output is correct
43	Correct	114 ms	7196 KB	Output is correct
44	Correct	113 ms	7192 KB	Output is correct
45	Correct	117 ms	7268 KB	Output is correct
46	Correct	116 ms	7192 KB	Output is correct
47	Correct	114 ms	7040 KB	Output is correct
48	Correct	115 ms	7540 KB	Output is correct
49	Correct	120 ms	7092 KB	Output is correct
50	Correct	113 ms	7592 KB	Output is correct
51	Correct	115 ms	7520 KB	Output is correct
52	Correct	114 ms	7184 KB	Output is correct
53	Correct	117 ms	7044 KB	Output is correct
54	Correct	115 ms	7396 KB	Output is correct
55	Correct	114 ms	7180 KB	Output is correct
56	Correct	115 ms	7268 KB	Output is correct
57	Correct	114 ms	7312 KB	Output is correct
58	Correct	114 ms	7652 KB	Output is correct
59	Correct	114 ms	7516 KB	Output is correct
60	Correct	114 ms	7472 KB	Output is correct
61	Correct	114 ms	7276 KB	Output is correct
62	Correct	126 ms	7532 KB	Output is correct
63	Correct	115 ms	7512 KB	Output is correct

Subtask #4
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	7408 KB	Output is correct
2	Correct	48 ms	8368 KB	Output is correct
3	Correct	48 ms	7208 KB	Output is correct
4	Correct	47 ms	7504 KB	Output is correct
5	Correct	48 ms	7524 KB	Output is correct
6	Correct	47 ms	7456 KB	Output is correct
7	Correct	49 ms	7432 KB	Output is correct
8	Correct	50 ms	7356 KB	Output is correct
9	Correct	48 ms	7392 KB	Output is correct
10	Correct	46 ms	7468 KB	Output is correct
11	Correct	51 ms	7568 KB	Output is correct
12	Correct	47 ms	7344 KB	Output is correct
13	Correct	47 ms	7348 KB	Output is correct
14	Correct	59 ms	7136 KB	Output is correct
15	Correct	53 ms	7432 KB	Output is correct
16	Correct	52 ms	7308 KB	Output is correct
17	Correct	47 ms	7416 KB	Output is correct
18	Correct	47 ms	7324 KB	Output is correct
19	Correct	46 ms	7412 KB	Output is correct
20	Correct	50 ms	7340 KB	Output is correct
21	Correct	47 ms	7264 KB	Output is correct
22	Correct	56 ms	6880 KB	Output is correct
23	Correct	55 ms	7016 KB	Output is correct
24	Correct	50 ms	7180 KB	Output is correct
25	Correct	63 ms	7216 KB	Output is correct
26	Correct	49 ms	7060 KB	Output is correct
27	Correct	49 ms	7208 KB	Output is correct
28	Correct	49 ms	6952 KB	Output is correct
29	Correct	49 ms	7004 KB	Output is correct
30	Correct	53 ms	6936 KB	Output is correct
31	Correct	57 ms	7268 KB	Output is correct
32	Correct	50 ms	7000 KB	Output is correct
33	Correct	49 ms	6996 KB	Output is correct
34	Correct	50 ms	7092 KB	Output is correct
35	Correct	49 ms	6964 KB	Output is correct
36	Correct	49 ms	7064 KB	Output is correct
37	Correct	50 ms	7020 KB	Output is correct
38	Correct	50 ms	6920 KB	Output is correct
39	Correct	49 ms	7344 KB	Output is correct
40	Correct	49 ms	7024 KB	Output is correct
41	Correct	50 ms	7076 KB	Output is correct
42	Correct	49 ms	6864 KB	Output is correct
43	Correct	114 ms	7196 KB	Output is correct
44	Correct	113 ms	7192 KB	Output is correct
45	Correct	117 ms	7268 KB	Output is correct
46	Correct	116 ms	7192 KB	Output is correct
47	Correct	114 ms	7040 KB	Output is correct
48	Correct	115 ms	7540 KB	Output is correct
49	Correct	120 ms	7092 KB	Output is correct
50	Correct	113 ms	7592 KB	Output is correct
51	Correct	115 ms	7520 KB	Output is correct
52	Correct	114 ms	7184 KB	Output is correct
53	Correct	117 ms	7044 KB	Output is correct
54	Correct	115 ms	7396 KB	Output is correct
55	Correct	114 ms	7180 KB	Output is correct
56	Correct	115 ms	7268 KB	Output is correct
57	Correct	114 ms	7312 KB	Output is correct
58	Correct	114 ms	7652 KB	Output is correct
59	Correct	114 ms	7516 KB	Output is correct
60	Correct	114 ms	7472 KB	Output is correct
61	Correct	114 ms	7276 KB	Output is correct
62	Correct	126 ms	7532 KB	Output is correct
63	Correct	115 ms	7512 KB	Output is correct
64	Correct	1054 ms	7952 KB	Output is correct
65	Correct	1058 ms	8076 KB	Output is correct
66	Correct	1036 ms	8076 KB	Output is correct
67	Correct	1058 ms	7816 KB	Output is correct
68	Correct	1056 ms	7876 KB	Output is correct
69	Correct	1039 ms	8076 KB	Output is correct
70	Correct	1027 ms	7964 KB	Output is correct
71	Correct	1025 ms	7816 KB	Output is correct
72	Correct	1020 ms	7816 KB	Output is correct
73	Correct	1030 ms	7872 KB	Output is correct
74	Correct	1038 ms	7816 KB	Output is correct
75	Correct	1033 ms	7588 KB	Output is correct
76	Correct	1031 ms	8268 KB	Output is correct
77	Correct	1035 ms	7824 KB	Output is correct
78	Correct	1050 ms	7956 KB	Output is correct
79	Correct	1025 ms	8064 KB	Output is correct
80	Correct	1047 ms	8080 KB	Output is correct
81	Correct	1070 ms	8136 KB	Output is correct
82	Correct	1038 ms	8180 KB	Output is correct
83	Correct	1033 ms	7940 KB	Output is correct
84	Correct	1049 ms	8208 KB	Output is correct

답안 #953620

Compilation message

Subtask #1 21.0 / 21.0

Subtask #2 29.0 / 29.0

Subtask #3 34.0 / 34.0

Subtask #4 16.0 / 16.0

Subtask #1
21.0 / 21.0

Subtask #2
29.0 / 29.0

Subtask #3
34.0 / 34.0

Subtask #4
16.0 / 16.0