oj.uz

Submission #597149

# Submission time Handle Problem Language Result Execution time Memory
597149 2022-07-15T15:31:22 Z Valaki2 Cubeword (CEOI19_cubeword) C++14
21 / 100
 954 ms 7380 KB 
#include <bits/stdc++.h>
using namespace std;

#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 = 6;

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 try_scenario() {
    int res = 1;
    for(pii p : neighbours) {
        int coeff = combinations[len][corners[p.fi]][corners[p.se]];
        if(coeff == 0) {
            return 0;
        }
        res = (res * coeff) % mod;
    }
    return res;
}

void backtrack(int corner_id) {
    if(corner_id == 8) {
        ans = (ans + 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;
    v.assign(2 * n, "");
    for(int i = 0; i < n; i++) {
        cin >> v[i];
        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(8, -1);
    for(len = min_l; len <= max_l; len++) {
        backtrack(0);
    }
    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:36:1: warning: control reaches end of non-void function [-Wreturn-type]
   36 | }
      | ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 819 ms 7352 KB Output is correct
2 Correct 830 ms 7352 KB Output is correct
3 Correct 841 ms 7380 KB Output is correct
4 Correct 954 ms 7348 KB Output is correct
5 Correct 812 ms 7352 KB Output is correct
6 Correct 788 ms 7372 KB Output is correct
7 Correct 798 ms 7380 KB Output is correct
8 Correct 902 ms 7380 KB Output is correct
9 Correct 791 ms 7380 KB Output is correct
10 Correct 762 ms 7380 KB Output is correct
11 Correct 789 ms 7352 KB Output is correct
12 Correct 797 ms 7380 KB Output is correct
13 Correct 799 ms 7344 KB Output is correct
14 Correct 880 ms 7348 KB Output is correct
15 Correct 818 ms 7380 KB Output is correct
16 Correct 845 ms 7348 KB Output is correct
17 Correct 852 ms 7352 KB Output is correct
18 Correct 813 ms 7356 KB Output is correct
19 Correct 798 ms 7380 KB Output is correct
20 Correct 800 ms 7380 KB Output is correct
21 Correct 883 ms 7380 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 819 ms 7352 KB Output is correct
2 Correct 830 ms 7352 KB Output is correct
3 Correct 841 ms 7380 KB Output is correct
4 Correct 954 ms 7348 KB Output is correct
5 Correct 812 ms 7352 KB Output is correct
6 Correct 788 ms 7372 KB Output is correct
7 Correct 798 ms 7380 KB Output is correct
8 Correct 902 ms 7380 KB Output is correct
9 Correct 791 ms 7380 KB Output is correct
10 Correct 762 ms 7380 KB Output is correct
11 Correct 789 ms 7352 KB Output is correct
12 Correct 797 ms 7380 KB Output is correct
13 Correct 799 ms 7344 KB Output is correct
14 Correct 880 ms 7348 KB Output is correct
15 Correct 818 ms 7380 KB Output is correct
16 Correct 845 ms 7348 KB Output is correct
17 Correct 852 ms 7352 KB Output is correct
18 Correct 813 ms 7356 KB Output is correct
19 Correct 798 ms 7380 KB Output is correct
20 Correct 800 ms 7380 KB Output is correct
21 Correct 883 ms 7380 KB Output is correct
22 Runtime error 850 ms 7244 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 819 ms 7352 KB Output is correct
2 Correct 830 ms 7352 KB Output is correct
3 Correct 841 ms 7380 KB Output is correct
4 Correct 954 ms 7348 KB Output is correct
5 Correct 812 ms 7352 KB Output is correct
6 Correct 788 ms 7372 KB Output is correct
7 Correct 798 ms 7380 KB Output is correct
8 Correct 902 ms 7380 KB Output is correct
9 Correct 791 ms 7380 KB Output is correct
10 Correct 762 ms 7380 KB Output is correct
11 Correct 789 ms 7352 KB Output is correct
12 Correct 797 ms 7380 KB Output is correct
13 Correct 799 ms 7344 KB Output is correct
14 Correct 880 ms 7348 KB Output is correct
15 Correct 818 ms 7380 KB Output is correct
16 Correct 845 ms 7348 KB Output is correct
17 Correct 852 ms 7352 KB Output is correct
18 Correct 813 ms 7356 KB Output is correct
19 Correct 798 ms 7380 KB Output is correct
20 Correct 800 ms 7380 KB Output is correct
21 Correct 883 ms 7380 KB Output is correct
22 Runtime error 850 ms 7244 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 819 ms 7352 KB Output is correct
2 Correct 830 ms 7352 KB Output is correct
3 Correct 841 ms 7380 KB Output is correct
4 Correct 954 ms 7348 KB Output is correct
5 Correct 812 ms 7352 KB Output is correct
6 Correct 788 ms 7372 KB Output is correct
7 Correct 798 ms 7380 KB Output is correct
8 Correct 902 ms 7380 KB Output is correct
9 Correct 791 ms 7380 KB Output is correct
10 Correct 762 ms 7380 KB Output is correct
11 Correct 789 ms 7352 KB Output is correct
12 Correct 797 ms 7380 KB Output is correct
13 Correct 799 ms 7344 KB Output is correct
14 Correct 880 ms 7348 KB Output is correct
15 Correct 818 ms 7380 KB Output is correct
16 Correct 845 ms 7348 KB Output is correct
17 Correct 852 ms 7352 KB Output is correct
18 Correct 813 ms 7356 KB Output is correct
19 Correct 798 ms 7380 KB Output is correct
20 Correct 800 ms 7380 KB Output is correct
21 Correct 883 ms 7380 KB Output is correct
22 Runtime error 850 ms 7244 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -