oj.uz

답안 #658498

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
658498 2022-11-13T10:45:43 Z mychecksedad Cubeword (CEOI19_cubeword) C++17
50 / 100
 1061 ms 8348 KB 
/* 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];
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 >= 'a' && c <= 'p')) c = 'p' + (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 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 middle = 0; middle < S*S; ++middle){
                    int k = middle / S, l = middle % S;

                    ll pp = (dp[k][l] * dp[x][k] * dp[y][l]) % MOD;
                    ll ppp = (dp[z][k] * dp[w][l]) % MOD;
                    (P += ppp * pp) %= 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:80:16: warning: unused variable 'aa' [-Wunused-variable]
   80 |     int T = 1, aa;
      |                ^~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 994 ms 6568 KB Output is correct
2 Correct 986 ms 6644 KB Output is correct
3 Correct 994 ms 6660 KB Output is correct
4 Correct 1002 ms 6436 KB Output is correct
5 Correct 988 ms 6516 KB Output is correct
6 Correct 997 ms 6468 KB Output is correct
7 Correct 1004 ms 6536 KB Output is correct
8 Correct 999 ms 6620 KB Output is correct
9 Correct 1022 ms 6608 KB Output is correct
10 Correct 1004 ms 6600 KB Output is correct
11 Correct 1010 ms 6544 KB Output is correct
12 Correct 1008 ms 6528 KB Output is correct
13 Correct 990 ms 6648 KB Output is correct
14 Correct 971 ms 6480 KB Output is correct
15 Correct 999 ms 6480 KB Output is correct
16 Correct 1055 ms 6576 KB Output is correct
17 Correct 990 ms 6688 KB Output is correct
18 Correct 1008 ms 6484 KB Output is correct
19 Correct 1006 ms 6496 KB Output is correct
20 Correct 996 ms 6512 KB Output is correct
21 Correct 1010 ms 6532 KB Output is correct

Subtask #2
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 994 ms 6568 KB Output is correct
2 Correct 986 ms 6644 KB Output is correct
3 Correct 994 ms 6660 KB Output is correct
4 Correct 1002 ms 6436 KB Output is correct
5 Correct 988 ms 6516 KB Output is correct
6 Correct 997 ms 6468 KB Output is correct
7 Correct 1004 ms 6536 KB Output is correct
8 Correct 999 ms 6620 KB Output is correct
9 Correct 1022 ms 6608 KB Output is correct
10 Correct 1004 ms 6600 KB Output is correct
11 Correct 1010 ms 6544 KB Output is correct
12 Correct 1008 ms 6528 KB Output is correct
13 Correct 990 ms 6648 KB Output is correct
14 Correct 971 ms 6480 KB Output is correct
15 Correct 999 ms 6480 KB Output is correct
16 Correct 1055 ms 6576 KB Output is correct
17 Correct 990 ms 6688 KB Output is correct
18 Correct 1008 ms 6484 KB Output is correct
19 Correct 1006 ms 6496 KB Output is correct
20 Correct 996 ms 6512 KB Output is correct
21 Correct 1010 ms 6532 KB Output is correct
22 Correct 1024 ms 5704 KB Output is correct
23 Correct 1004 ms 6480 KB Output is correct
24 Correct 988 ms 6464 KB Output is correct
25 Correct 994 ms 6456 KB Output is correct
26 Correct 1030 ms 6460 KB Output is correct
27 Correct 998 ms 6504 KB Output is correct
28 Correct 1061 ms 6544 KB Output is correct
29 Correct 984 ms 6480 KB Output is correct
30 Correct 987 ms 6468 KB Output is correct
31 Correct 1020 ms 6460 KB Output is correct
32 Correct 988 ms 6588 KB Output is correct
33 Correct 999 ms 6556 KB Output is correct
34 Correct 983 ms 6520 KB Output is correct
35 Correct 988 ms 6480 KB Output is correct
36 Correct 1036 ms 6440 KB Output is correct
37 Correct 1006 ms 6380 KB Output is correct
38 Correct 988 ms 6488 KB Output is correct
39 Correct 1004 ms 6444 KB Output is correct
40 Correct 1004 ms 6468 KB Output is correct
41 Correct 1026 ms 6424 KB Output is correct
42 Correct 991 ms 6532 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 994 ms 6568 KB Output is correct
2 Correct 986 ms 6644 KB Output is correct
3 Correct 994 ms 6660 KB Output is correct
4 Correct 1002 ms 6436 KB Output is correct
5 Correct 988 ms 6516 KB Output is correct
6 Correct 997 ms 6468 KB Output is correct
7 Correct 1004 ms 6536 KB Output is correct
8 Correct 999 ms 6620 KB Output is correct
9 Correct 1022 ms 6608 KB Output is correct
10 Correct 1004 ms 6600 KB Output is correct
11 Correct 1010 ms 6544 KB Output is correct
12 Correct 1008 ms 6528 KB Output is correct
13 Correct 990 ms 6648 KB Output is correct
14 Correct 971 ms 6480 KB Output is correct
15 Correct 999 ms 6480 KB Output is correct
16 Correct 1055 ms 6576 KB Output is correct
17 Correct 990 ms 6688 KB Output is correct
18 Correct 1008 ms 6484 KB Output is correct
19 Correct 1006 ms 6496 KB Output is correct
20 Correct 996 ms 6512 KB Output is correct
21 Correct 1010 ms 6532 KB Output is correct
22 Correct 1024 ms 5704 KB Output is correct
23 Correct 1004 ms 6480 KB Output is correct
24 Correct 988 ms 6464 KB Output is correct
25 Correct 994 ms 6456 KB Output is correct
26 Correct 1030 ms 6460 KB Output is correct
27 Correct 998 ms 6504 KB Output is correct
28 Correct 1061 ms 6544 KB Output is correct
29 Correct 984 ms 6480 KB Output is correct
30 Correct 987 ms 6468 KB Output is correct
31 Correct 1020 ms 6460 KB Output is correct
32 Correct 988 ms 6588 KB Output is correct
33 Correct 999 ms 6556 KB Output is correct
34 Correct 983 ms 6520 KB Output is correct
35 Correct 988 ms 6480 KB Output is correct
36 Correct 1036 ms 6440 KB Output is correct
37 Correct 1006 ms 6380 KB Output is correct
38 Correct 988 ms 6488 KB Output is correct
39 Correct 1004 ms 6444 KB Output is correct
40 Correct 1004 ms 6468 KB Output is correct
41 Correct 1026 ms 6424 KB Output is correct
42 Correct 991 ms 6532 KB Output is correct
43 Runtime error 14 ms 8348 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 994 ms 6568 KB Output is correct
2 Correct 986 ms 6644 KB Output is correct
3 Correct 994 ms 6660 KB Output is correct
4 Correct 1002 ms 6436 KB Output is correct
5 Correct 988 ms 6516 KB Output is correct
6 Correct 997 ms 6468 KB Output is correct
7 Correct 1004 ms 6536 KB Output is correct
8 Correct 999 ms 6620 KB Output is correct
9 Correct 1022 ms 6608 KB Output is correct
10 Correct 1004 ms 6600 KB Output is correct
11 Correct 1010 ms 6544 KB Output is correct
12 Correct 1008 ms 6528 KB Output is correct
13 Correct 990 ms 6648 KB Output is correct
14 Correct 971 ms 6480 KB Output is correct
15 Correct 999 ms 6480 KB Output is correct
16 Correct 1055 ms 6576 KB Output is correct
17 Correct 990 ms 6688 KB Output is correct
18 Correct 1008 ms 6484 KB Output is correct
19 Correct 1006 ms 6496 KB Output is correct
20 Correct 996 ms 6512 KB Output is correct
21 Correct 1010 ms 6532 KB Output is correct
22 Correct 1024 ms 5704 KB Output is correct
23 Correct 1004 ms 6480 KB Output is correct
24 Correct 988 ms 6464 KB Output is correct
25 Correct 994 ms 6456 KB Output is correct
26 Correct 1030 ms 6460 KB Output is correct
27 Correct 998 ms 6504 KB Output is correct
28 Correct 1061 ms 6544 KB Output is correct
29 Correct 984 ms 6480 KB Output is correct
30 Correct 987 ms 6468 KB Output is correct
31 Correct 1020 ms 6460 KB Output is correct
32 Correct 988 ms 6588 KB Output is correct
33 Correct 999 ms 6556 KB Output is correct
34 Correct 983 ms 6520 KB Output is correct
35 Correct 988 ms 6480 KB Output is correct
36 Correct 1036 ms 6440 KB Output is correct
37 Correct 1006 ms 6380 KB Output is correct
38 Correct 988 ms 6488 KB Output is correct
39 Correct 1004 ms 6444 KB Output is correct
40 Correct 1004 ms 6468 KB Output is correct
41 Correct 1026 ms 6424 KB Output is correct
42 Correct 991 ms 6532 KB Output is correct
43 Runtime error 14 ms 8348 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -