oj.uz

Submission #947581

# Submission time Handle Problem Language Result Execution time Memory
947581 2024-03-16T13:43:56 Z GrindMachine Cubeword (CEOI19_cubeword) C++17
100 / 100
 808 ms 13348 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi
some codes (to understand the edi idea)

sum the answers over all lengths
how to calculate the ans for a fixed length?

key idea:
when the letters in some vertices are fixed, the #of cubes that satisfy the fixed letters can be quickly counted
which vertices to fix?

fix 4 vertices:
a = front bottom left
b = front top right
c = back bottom right
d = back top left

none of these vertices are adj to each other
look at the 4 unfixed vertices
each one is adjacent to 3 vertices, all of which are fixed
so an unfixed vertex can have any letter, but the words on the 3 edges need to end with the fixed letters
precompute f(a,b,c) = #of ordered triplets of words s.t all 3 words start with the same letter, but end with a,b,c respectively
this can be used to count the #of cubes satisfying the fixed letters in O(1)

for eg, look at the front bottom right vertex
it's adj to a,b,c
so ways to fill these edges = f(a,b,c)
similar argument holds for the other 3 unfixed vertices

at the end, the final formula looks like:
f(a,b,c)*f(a,b,d)*f(b,c,d)*f(a,c,d)

*/

