답안 #658504

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
658504	2022-11-13T11:13:33 Z	mychecksedad	Cubeword (CEOI19_cubeword)	C++17	50 / 100	159 ms	6576 KB

cubeword

/* Author : Mychecksdead */
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long int ll;
typedef long double ld;
#define MOD1 (1000000000+7)
#define MOD (998244353)
#define PI 3.1415926535
#define pb push_back
#define setp() cout << setprecision(15)
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " is " << x << '\n';
const int N = 1e6+100, M = 1e5+10, F = 2147483646, K = 20;

int n, S = 16;
ll dp[100][100], d[N];
vector<string> s[15];
bool is_palindrome(string &a){
    bool ok = 1;
    int x = a.length();
    for(int i = 0; i < x / 2; ++i) ok &= (a[i] == a[x - i - 1]);

    return ok;
}
void solve(){
    cin >> n;
    for(int i = 0; i < n; ++i){
        string a; cin >> a;
        for(char &c: a){
            if(c >= '0' && c <= '9'){
                c = 'z' + 26 + (c - '0') + 1;
            }
            else if(!(c >= 'a' && c <= 'z')){
                c = 'z' + (c - 'A') + 1;
            }
        }
        s[a.length()].pb(a);
    }
    ll ans = 0;
    for(int i = 1; i < 15; ++i){
        if(s[i].empty()) continue;
        for(int j = 0; j < S; ++j) for(int k = 0; k < S; ++k) dp[j][k] = 0;
        
        map<string, bool> used;
        for(auto a: s[i]){
            if(used[a]) continue;
            if(is_palindrome(a)){
                dp[a[0] - 'a'][a[0] - 'a']++;
            }else{
                dp[a[0] - 'a'][a.back() - 'a']++;
                dp[a.back() - 'a'][a[0] - 'a']++;
            }
            reverse(all(a));
            used[a] = 1;
        }

        for(int mask = 0; mask < S*S*S; mask++){
            int x = mask % S, y = (mask / S) % S, z = mask / S / S;
            d[mask] = 0;
            for(int l = 0; l < S; ++l){
                (d[mask] += dp[x][l] * dp[y][l] * dp[z][l]) %= MOD;
            }
        }

        for(int left = 0; left < S*S; ++left){
            int x = left / S, y = left % S;
            for(int right = 0; right < S*S; ++right){
                int z = right / S, w = right % S;

                ll p = dp[x][y] * dp[z][w] % MOD;

                ll P = 0;


                for(int l = 0; l < S; ++l){
                    ll pp = (dp[x][l] * dp[z][l]) % MOD;
                    (P += pp * d[y + l * S + w * S * S]) %= MOD;
                }

                (P *= P) %= MOD;
                (ans += P * p) %= MOD;
            }
        }
    }
    cout << ans;
}





int main(){
    cin.tie(0); ios::sync_with_stdio(0);
    int T = 1, aa;
    // cin >> T;aa=T;
    while(T--){
        // cout << "Case #" << aa-T << ": ";
        solve();
    }
    return 0;
 
}

Compilation message

cubeword.cpp: In function 'int main()':
cubeword.cpp:96:16: warning: unused variable 'aa' [-Wunused-variable]
   96 |     int T = 1, aa;
      |                ^~

Subtask #1

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	129 ms	6456 KB	Output is correct
2	Correct	127 ms	6484 KB	Output is correct
3	Correct	110 ms	6524 KB	Output is correct
4	Correct	110 ms	6544 KB	Output is correct
5	Correct	120 ms	6456 KB	Output is correct
6	Correct	125 ms	6524 KB	Output is correct
7	Correct	122 ms	6552 KB	Output is correct
8	Correct	110 ms	6576 KB	Output is correct
9	Correct	111 ms	6484 KB	Output is correct
10	Correct	134 ms	6512 KB	Output is correct
11	Correct	118 ms	6460 KB	Output is correct
12	Correct	110 ms	6512 KB	Output is correct
13	Correct	110 ms	6556 KB	Output is correct
14	Correct	110 ms	6512 KB	Output is correct
15	Correct	117 ms	6524 KB	Output is correct
16	Correct	115 ms	6548 KB	Output is correct
17	Correct	112 ms	6560 KB	Output is correct
18	Correct	116 ms	6524 KB	Output is correct
19	Correct	129 ms	6500 KB	Output is correct
20	Correct	110 ms	6432 KB	Output is correct
21	Correct	114 ms	6404 KB	Output is correct

