답안 #658586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
658586	2022-11-13T15:28:03 Z	mychecksedad	Cubeword (CEOI19_cubeword)	C++17	50 / 100	230 ms	8068 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 = 65, mul[8] = { 24, 12, 12, 4, 12, 6, 4, 1 };
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){
    int q = 0;
    if(a==b) q += 1;
    if(b==c) q += 2;
    if(c==d) q += 4;
    return mul[q];
}

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] % MOD) * 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:101:16: warning: unused variable 'aa' [-Wunused-variable]
  101 |     int T = 1, aa;
      |                ^~

Subtask #1

21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	221 ms	8068 KB	Output is correct
2	Correct	218 ms	7940 KB	Output is correct
3	Correct	230 ms	8044 KB	Output is correct
4	Correct	217 ms	7996 KB	Output is correct
5	Correct	221 ms	7956 KB	Output is correct
6	Correct	225 ms	7944 KB	Output is correct
7	Correct	220 ms	7972 KB	Output is correct
8	Correct	217 ms	7920 KB	Output is correct
9	Correct	221 ms	7952 KB	Output is correct
10	Correct	220 ms	7992 KB	Output is correct
11	Correct	226 ms	7972 KB	Output is correct
12	Correct	225 ms	7960 KB	Output is correct
13	Correct	216 ms	7976 KB	Output is correct
14	Correct	220 ms	8000 KB	Output is correct
15	Correct	224 ms	7996 KB	Output is correct
16	Correct	221 ms	7952 KB	Output is correct
17	Correct	220 ms	8000 KB	Output is correct
18	Correct	228 ms	7972 KB	Output is correct
19	Correct	219 ms	7988 KB	Output is correct
20	Correct	219 ms	7880 KB	Output is correct
21	Correct	229 ms	7884 KB	Output is correct

Subtask #2

29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	221 ms	8068 KB	Output is correct
2	Correct	218 ms	7940 KB	Output is correct
3	Correct	230 ms	8044 KB	Output is correct
4	Correct	217 ms	7996 KB	Output is correct
5	Correct	221 ms	7956 KB	Output is correct
6	Correct	225 ms	7944 KB	Output is correct
7	Correct	220 ms	7972 KB	Output is correct
8	Correct	217 ms	7920 KB	Output is correct
9	Correct	221 ms	7952 KB	Output is correct
10	Correct	220 ms	7992 KB	Output is correct
11	Correct	226 ms	7972 KB	Output is correct
12	Correct	225 ms	7960 KB	Output is correct
13	Correct	216 ms	7976 KB	Output is correct
14	Correct	220 ms	8000 KB	Output is correct
15	Correct	224 ms	7996 KB	Output is correct
16	Correct	221 ms	7952 KB	Output is correct
17	Correct	220 ms	8000 KB	Output is correct
18	Correct	228 ms	7972 KB	Output is correct
19	Correct	219 ms	7988 KB	Output is correct
20	Correct	219 ms	7880 KB	Output is correct
21	Correct	229 ms	7884 KB	Output is correct
22	Correct	216 ms	7128 KB	Output is correct
23	Correct	222 ms	7172 KB	Output is correct
24	Correct	220 ms	7272 KB	Output is correct
25	Correct	217 ms	7152 KB	Output is correct
26	Correct	223 ms	7184 KB	Output is correct
27	Correct	218 ms	7148 KB	Output is correct
28	Correct	220 ms	7168 KB	Output is correct
29	Correct	215 ms	7120 KB	Output is correct
30	Correct	217 ms	7080 KB	Output is correct
31	Correct	215 ms	7152 KB	Output is correct
32	Correct	217 ms	7152 KB	Output is correct
33	Correct	219 ms	7116 KB	Output is correct
34	Correct	219 ms	7160 KB	Output is correct
35	Correct	216 ms	7112 KB	Output is correct
36	Correct	214 ms	7160 KB	Output is correct
37	Correct	221 ms	7252 KB	Output is correct
38	Correct	214 ms	7272 KB	Output is correct
39	Correct	215 ms	7076 KB	Output is correct
40	Correct	216 ms	7200 KB	Output is correct
41	Correct	217 ms	7164 KB	Output is correct
42	Correct	217 ms	7116 KB	Output is correct

Subtask #3

0 / 34.0