const int MOD = 998244353;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    ll n; cin >> n;
    vector<string> a(n);
    rep(i,n) cin >> a[i];
    rep(i,n){
        auto s = a[i];
        reverse(all(s));
        a.pb(s);
    }

    sort(all(a));
    a.resize(unique(all(a))-a.begin());
    n = sz(a);

    vector<char> b;
    trav(s,a){
        trav(ch,s){
            b.pb(ch);
        }
    }

    sort(all(b));
    b.resize(unique(all(b))-b.begin());
    ll alpha = sz(b);

    ll cnt[15][alpha][alpha];
    memset(cnt,0,sizeof cnt);
    rep(i,n){
        auto &s = a[i];
        ll x = lower_bound(all(b),s[0])-b.begin();
        ll y = lower_bound(all(b),s.back())-b.begin();
        cnt[sz(s)][x][y]++;
    }

    ll f[alpha][alpha][alpha];
    ll ans = 0;

    for(int len = 3; len <= 10; ++len){
        memset(f,0,sizeof f);
        rep(first,alpha){
            rep(x,alpha){
                rep(y,alpha){
                    rep(z,alpha){
                        ll add = cnt[len][first][x]*cnt[len][first][y]*cnt[len][first][z];
                        f[x][y][z] = (f[x][y][z]+add)%MOD;
                    }
                }
            }
        }

        rep(w,alpha){
            rep(x,alpha){
                rep(y,alpha){
                    rep(z,alpha){
                        ll add = f[w][x][y]*f[w][x][z]%MOD*f[x][y][z]%MOD*f[w][y][z];
                        ans = (ans+add)%MOD;
                    }
                }
            }
        }
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 11540 KB Output is correct
2 Correct 100 ms 10804 KB Output is correct
3 Correct 100 ms 10804 KB Output is correct
4 Correct 100 ms 10804 KB Output is correct
5 Correct 103 ms 10764 KB Output is correct
6 Correct 108 ms 10808 KB Output is correct
7 Correct 103 ms 10980 KB Output is correct
8 Correct 100 ms 10812 KB Output is correct
9 Correct 113 ms 10804 KB Output is correct
10 Correct 100 ms 10776 KB Output is correct
11 Correct 100 ms 10776 KB Output is correct
12 Correct 99 ms 10776 KB Output is correct
13 Correct 105 ms 10892 KB Output is correct
14 Correct 100 ms 11028 KB Output is correct
15 Correct 114 ms 10900 KB Output is correct
16 Correct 101 ms 11072 KB Output is correct
17 Correct 106 ms 11152 KB Output is correct
18 Correct 101 ms 10896 KB Output is correct
19 Correct 100 ms 11028 KB Output is correct
20 Correct 101 ms 11028 KB Output is correct
21 Correct 102 ms 10948 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 11540 KB Output is correct
2 Correct 100 ms 10804 KB Output is correct
3 Correct 100 ms 10804 KB Output is correct
4 Correct 100 ms 10804 KB Output is correct
5 Correct 103 ms 10764 KB Output is correct
6 Correct 108 ms 10808 KB Output is correct
7 Correct 103 ms 10980 KB Output is correct
8 Correct 100 ms 10812 KB Output is correct
9 Correct 113 ms 10804 KB Output is correct
10 Correct 100 ms 10776 KB Output is correct
11 Correct 100 ms 10776 KB Output is correct
12 Correct 99 ms 10776 KB Output is correct
13 Correct 105 ms 10892 KB Output is correct
14 Correct 100 ms 11028 KB Output is correct
15 Correct 114 ms 10900 KB Output is correct
16 Correct 101 ms 11072 KB Output is correct
17 Correct 106 ms 11152 KB Output is correct
18 Correct 101 ms 10896 KB Output is correct
19 Correct 100 ms 11028 KB Output is correct
20 Correct 101 ms 11028 KB Output is correct
21 Correct 102 ms 10948 KB Output is correct
22 Correct 107 ms 10776 KB Output is correct
23 Correct 104 ms 10896 KB Output is correct
24 Correct 105 ms 10864 KB Output is correct
25 Correct 124 ms 10824 KB Output is correct
26 Correct 110 ms 10776 KB Output is correct
27 Correct 107 ms 10776 KB Output is correct
28 Correct 114 ms 10776 KB Output is correct
29 Correct 115 ms 11028 KB Output is correct
30 Correct 108 ms 10768 KB Output is correct
31 Correct 104 ms 10776 KB Output is correct
32 Correct 105 ms 10776 KB Output is correct
33 Correct 116 ms 11284 KB Output is correct
34 Correct 109 ms 10772 KB Output is correct
35 Correct 112 ms 10776 KB Output is correct
36 Correct 106 ms 10772 KB Output is correct
37 Correct 104 ms 10812 KB Output is correct
38 Correct 103 ms 10824 KB Output is correct
39 Correct 105 ms 10820 KB Output is correct
40 Correct 110 ms 10772 KB Output is correct
41 Correct 118 ms 11028 KB Output is correct
42 Correct 110 ms 10772 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 11540 KB Output is correct
2 Correct 100 ms 10804 KB Output is correct
3 Correct 100 ms 10804 KB Output is correct
4 Correct 100 ms 10804 KB Output is correct
5 Correct 103 ms 10764 KB Output is correct
6 Correct 108 ms 10808 KB Output is correct
7 Correct 103 ms 10980 KB Output is correct
8 Correct 100 ms 10812 KB Output is correct
9 Correct 113 ms 10804 KB Output is correct
10 Correct 100 ms 10776 KB Output is correct
11 Correct 100 ms 10776 KB Output is correct
12 Correct 99 ms 10776 KB Output is correct
13 Correct 105 ms 10892 KB Output is correct
14 Correct 100 ms 11028 KB Output is correct
15 Correct 114 ms 10900 KB Output is correct
16 Correct 101 ms 11072 KB Output is correct
17 Correct 106 ms 11152 KB Output is correct
18 Correct 101 ms 10896 KB Output is correct
19 Correct 100 ms 11028 KB Output is correct
20 Correct 101 ms 11028 KB Output is correct
21 Correct 102 ms 10948 KB Output is correct
22 Correct 107 ms 10776 KB Output is correct
23 Correct 104 ms 10896 KB Output is correct
24 Correct 105 ms 10864 KB Output is correct
25 Correct 124 ms 10824 KB Output is correct
26 Correct 110 ms 10776 KB Output is correct
27 Correct 107 ms 10776 KB Output is correct
28 Correct 114 ms 10776 KB Output is correct
29 Correct 115 ms 11028 KB Output is correct
30 Correct 108 ms 10768 KB Output is correct
31 Correct 104 ms 10776 KB Output is correct
32 Correct 105 ms 10776 KB Output is correct
33 Correct 116 ms 11284 KB Output is correct
34 Correct 109 ms 10772 KB Output is correct
35 Correct 112 ms 10776 KB Output is correct
36 Correct 106 ms 10772 KB Output is correct
37 Correct 104 ms 10812 KB Output is correct
38 Correct 103 ms 10824 KB Output is correct
39 Correct 105 ms 10820 KB Output is correct
40 Correct 110 ms 10772 KB Output is correct
41 Correct 118 ms 11028 KB Output is correct
42 Correct 110 ms 10772 KB Output is correct
43 Correct 161 ms 11064 KB Output is correct
44 Correct 157 ms 11028 KB Output is correct
45 Correct 155 ms 11028 KB Output is correct
46 Correct 161 ms 11032 KB Output is correct
47 Correct 154 ms 11028 KB Output is correct
48 Correct 159 ms 11056 KB Output is correct
49 Correct 161 ms 11024 KB Output is correct
50 Correct 155 ms 11032 KB Output is correct
51 Correct 165 ms 11292 KB Output is correct
52 Correct 154 ms 11028 KB Output is correct
53 Correct 159 ms 11032 KB Output is correct
54 Correct 157 ms 11056 KB Output is correct
55 Correct 174 ms 10920 KB Output is correct
56 Correct 153 ms 11036 KB Output is correct
57 Correct 155 ms 11228 KB Output is correct
58 Correct 155 ms 11028 KB Output is correct
59 Correct 155 ms 11044 KB Output is correct
60 Correct 157 ms 11032 KB Output is correct
61 Correct 160 ms 11028 KB Output is correct
62 Correct 154 ms 11040 KB Output is correct
63 Correct 152 ms 11028 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 11540 KB Output is correct
2 Correct 100 ms 10804 KB Output is correct
3 Correct 100 ms 10804 KB Output is correct
4 Correct 100 ms 10804 KB Output is correct
5 Correct 103 ms 10764 KB Output is correct
6 Correct 108 ms 10808 KB Output is correct
7 Correct 103 ms 10980 KB Output is correct
8 Correct 100 ms 10812 KB Output is correct
9 Correct 113 ms 10804 KB Output is correct
10 Correct 100 ms 10776 KB Output is correct
11 Correct 100 ms 10776 KB Output is correct
12 Correct 99 ms 10776 KB Output is correct
13 Correct 105 ms 10892 KB Output is correct
14 Correct 100 ms 11028 KB Output is correct
15 Correct 114 ms 10900 KB Output is correct
16 Correct 101 ms 11072 KB Output is correct
17 Correct 106 ms 11152 KB Output is correct
18 Correct 101 ms 10896 KB Output is correct
19 Correct 100 ms 11028 KB Output is correct
20 Correct 101 ms 11028 KB Output is correct
21 Correct 102 ms 10948 KB Output is correct
22 Correct 107 ms 10776 KB Output is correct
23 Correct 104 ms 10896 KB Output is correct
24 Correct 105 ms 10864 KB Output is correct
25 Correct 124 ms 10824 KB Output is correct
26 Correct 110 ms 10776 KB Output is correct
27 Correct 107 ms 10776 KB Output is correct
28 Correct 114 ms 10776 KB Output is correct
29 Correct 115 ms 11028 KB Output is correct
30 Correct 108 ms 10768 KB Output is correct
31 Correct 104 ms 10776 KB Output is correct
32 Correct 105 ms 10776 KB Output is correct
33 Correct 116 ms 11284 KB Output is correct
34 Correct 109 ms 10772 KB Output is correct
35 Correct 112 ms 10776 KB Output is correct
36 Correct 106 ms 10772 KB Output is correct
37 Correct 104 ms 10812 KB Output is correct
38 Correct 103 ms 10824 KB Output is correct
39 Correct 105 ms 10820 KB Output is correct
40 Correct 110 ms 10772 KB Output is correct
41 Correct 118 ms 11028 KB Output is correct
42 Correct 110 ms 10772 KB Output is correct
43 Correct 161 ms 11064 KB Output is correct
44 Correct 157 ms 11028 KB Output is correct
45 Correct 155 ms 11028 KB Output is correct
46 Correct 161 ms 11032 KB Output is correct
47 Correct 154 ms 11028 KB Output is correct
48 Correct 159 ms 11056 KB Output is correct
49 Correct 161 ms 11024 KB Output is correct
50 Correct 155 ms 11032 KB Output is correct
51 Correct 165 ms 11292 KB Output is correct
52 Correct 154 ms 11028 KB Output is correct
53 Correct 159 ms 11032 KB Output is correct
54 Correct 157 ms 11056 KB Output is correct
55 Correct 174 ms 10920 KB Output is correct
56 Correct 153 ms 11036 KB Output is correct
57 Correct 155 ms 11228 KB Output is correct
58 Correct 155 ms 11028 KB Output is correct
59 Correct 155 ms 11044 KB Output is correct
60 Correct 157 ms 11032 KB Output is correct
61 Correct 160 ms 11028 KB Output is correct
62 Correct 154 ms 11040 KB Output is correct
63 Correct 152 ms 11028 KB Output is correct
64 Correct 804 ms 13076 KB Output is correct
65 Correct 794 ms 13080 KB Output is correct
66 Correct 787 ms 12936 KB Output is correct
67 Correct 797 ms 12832 KB Output is correct
68 Correct 783 ms 12836 KB Output is correct
69 Correct 788 ms 13072 KB Output is correct
70 Correct 794 ms 13072 KB Output is correct
71 Correct 788 ms 13072 KB Output is correct
72 Correct 806 ms 13080 KB Output is correct
73 Correct 791 ms 13076 KB Output is correct
74 Correct 788 ms 13076 KB Output is correct
75 Correct 788 ms 13072 KB Output is correct
76 Correct 794 ms 13076 KB Output is correct
77 Correct 787 ms 13072 KB Output is correct
78 Correct 784 ms 13076 KB Output is correct
79 Correct 795 ms 13328 KB Output is correct
80 Correct 804 ms 12844 KB Output is correct
81 Correct 804 ms 13348 KB Output is correct
82 Correct 791 ms 13076 KB Output is correct
83 Correct 792 ms 13076 KB Output is correct
84 Correct 808 ms 12836 KB Output is correct