답안 #658582

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
658582	2022-11-13T15:15:51 Z	mychecksedad	Cubeword (CEOI19_cubeword)	C++17	50 / 100	235 ms	7996 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 = 63;
ll dp[100][100], d[70][70][70];
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;
}

int comb(int a, int b, int c, int d){
    if(a==b && b==c && c==d) return 1;
    if(a==b && b==c && c!=d) return 4;
    if(a==b && b!=c && c==d) return 6;
    if(a!=b && b==c && c==d) return 4;
    if(a==b && b!=c && c!=d) return 12;
    if(a!=b && b==c && c!=d) return 12;
    if(a!=b && b!=c && c==d) return 12;
    return 24;
}

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 a = 0; a < S; ++a){
            for(int b = a; b < S; ++b){
                for(int c = b; c < S; ++c){
                    d[a][b][c] = 0;
                    for(int l = 0; l < S; ++l){
                        (d[a][b][c] += dp[a][l] * dp[b][l] * dp[c][l]) %= MOD;
                    }   
                }
            }
        }

        for(int a = 0; a < S; ++a){
            for(int b = a; b < S; ++b){
                for(int c = b; c < S; ++c){
                    for(int e = c; e < S; ++e){
                        ll p = (d[a][b][c] * d[a][b][e] % MOD) * (d[a][c][e] * d[b][c][e] % MOD) % MOD;
                        (ans += p * comb(a, b, c, e)) %= 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:104:16: warning: unused variable 'aa' [-Wunused-variable]
  104 |     int T = 1, aa;
      |                ^~

Subtask #1

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	218 ms	7836 KB	Output is correct
2	Correct	213 ms	7976 KB	Output is correct
3	Correct	235 ms	7996 KB	Output is correct
4	Correct	208 ms	7820 KB	Output is correct
5	Correct	220 ms	7888 KB	Output is correct
6	Correct	210 ms	7840 KB	Output is correct
7	Correct	206 ms	7852 KB	Output is correct
8	Correct	203 ms	7940 KB	Output is correct
9	Correct	201 ms	7860 KB	Output is correct
10	Correct	203 ms	7904 KB	Output is correct
11	Correct	206 ms	7832 KB	Output is correct
12	Correct	205 ms	7848 KB	Output is correct
13	Correct	207 ms	7840 KB	Output is correct
14	Correct	204 ms	7916 KB	Output is correct
15	Correct	203 ms	7844 KB	Output is correct
16	Correct	212 ms	7992 KB	Output is correct
17	Correct	203 ms	7916 KB	Output is correct
18	Correct	221 ms	7828 KB	Output is correct
19	Correct	203 ms	7884 KB	Output is correct
20	Correct	217 ms	7792 KB	Output is correct
21	Correct	217 ms	7808 KB	Output is correct

Subtask #2

29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	218 ms	7836 KB	Output is correct
2	Correct	213 ms	7976 KB	Output is correct
3	Correct	235 ms	7996 KB	Output is correct
4	Correct	208 ms	7820 KB	Output is correct
5	Correct	220 ms	7888 KB	Output is correct
6	Correct	210 ms	7840 KB	Output is correct
7	Correct	206 ms	7852 KB	Output is correct
8	Correct	203 ms	7940 KB	Output is correct
9	Correct	201 ms	7860 KB	Output is correct
10	Correct	203 ms	7904 KB	Output is correct
11	Correct	206 ms	7832 KB	Output is correct
12	Correct	205 ms	7848 KB	Output is correct
13	Correct	207 ms	7840 KB	Output is correct
14	Correct	204 ms	7916 KB	Output is correct
15	Correct	203 ms	7844 KB	Output is correct
16	Correct	212 ms	7992 KB	Output is correct
17	Correct	203 ms	7916 KB	Output is correct
18	Correct	221 ms	7828 KB	Output is correct
19	Correct	203 ms	7884 KB	Output is correct
20	Correct	217 ms	7792 KB	Output is correct
21	Correct	217 ms	7808 KB	Output is correct
22	Correct	204 ms	7092 KB	Output is correct
23	Correct	201 ms	7008 KB	Output is correct
24	Correct	208 ms	7004 KB	Output is correct
25	Correct	208 ms	7072 KB	Output is correct
26	Correct	201 ms	7076 KB	Output is correct
27	Correct	199 ms	7028 KB	Output is correct
28	Correct	229 ms	7004 KB	Output is correct
29	Correct	209 ms	7188 KB	Output is correct
30	Correct	211 ms	7000 KB	Output is correct
31	Correct	230 ms	7072 KB	Output is correct
32	Correct	206 ms	7160 KB	Output is correct
33	Correct	223 ms	6992 KB	Output is correct
34	Correct	208 ms	7124 KB	Output is correct
35	Correct	207 ms	7072 KB	Output is correct
36	Correct	209 ms	7080 KB	Output is correct
37	Correct	198 ms	7096 KB	Output is correct
38	Correct	196 ms	7096 KB	Output is correct
39	Correct	222 ms	7056 KB	Output is correct
40	Correct	200 ms	7188 KB	Output is correct
41	Correct	206 ms	7008 KB	Output is correct
42	Correct	215 ms	7232 KB	Output is correct

Subtask #3

0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	218 ms	7836 KB	Output is correct
2	Correct	213 ms	7976 KB	Output is correct
3	Correct	235 ms	7996 KB	Output is correct
4	Correct	208 ms	7820 KB	Output is correct
5	Correct	220 ms	7888 KB	Output is correct
6	Correct	210 ms	7840 KB	Output is correct
7	Correct	206 ms	7852 KB	Output is correct
8	Correct	203 ms	7940 KB	Output is correct
9	Correct	201 ms	7860 KB	Output is correct
10	Correct	203 ms	7904 KB	Output is correct
11	Correct	206 ms	7832 KB	Output is correct
12	Correct	205 ms	7848 KB	Output is correct
13	Correct	207 ms	7840 KB	Output is correct
14	Correct	204 ms	7916 KB	Output is correct
15	Correct	203 ms	7844 KB	Output is correct
16	Correct	212 ms	7992 KB	Output is correct
17	Correct	203 ms	7916 KB	Output is correct
18	Correct	221 ms	7828 KB	Output is correct
19	Correct	203 ms	7884 KB	Output is correct
20	Correct	217 ms	7792 KB	Output is correct
21	Correct	217 ms	7808 KB	Output is correct
22	Correct	204 ms	7092 KB	Output is correct
23	Correct	201 ms	7008 KB	Output is correct
24	Correct	208 ms	7004 KB	Output is correct
25	Correct	208 ms	7072 KB	Output is correct
26	Correct	201 ms	7076 KB	Output is correct
27	Correct	199 ms	7028 KB	Output is correct
28	Correct	229 ms	7004 KB	Output is correct
29	Correct	209 ms	7188 KB	Output is correct
30	Correct	211 ms	7000 KB	Output is correct
31	Correct	230 ms	7072 KB	Output is correct
32	Correct	206 ms	7160 KB	Output is correct
33	Correct	223 ms	6992 KB	Output is correct
34	Correct	208 ms	7124 KB	Output is correct
35	Correct	207 ms	7072 KB	Output is correct
36	Correct	209 ms	7080 KB	Output is correct
37	Correct	198 ms	7096 KB	Output is correct
38	Correct	196 ms	7096 KB	Output is correct
39	Correct	222 ms	7056 KB	Output is correct
40	Correct	200 ms	7188 KB	Output is correct
41	Correct	206 ms	7008 KB	Output is correct
42	Correct	215 ms	7232 KB	Output is correct
43	Incorrect	209 ms	6988 KB	Output isn't correct
44	Halted	0 ms	0 KB	-

Subtask #4

0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	218 ms	7836 KB	Output is correct
2	Correct	213 ms	7976 KB	Output is correct
3	Correct	235 ms	7996 KB	Output is correct
4	Correct	208 ms	7820 KB	Output is correct
5	Correct	220 ms	7888 KB	Output is correct
6	Correct	210 ms	7840 KB	Output is correct
7	Correct	206 ms	7852 KB	Output is correct
8	Correct	203 ms	7940 KB	Output is correct
9	Correct	201 ms	7860 KB	Output is correct
10	Correct	203 ms	7904 KB	Output is correct
11	Correct	206 ms	7832 KB	Output is correct
12	Correct	205 ms	7848 KB	Output is correct
13	Correct	207 ms	7840 KB	Output is correct
14	Correct	204 ms	7916 KB	Output is correct
15	Correct	203 ms	7844 KB	Output is correct
16	Correct	212 ms	7992 KB	Output is correct
17	Correct	203 ms	7916 KB	Output is correct
18	Correct	221 ms	7828 KB	Output is correct
19	Correct	203 ms	7884 KB	Output is correct
20	Correct	217 ms	7792 KB	Output is correct
21	Correct	217 ms	7808 KB	Output is correct
22	Correct	204 ms	7092 KB	Output is correct
23	Correct	201 ms	7008 KB	Output is correct
24	Correct	208 ms	7004 KB	Output is correct
25	Correct	208 ms	7072 KB	Output is correct
26	Correct	201 ms	7076 KB	Output is correct
27	Correct	199 ms	7028 KB	Output is correct
28	Correct	229 ms	7004 KB	Output is correct
29	Correct	209 ms	7188 KB	Output is correct
30	Correct	211 ms	7000 KB	Output is correct
31	Correct	230 ms	7072 KB	Output is correct
32	Correct	206 ms	7160 KB	Output is correct
33	Correct	223 ms	6992 KB	Output is correct
34	Correct	208 ms	7124 KB	Output is correct
35	Correct	207 ms	7072 KB	Output is correct
36	Correct	209 ms	7080 KB	Output is correct
37	Correct	198 ms	7096 KB	Output is correct
38	Correct	196 ms	7096 KB	Output is correct
39	Correct	222 ms	7056 KB	Output is correct
40	Correct	200 ms	7188 KB	Output is correct
41	Correct	206 ms	7008 KB	Output is correct
42	Correct	215 ms	7232 KB	Output is correct
43	Incorrect	209 ms	6988 KB	Output isn't correct
44	Halted	0 ms	0 KB	-