#	결과	실행 시간	메모리	Grader output
1	Correct	221 ms	8068 KB	Output is correct
2	Correct	218 ms	7940 KB	Output is correct
3	Correct	230 ms	8044 KB	Output is correct
4	Correct	217 ms	7996 KB	Output is correct
5	Correct	221 ms	7956 KB	Output is correct
6	Correct	225 ms	7944 KB	Output is correct
7	Correct	220 ms	7972 KB	Output is correct
8	Correct	217 ms	7920 KB	Output is correct
9	Correct	221 ms	7952 KB	Output is correct
10	Correct	220 ms	7992 KB	Output is correct
11	Correct	226 ms	7972 KB	Output is correct
12	Correct	225 ms	7960 KB	Output is correct
13	Correct	216 ms	7976 KB	Output is correct
14	Correct	220 ms	8000 KB	Output is correct
15	Correct	224 ms	7996 KB	Output is correct
16	Correct	221 ms	7952 KB	Output is correct
17	Correct	220 ms	8000 KB	Output is correct
18	Correct	228 ms	7972 KB	Output is correct
19	Correct	219 ms	7988 KB	Output is correct
20	Correct	219 ms	7880 KB	Output is correct
21	Correct	229 ms	7884 KB	Output is correct
22	Correct	216 ms	7128 KB	Output is correct
23	Correct	222 ms	7172 KB	Output is correct
24	Correct	220 ms	7272 KB	Output is correct
25	Correct	217 ms	7152 KB	Output is correct
26	Correct	223 ms	7184 KB	Output is correct
27	Correct	218 ms	7148 KB	Output is correct
28	Correct	220 ms	7168 KB	Output is correct
29	Correct	215 ms	7120 KB	Output is correct
30	Correct	217 ms	7080 KB	Output is correct
31	Correct	215 ms	7152 KB	Output is correct
32	Correct	217 ms	7152 KB	Output is correct
33	Correct	219 ms	7116 KB	Output is correct
34	Correct	219 ms	7160 KB	Output is correct
35	Correct	216 ms	7112 KB	Output is correct
36	Correct	214 ms	7160 KB	Output is correct
37	Correct	221 ms	7252 KB	Output is correct
38	Correct	214 ms	7272 KB	Output is correct
39	Correct	215 ms	7076 KB	Output is correct
40	Correct	216 ms	7200 KB	Output is correct
41	Correct	217 ms	7164 KB	Output is correct
42	Correct	217 ms	7116 KB	Output is correct
43	Incorrect	218 ms	7200 KB	Output isn't correct
44	Halted	0 ms	0 KB	-

Subtask #4

0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	221 ms	8068 KB	Output is correct
2	Correct	218 ms	7940 KB	Output is correct
3	Correct	230 ms	8044 KB	Output is correct
4	Correct	217 ms	7996 KB	Output is correct
5	Correct	221 ms	7956 KB	Output is correct
6	Correct	225 ms	7944 KB	Output is correct
7	Correct	220 ms	7972 KB	Output is correct
8	Correct	217 ms	7920 KB	Output is correct
9	Correct	221 ms	7952 KB	Output is correct
10	Correct	220 ms	7992 KB	Output is correct
11	Correct	226 ms	7972 KB	Output is correct
12	Correct	225 ms	7960 KB	Output is correct
13	Correct	216 ms	7976 KB	Output is correct
14	Correct	220 ms	8000 KB	Output is correct
15	Correct	224 ms	7996 KB	Output is correct
16	Correct	221 ms	7952 KB	Output is correct
17	Correct	220 ms	8000 KB	Output is correct
18	Correct	228 ms	7972 KB	Output is correct
19	Correct	219 ms	7988 KB	Output is correct
20	Correct	219 ms	7880 KB	Output is correct
21	Correct	229 ms	7884 KB	Output is correct
22	Correct	216 ms	7128 KB	Output is correct
23	Correct	222 ms	7172 KB	Output is correct
24	Correct	220 ms	7272 KB	Output is correct
25	Correct	217 ms	7152 KB	Output is correct
26	Correct	223 ms	7184 KB	Output is correct
27	Correct	218 ms	7148 KB	Output is correct
28	Correct	220 ms	7168 KB	Output is correct
29	Correct	215 ms	7120 KB	Output is correct
30	Correct	217 ms	7080 KB	Output is correct
31	Correct	215 ms	7152 KB	Output is correct
32	Correct	217 ms	7152 KB	Output is correct
33	Correct	219 ms	7116 KB	Output is correct
34	Correct	219 ms	7160 KB	Output is correct
35	Correct	216 ms	7112 KB	Output is correct
36	Correct	214 ms	7160 KB	Output is correct
37	Correct	221 ms	7252 KB	Output is correct
38	Correct	214 ms	7272 KB	Output is correct
39	Correct	215 ms	7076 KB	Output is correct
40	Correct	216 ms	7200 KB	Output is correct
41	Correct	217 ms	7164 KB	Output is correct
42	Correct	217 ms	7116 KB	Output is correct
43	Incorrect	218 ms	7200 KB	Output isn't correct
44	Halted	0 ms	0 KB	-