Subtask #2

29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	129 ms	6456 KB	Output is correct
2	Correct	127 ms	6484 KB	Output is correct
3	Correct	110 ms	6524 KB	Output is correct
4	Correct	110 ms	6544 KB	Output is correct
5	Correct	120 ms	6456 KB	Output is correct
6	Correct	125 ms	6524 KB	Output is correct
7	Correct	122 ms	6552 KB	Output is correct
8	Correct	110 ms	6576 KB	Output is correct
9	Correct	111 ms	6484 KB	Output is correct
10	Correct	134 ms	6512 KB	Output is correct
11	Correct	118 ms	6460 KB	Output is correct
12	Correct	110 ms	6512 KB	Output is correct
13	Correct	110 ms	6556 KB	Output is correct
14	Correct	110 ms	6512 KB	Output is correct
15	Correct	117 ms	6524 KB	Output is correct
16	Correct	115 ms	6548 KB	Output is correct
17	Correct	112 ms	6560 KB	Output is correct
18	Correct	116 ms	6524 KB	Output is correct
19	Correct	129 ms	6500 KB	Output is correct
20	Correct	110 ms	6432 KB	Output is correct
21	Correct	114 ms	6404 KB	Output is correct
22	Correct	136 ms	5696 KB	Output is correct
23	Correct	121 ms	5724 KB	Output is correct
24	Correct	110 ms	5704 KB	Output is correct
25	Correct	109 ms	5728 KB	Output is correct
26	Correct	110 ms	5636 KB	Output is correct
27	Correct	114 ms	5704 KB	Output is correct
28	Correct	114 ms	5676 KB	Output is correct
29	Correct	110 ms	5680 KB	Output is correct
30	Correct	113 ms	5840 KB	Output is correct
31	Correct	109 ms	5656 KB	Output is correct
32	Correct	126 ms	5664 KB	Output is correct
33	Correct	111 ms	5716 KB	Output is correct
34	Correct	109 ms	5652 KB	Output is correct
35	Correct	117 ms	5740 KB	Output is correct
36	Correct	113 ms	5720 KB	Output is correct
37	Correct	117 ms	5724 KB	Output is correct
38	Correct	112 ms	5656 KB	Output is correct
39	Correct	109 ms	5672 KB	Output is correct
40	Correct	120 ms	5724 KB	Output is correct
41	Correct	136 ms	5796 KB	Output is correct
42	Correct	128 ms	5756 KB	Output is correct

Subtask #3

