oj.uz

Submission #597168

# Submission time Handle Problem Language Result Execution time Memory
597168 2022-07-15T16:20:08 Z Valaki2 Cubeword (CEOI19_cubeword) C++14
50 / 100
 635 ms 15056 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int mod = 998244353;

const int maxn = 2e5;
const int min_l = 3;
const int max_l = 10;
const int max_ch = 16;

int combinations[max_l + 1][max_ch][max_ch];

int convert(char ch) {
    if(ch >= 'a' && ch <= 'p') {
        return ch - 'a';
    }
    if(ch >= 'q' && ch <= 'z') {
        return ch - 'q' + 32;
    }
    if(ch >= 'A' && ch <= 'P') {
        return ch - 'A' + 16;
    }
    if(ch >= 'Q' && ch <= 'Z') {
        return ch - 'Q' + 42;
    }
    if(ch >= '0' && ch <= '9') {
        return ch - '0' + 52;
    }
}

int n;
vector<string> v;
int ans;

int len;
vector<int> corners;
// vector<pii > neighbours;
int number[max_ch][max_ch][max_ch];
int prec[max_ch][max_ch][max_ch][max_ch];

int try_scenario() {
    int res = 1;
    for(int i = 1; i <= 3; i++) {
        res = (res * combinations[len][corners[0]][corners[i]]) % mod;
    }
    return res;
}

void backtrack(int corner_id) {
    if(corner_id == 4) {
        number[corners[1]][corners[2]][corners[3]] = (number[corners[1]][corners[2]][corners[3]] + try_scenario()) % mod;
    } else {
        for(corners[corner_id] = 0; corners[corner_id] < max_ch; corners[corner_id]++) {
            backtrack(corner_id + 1);
        }
    }
}

