oj.uz

Submission #579169

# Submission time Handle Problem Language Result Execution time Memory
579169 2022-06-18T12:38:19 Z talant117408 Cubeword (CEOI19_cubeword) C++17
84 / 100
 472 ms 55904 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

const int mod = 998244353;

ll add(ll a, ll b) {
    return ((a + b) % mod + mod) % mod;
}

ll mult(ll a, ll b) {
    return ((a * b) % mod + mod) % mod;
}

int index(char ch) {
    if ('a' <= ch && ch <= 'p') return int(ch-'a');
    else return int(ch-'A')+16;
    //~ else return int(ch-'0')+52;
}

const int CH = 32;
ll ways[11][CH][CH], side[4][11][CH][CH][CH];

void solve() {
    int n;
    cin >> n;
    vector <string> v;
    set <string> st;
    
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        auto s2 = s;
        reverse(all(s2));
        int last = sz(st);
        st.insert(s2);
        if (last != sz(st)) {
            st.insert(s);
            v.pb(s);
        }
    }
    vector <int> used(11);
    for (auto to : v) {
        if (to[0] == to.back()) {
            auto to2 = to;
            reverse(all(to2));
            ways[sz(to)][index(to.back())][index(to.back())] += 1 + (to != to2);
        }
        else {
            ways[sz(to)][index(to[0])][index(to.back())]++;
            ways[sz(to)][index(to.back())][index(to[0])]++;
        }
        used[sz(to)] = 1;
    }
    for (int j = 3; j <= 10; j++) {
        if (used[j] == 0) continue;
        for (int j2 = 0; j2 < CH; j2++)
        for (int j3 = 0; j3 < CH; j3++)
        for (int j4 = 0; j4 < CH; j4++) 
        for (int j1 = 0; j1 < CH; j1++) 
        for (int k = 0; k < 4; k++) 
        side[k][j][j2][j3][j4] = add(side[k][j][j2][j3][j4], mult(mult(ways[j][j1][j2], ways[j][j1][j3]), ways[j][j1][j4]));
    }
    
    ll ans = 0;
    
    for (int j = 3; j <= 10; j++) {
        if (used[j] == 0) continue;
        for (int _1 = 0; _1 < CH; _1++)
        for (int _4 = 0; _4 < CH; _4++)
        for (int _6 = 0; _6 < CH; _6++)
        for (int _7 = 0; _7 < CH; _7++)
        ans = add(ans, mult(mult(side[0][j][_1][_4][_6], side[1][j][_1][_4][_7]), mult(side[2][j][_1][_6][_7], side[3][j][_4][_7][_6])));
    }
        
    cout << ans << endl;
}

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 25896 KB Output is correct
2 Correct 432 ms 26784 KB Output is correct
3 Correct 444 ms 26892 KB Output is correct
4 Correct 452 ms 26800 KB Output is correct
5 Correct 441 ms 26816 KB Output is correct
6 Correct 446 ms 26896 KB Output is correct
7 Correct 435 ms 26924 KB Output is correct
8 Correct 439 ms 26808 KB Output is correct
9 Correct 445 ms 26744 KB Output is correct
10 Correct 433 ms 26916 KB Output is correct
11 Correct 455 ms 26820 KB Output is correct
12 Correct 472 ms 26804 KB Output is correct
13 Correct 440 ms 26800 KB Output is correct
14 Correct 452 ms 26776 KB Output is correct
15 Correct 449 ms 26800 KB Output is correct
16 Correct 432 ms 26844 KB Output is correct
17 Correct 440 ms 26800 KB Output is correct
18 Correct 443 ms 26744 KB Output is correct
19 Correct 430 ms 26804 KB Output is correct
20 Correct 426 ms 26756 KB Output is correct
21 Correct 428 ms 26752 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 25896 KB Output is correct
2 Correct 432 ms 26784 KB Output is correct
3 Correct 444 ms 26892 KB Output is correct
4 Correct 452 ms 26800 KB Output is correct
5 Correct 441 ms 26816 KB Output is correct
6 Correct 446 ms 26896 KB Output is correct
7 Correct 435 ms 26924 KB Output is correct
8 Correct 439 ms 26808 KB Output is correct
9 Correct 445 ms 26744 KB Output is correct
10 Correct 433 ms 26916 KB Output is correct
11 Correct 455 ms 26820 KB Output is correct
12 Correct 472 ms 26804 KB Output is correct
13 Correct 440 ms 26800 KB Output is correct
14 Correct 452 ms 26776 KB Output is correct
15 Correct 449 ms 26800 KB Output is correct
16 Correct 432 ms 26844 KB Output is correct
17 Correct 440 ms 26800 KB Output is correct
18 Correct 443 ms 26744 KB Output is correct
19 Correct 430 ms 26804 KB Output is correct
20 Correct 426 ms 26756 KB Output is correct
21 Correct 428 ms 26752 KB Output is correct
22 Correct 434 ms 27628 KB Output is correct
23 Correct 444 ms 27524 KB Output is correct
24 Correct 436 ms 27548 KB Output is correct
25 Correct 422 ms 27520 KB Output is correct
26 Correct 436 ms 27520 KB Output is correct
27 Correct 444 ms 27576 KB Output is correct
28 Correct 438 ms 27508 KB Output is correct
29 Correct 436 ms 27516 KB Output is correct
30 Correct 439 ms 27504 KB Output is correct
31 Correct 441 ms 27548 KB Output is correct
32 Correct 424 ms 27552 KB Output is correct
33 Correct 428 ms 27568 KB Output is correct
34 Correct 426 ms 27484 KB Output is correct
35 Correct 430 ms 27436 KB Output is correct
36 Correct 438 ms 27520 KB Output is correct
37 Correct 428 ms 27528 KB Output is correct
38 Correct 430 ms 27568 KB Output is correct
39 Correct 431 ms 27548 KB Output is correct
40 Correct 430 ms 27564 KB Output is correct
41 Correct 428 ms 27476 KB Output is correct
42 Correct 431 ms 27632 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 25896 KB Output is correct
2 Correct 432 ms 26784 KB Output is correct
3 Correct 444 ms 26892 KB Output is correct
4 Correct 452 ms 26800 KB Output is correct
5 Correct 441 ms 26816 KB Output is correct
6 Correct 446 ms 26896 KB Output is correct
7 Correct 435 ms 26924 KB Output is correct
8 Correct 439 ms 26808 KB Output is correct
9 Correct 445 ms 26744 KB Output is correct
10 Correct 433 ms 26916 KB Output is correct
11 Correct 455 ms 26820 KB Output is correct
12 Correct 472 ms 26804 KB Output is correct
13 Correct 440 ms 26800 KB Output is correct
14 Correct 452 ms 26776 KB Output is correct
15 Correct 449 ms 26800 KB Output is correct
16 Correct 432 ms 26844 KB Output is correct
17 Correct 440 ms 26800 KB Output is correct
18 Correct 443 ms 26744 KB Output is correct
19 Correct 430 ms 26804 KB Output is correct
20 Correct 426 ms 26756 KB Output is correct
21 Correct 428 ms 26752 KB Output is correct
22 Correct 434 ms 27628 KB Output is correct
23 Correct 444 ms 27524 KB Output is correct
24 Correct 436 ms 27548 KB Output is correct
25 Correct 422 ms 27520 KB Output is correct
26 Correct 436 ms 27520 KB Output is correct
27 Correct 444 ms 27576 KB Output is correct
28 Correct 438 ms 27508 KB Output is correct
29 Correct 436 ms 27516 KB Output is correct
30 Correct 439 ms 27504 KB Output is correct
31 Correct 441 ms 27548 KB Output is correct
32 Correct 424 ms 27552 KB Output is correct
33 Correct 428 ms 27568 KB Output is correct
34 Correct 426 ms 27484 KB Output is correct
35 Correct 430 ms 27436 KB Output is correct
36 Correct 438 ms 27520 KB Output is correct
37 Correct 428 ms 27528 KB Output is correct
38 Correct 430 ms 27568 KB Output is correct
39 Correct 431 ms 27548 KB Output is correct
40 Correct 430 ms 27564 KB Output is correct
41 Correct 428 ms 27476 KB Output is correct
42 Correct 431 ms 27632 KB Output is correct
43 Correct 432 ms 27732 KB Output is correct
44 Correct 429 ms 27800 KB Output is correct
45 Correct 422 ms 27864 KB Output is correct
46 Correct 429 ms 27700 KB Output is correct
47 Correct 423 ms 27748 KB Output is correct
48 Correct 427 ms 27776 KB Output is correct
49 Correct 436 ms 27672 KB Output is correct
50 Correct 435 ms 27712 KB Output is correct
51 Correct 425 ms 27664 KB Output is correct
52 Correct 434 ms 27668 KB Output is correct
53 Correct 420 ms 27776 KB Output is correct
54 Correct 430 ms 27760 KB Output is correct
55 Correct 443 ms 27788 KB Output is correct
56 Correct 428 ms 27844 KB Output is correct
57 Correct 428 ms 27716 KB Output is correct
58 Correct 425 ms 27788 KB Output is correct
59 Correct 428 ms 27696 KB Output is correct
60 Correct 427 ms 27832 KB Output is correct
61 Correct 435 ms 27656 KB Output is correct
62 Correct 436 ms 27696 KB Output is correct
63 Correct 438 ms 27744 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 469 ms 25896 KB Output is correct
2 Correct 432 ms 26784 KB Output is correct
3 Correct 444 ms 26892 KB Output is correct
4 Correct 452 ms 26800 KB Output is correct
5 Correct 441 ms 26816 KB Output is correct
6 Correct 446 ms 26896 KB Output is correct
7 Correct 435 ms 26924 KB Output is correct
8 Correct 439 ms 26808 KB Output is correct
9 Correct 445 ms 26744 KB Output is correct
10 Correct 433 ms 26916 KB Output is correct
11 Correct 455 ms 26820 KB Output is correct
12 Correct 472 ms 26804 KB Output is correct
13 Correct 440 ms 26800 KB Output is correct
14 Correct 452 ms 26776 KB Output is correct
15 Correct 449 ms 26800 KB Output is correct
16 Correct 432 ms 26844 KB Output is correct
17 Correct 440 ms 26800 KB Output is correct
18 Correct 443 ms 26744 KB Output is correct
19 Correct 430 ms 26804 KB Output is correct
20 Correct 426 ms 26756 KB Output is correct
21 Correct 428 ms 26752 KB Output is correct
22 Correct 434 ms 27628 KB Output is correct
23 Correct 444 ms 27524 KB Output is correct
24 Correct 436 ms 27548 KB Output is correct
25 Correct 422 ms 27520 KB Output is correct
26 Correct 436 ms 27520 KB Output is correct
27 Correct 444 ms 27576 KB Output is correct
28 Correct 438 ms 27508 KB Output is correct
29 Correct 436 ms 27516 KB Output is correct
30 Correct 439 ms 27504 KB Output is correct
31 Correct 441 ms 27548 KB Output is correct
32 Correct 424 ms 27552 KB Output is correct
33 Correct 428 ms 27568 KB Output is correct
34 Correct 426 ms 27484 KB Output is correct
35 Correct 430 ms 27436 KB Output is correct
36 Correct 438 ms 27520 KB Output is correct
37 Correct 428 ms 27528 KB Output is correct
38 Correct 430 ms 27568 KB Output is correct
39 Correct 431 ms 27548 KB Output is correct
40 Correct 430 ms 27564 KB Output is correct
41 Correct 428 ms 27476 KB Output is correct
42 Correct 431 ms 27632 KB Output is correct
43 Correct 432 ms 27732 KB Output is correct
44 Correct 429 ms 27800 KB Output is correct
45 Correct 422 ms 27864 KB Output is correct
46 Correct 429 ms 27700 KB Output is correct
47 Correct 423 ms 27748 KB Output is correct
48 Correct 427 ms 27776 KB Output is correct
49 Correct 436 ms 27672 KB Output is correct
50 Correct 435 ms 27712 KB Output is correct
51 Correct 425 ms 27664 KB Output is correct
52 Correct 434 ms 27668 KB Output is correct
53 Correct 420 ms 27776 KB Output is correct
54 Correct 430 ms 27760 KB Output is correct
55 Correct 443 ms 27788 KB Output is correct
56 Correct 428 ms 27844 KB Output is correct
57 Correct 428 ms 27716 KB Output is correct
58 Correct 425 ms 27788 KB Output is correct
59 Correct 428 ms 27696 KB Output is correct
60 Correct 427 ms 27832 KB Output is correct
61 Correct 435 ms 27656 KB Output is correct
62 Correct 436 ms 27696 KB Output is correct
63 Correct 438 ms 27744 KB Output is correct
64 Runtime error 438 ms 55904 KB Execution killed with signal 11
65 Halted 0 ms 0 KB -