0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	129 ms	6456 KB	Output is correct
2	Correct	127 ms	6484 KB	Output is correct
3	Correct	110 ms	6524 KB	Output is correct
4	Correct	110 ms	6544 KB	Output is correct
5	Correct	120 ms	6456 KB	Output is correct
6	Correct	125 ms	6524 KB	Output is correct
7	Correct	122 ms	6552 KB	Output is correct
8	Correct	110 ms	6576 KB	Output is correct
9	Correct	111 ms	6484 KB	Output is correct
10	Correct	134 ms	6512 KB	Output is correct
11	Correct	118 ms	6460 KB	Output is correct
12	Correct	110 ms	6512 KB	Output is correct
13	Correct	110 ms	6556 KB	Output is correct
14	Correct	110 ms	6512 KB	Output is correct
15	Correct	117 ms	6524 KB	Output is correct
16	Correct	115 ms	6548 KB	Output is correct
17	Correct	112 ms	6560 KB	Output is correct
18	Correct	116 ms	6524 KB	Output is correct
19	Correct	129 ms	6500 KB	Output is correct
20	Correct	110 ms	6432 KB	Output is correct
21	Correct	114 ms	6404 KB	Output is correct
22	Correct	136 ms	5696 KB	Output is correct
23	Correct	121 ms	5724 KB	Output is correct
24	Correct	110 ms	5704 KB	Output is correct
25	Correct	109 ms	5728 KB	Output is correct
26	Correct	110 ms	5636 KB	Output is correct
27	Correct	114 ms	5704 KB	Output is correct
28	Correct	114 ms	5676 KB	Output is correct
29	Correct	110 ms	5680 KB	Output is correct
30	Correct	113 ms	5840 KB	Output is correct
31	Correct	109 ms	5656 KB	Output is correct
32	Correct	126 ms	5664 KB	Output is correct
33	Correct	111 ms	5716 KB	Output is correct
34	Correct	109 ms	5652 KB	Output is correct
35	Correct	117 ms	5740 KB	Output is correct
36	Correct	113 ms	5720 KB	Output is correct
37	Correct	117 ms	5724 KB	Output is correct
38	Correct	112 ms	5656 KB	Output is correct
39	Correct	109 ms	5672 KB	Output is correct
40	Correct	120 ms	5724 KB	Output is correct
41	Correct	136 ms	5796 KB	Output is correct
42	Correct	128 ms	5756 KB	Output is correct
43	Incorrect	159 ms	5544 KB	Output isn't correct
44	Halted	0 ms	0 KB	-

Subtask #4

0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	129 ms	6456 KB	Output is correct
2	Correct	127 ms	6484 KB	Output is correct
3	Correct	110 ms	6524 KB	Output is correct
4	Correct	110 ms	6544 KB	Output is correct
5	Correct	120 ms	6456 KB	Output is correct
6	Correct	125 ms	6524 KB	Output is correct
7	Correct	122 ms	6552 KB	Output is correct
8	Correct	110 ms	6576 KB	Output is correct
9	Correct	111 ms	6484 KB	Output is correct
10	Correct	134 ms	6512 KB	Output is correct
11	Correct	118 ms	6460 KB	Output is correct
12	Correct	110 ms	6512 KB	Output is correct
13	Correct	110 ms	6556 KB	Output is correct
14	Correct	110 ms	6512 KB	Output is correct
15	Correct	117 ms	6524 KB	Output is correct
16	Correct	115 ms	6548 KB	Output is correct
17	Correct	112 ms	6560 KB	Output is correct
18	Correct	116 ms	6524 KB	Output is correct
19	Correct	129 ms	6500 KB	Output is correct
20	Correct	110 ms	6432 KB	Output is correct
21	Correct	114 ms	6404 KB	Output is correct
22	Correct	136 ms	5696 KB	Output is correct
23	Correct	121 ms	5724 KB	Output is correct
24	Correct	110 ms	5704 KB	Output is correct
25	Correct	109 ms	5728 KB	Output is correct
26	Correct	110 ms	5636 KB	Output is correct
27	Correct	114 ms	5704 KB	Output is correct
28	Correct	114 ms	5676 KB	Output is correct
29	Correct	110 ms	5680 KB	Output is correct
30	Correct	113 ms	5840 KB	Output is correct
31	Correct	109 ms	5656 KB	Output is correct
32	Correct	126 ms	5664 KB	Output is correct
33	Correct	111 ms	5716 KB	Output is correct
34	Correct	109 ms	5652 KB	Output is correct
35	Correct	117 ms	5740 KB	Output is correct
36	Correct	113 ms	5720 KB	Output is correct
37	Correct	117 ms	5724 KB	Output is correct
38	Correct	112 ms	5656 KB	Output is correct
39	Correct	109 ms	5672 KB	Output is correct
40	Correct	120 ms	5724 KB	Output is correct
41	Correct	136 ms	5796 KB	Output is correct
42	Correct	128 ms	5756 KB	Output is correct
43	Incorrect	159 ms	5544 KB	Output isn't correct
44	Halted	0 ms	0 KB	-