void solve() {
    cin >> n;
    //n = 1;
    v.assign(2 * n, "");
    for(int i = 0; i < n; i++) {
        cin >> v[i];
        //v[i] = "cabac";
        v[i + n] = v[i];
        reverse(v[i + n].begin(), v[i + n].end());
    }
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    n = (int) v.size();
    for(int i = 0; i < n; i++) {
        int cur_length = (int) v[i].size();
        int cur_first = convert(v[i].front());
        int cur_last = convert(v[i].back());
        combinations[cur_length][cur_first][cur_last]++;
    }
    /*for(int i = 0; i < 8; i++) {
        for(int j = i + 1; j < 8; j++) {
            if(__builtin_popcount(i ^ j) == 1) {
                neighbours.pb(mp(i, j));
            }
        }
    }*/
    corners.assign(4, 0);
    for(len = min_l; len <= max_l; len++) {
        // reset everything
        for(int i = 0; i < max_ch; i++) {
            for(int j = 0; j < max_ch; j++) {
                for(int k = 0; k < max_ch; k++) {
                    number[i][j][k] = 0;
                    for(int l = 0; l < max_ch; l++) {
                        prec[i][j][k][l] = combinations[len][i][j] * combinations[len][j][k] % mod * combinations[len][k][l] % mod;
                    }
                }
            }
        }
        backtrack(0);
        for(int a1 = 0; a1 < max_ch; a1++) {
            for(int a2 = 0; a2 < max_ch; a2++) {
                for(int a3 = 0; a3 < max_ch; a3++) {
                    for(int b1 = 0; b1 < max_ch; b1++) {
                        for(int b2 = 0; b2 < max_ch; b2++) {
                            for(int b3 = 0; b3 < max_ch; b3++) {
                                ans = (ans + (number[a1][a2][a3] * number[b1][b2][b3] % mod
                                    /** combinations[len][a1][b1] % mod
                                    * combinations[len][b1][a2] % mod
                                    * combinations[len][a2][b2] % mod
                                    * combinations[len][b2][a3] % mod
                                    * combinations[len][a3][b3] % mod
                                    * combinations[len][b3][a1] % mod*/
                                    * prec[a1][b1][a2][b2] % mod
                                    * prec[b2][a3][b3][a1]));
                            }
                            ans %= mod;
                        }
                    }
                }
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Compilation message

cubeword.cpp: In function 'long long int convert(char)':
cubeword.cpp:40:1: warning: control reaches end of non-void function [-Wreturn-type]
   40 | }
      | ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 7100 KB Output is correct
2 Correct 616 ms 7108 KB Output is correct
3 Correct 627 ms 7116 KB Output is correct
4 Correct 591 ms 7120 KB Output is correct
5 Correct 603 ms 7120 KB Output is correct
6 Correct 612 ms 7100 KB Output is correct
7 Correct 626 ms 7116 KB Output is correct
8 Correct 594 ms 7100 KB Output is correct
9 Correct 609 ms 7120 KB Output is correct
10 Correct 635 ms 7116 KB Output is correct
11 Correct 589 ms 7112 KB Output is correct
12 Correct 593 ms 7116 KB Output is correct
13 Correct 596 ms 7116 KB Output is correct
14 Correct 597 ms 7100 KB Output is correct
15 Correct 601 ms 7116 KB Output is correct
16 Correct 605 ms 7104 KB Output is correct
17 Correct 612 ms 7112 KB Output is correct
18 Correct 609 ms 7112 KB Output is correct
19 Correct 597 ms 7104 KB Output is correct
20 Correct 610 ms 7108 KB Output is correct
21 Correct 615 ms 7104 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 7100 KB Output is correct
2 Correct 616 ms 7108 KB Output is correct
3 Correct 627 ms 7116 KB Output is correct
4 Correct 591 ms 7120 KB Output is correct
5 Correct 603 ms 7120 KB Output is correct
6 Correct 612 ms 7100 KB Output is correct
7 Correct 626 ms 7116 KB Output is correct
8 Correct 594 ms 7100 KB Output is correct
9 Correct 609 ms 7120 KB Output is correct
10 Correct 635 ms 7116 KB Output is correct
11 Correct 589 ms 7112 KB Output is correct
12 Correct 593 ms 7116 KB Output is correct
13 Correct 596 ms 7116 KB Output is correct
14 Correct 597 ms 7100 KB Output is correct
15 Correct 601 ms 7116 KB Output is correct
16 Correct 605 ms 7104 KB Output is correct
17 Correct 612 ms 7112 KB Output is correct
18 Correct 609 ms 7112 KB Output is correct
19 Correct 597 ms 7104 KB Output is correct
20 Correct 610 ms 7108 KB Output is correct
21 Correct 615 ms 7104 KB Output is correct
22 Correct 609 ms 7112 KB Output is correct
23 Correct 577 ms 7880 KB Output is correct
24 Correct 589 ms 7896 KB Output is correct
25 Correct 586 ms 7880 KB Output is correct
26 Correct 589 ms 7880 KB Output is correct
27 Correct 583 ms 7876 KB Output is correct
28 Correct 579 ms 7880 KB Output is correct
29 Correct 579 ms 7880 KB Output is correct
30 Correct 580 ms 7888 KB Output is correct
31 Correct 580 ms 7880 KB Output is correct
32 Correct 578 ms 7884 KB Output is correct
33 Correct 582 ms 7856 KB Output is correct
34 Correct 584 ms 7884 KB Output is correct
35 Correct 585 ms 7876 KB Output is correct
36 Correct 575 ms 7880 KB Output is correct
37 Correct 585 ms 7880 KB Output is correct
38 Correct 578 ms 7880 KB Output is correct
39 Correct 580 ms 7880 KB Output is correct
40 Correct 579 ms 7864 KB Output is correct
41 Correct 580 ms 7880 KB Output is correct
42 Correct 578 ms 7884 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 7100 KB Output is correct
2 Correct 616 ms 7108 KB Output is correct
3 Correct 627 ms 7116 KB Output is correct
4 Correct 591 ms 7120 KB Output is correct
5 Correct 603 ms 7120 KB Output is correct
6 Correct 612 ms 7100 KB Output is correct
7 Correct 626 ms 7116 KB Output is correct
8 Correct 594 ms 7100 KB Output is correct
9 Correct 609 ms 7120 KB Output is correct
10 Correct 635 ms 7116 KB Output is correct
11 Correct 589 ms 7112 KB Output is correct
12 Correct 593 ms 7116 KB Output is correct
13 Correct 596 ms 7116 KB Output is correct
14 Correct 597 ms 7100 KB Output is correct
15 Correct 601 ms 7116 KB Output is correct
16 Correct 605 ms 7104 KB Output is correct
17 Correct 612 ms 7112 KB Output is correct
18 Correct 609 ms 7112 KB Output is correct
19 Correct 597 ms 7104 KB Output is correct
20 Correct 610 ms 7108 KB Output is correct
21 Correct 615 ms 7104 KB Output is correct
22 Correct 609 ms 7112 KB Output is correct
23 Correct 577 ms 7880 KB Output is correct
24 Correct 589 ms 7896 KB Output is correct
25 Correct 586 ms 7880 KB Output is correct
26 Correct 589 ms 7880 KB Output is correct
27 Correct 583 ms 7876 KB Output is correct
28 Correct 579 ms 7880 KB Output is correct
29 Correct 579 ms 7880 KB Output is correct
30 Correct 580 ms 7888 KB Output is correct
31 Correct 580 ms 7880 KB Output is correct
32 Correct 578 ms 7884 KB Output is correct
33 Correct 582 ms 7856 KB Output is correct
34 Correct 584 ms 7884 KB Output is correct
35 Correct 585 ms 7876 KB Output is correct
36 Correct 575 ms 7880 KB Output is correct
37 Correct 585 ms 7880 KB Output is correct
38 Correct 578 ms 7880 KB Output is correct
39 Correct 580 ms 7880 KB Output is correct
40 Correct 579 ms 7864 KB Output is correct
41 Correct 580 ms 7880 KB Output is correct
42 Correct 578 ms 7884 KB Output is correct
43 Runtime error 593 ms 15056 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 7100 KB Output is correct
2 Correct 616 ms 7108 KB Output is correct
3 Correct 627 ms 7116 KB Output is correct
4 Correct 591 ms 7120 KB Output is correct
5 Correct 603 ms 7120 KB Output is correct
6 Correct 612 ms 7100 KB Output is correct
7 Correct 626 ms 7116 KB Output is correct
8 Correct 594 ms 7100 KB Output is correct
9 Correct 609 ms 7120 KB Output is correct
10 Correct 635 ms 7116 KB Output is correct
11 Correct 589 ms 7112 KB Output is correct
12 Correct 593 ms 7116 KB Output is correct
13 Correct 596 ms 7116 KB Output is correct
14 Correct 597 ms 7100 KB Output is correct
15 Correct 601 ms 7116 KB Output is correct
16 Correct 605 ms 7104 KB Output is correct
17 Correct 612 ms 7112 KB Output is correct
18 Correct 609 ms 7112 KB Output is correct
19 Correct 597 ms 7104 KB Output is correct
20 Correct 610 ms 7108 KB Output is correct
21 Correct 615 ms 7104 KB Output is correct
22 Correct 609 ms 7112 KB Output is correct
23 Correct 577 ms 7880 KB Output is correct
24 Correct 589 ms 7896 KB Output is correct
25 Correct 586 ms 7880 KB Output is correct
26 Correct 589 ms 7880 KB Output is correct
27 Correct 583 ms 7876 KB Output is correct
28 Correct 579 ms 7880 KB Output is correct
29 Correct 579 ms 7880 KB Output is correct
30 Correct 580 ms 7888 KB Output is correct
31 Correct 580 ms 7880 KB Output is correct
32 Correct 578 ms 7884 KB Output is correct
33 Correct 582 ms 7856 KB Output is correct
34 Correct 584 ms 7884 KB Output is correct
35 Correct 585 ms 7876 KB Output is correct
36 Correct 575 ms 7880 KB Output is correct
37 Correct 585 ms 7880 KB Output is correct
38 Correct 578 ms 7880 KB Output is correct
39 Correct 580 ms 7880 KB Output is correct
40 Correct 579 ms 7864 KB Output is correct
41 Correct 580 ms 7880 KB Output is correct
42 Correct 578 ms 7884 KB Output is correct
43 Runtime error 593 ms 15056 KB Execution killed with signal 11
44 Halted 0 ms 0 KB -