oj.uz

Submission #275985

# Submission time Handle Problem Language Result Execution time Memory
275985 2020-08-20T08:52:48 Z egekabas Cubeword (CEOI19_cubeword) C++14
50 / 100
 378 ms 28404 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
ll mod = 998244353;
ll ans = 0;
vector<string> a[11];
const ll n = 30;
ll cnt[70][70];
map<char, ll> mpp;
ll dp1[70][70][70];
ll dp2[70][70][70][70];
ll dp3[70][70][70];

void solve(int cur){
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            cnt[i][j] = 0;
    int sz = a[cur].size();
    for(int i = 0;  i < sz; ++i){
        string u = a[cur][i];
        reverse(all(u));
        a[cur].pb(u);
    }
    sort(all(a[cur]));
    a[cur].resize(unique(all(a[cur]))-a[cur].begin());
    for(auto u : a[cur]){
        cnt[mpp[u[0]]][mpp[u.back()]]++;
    }
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            for(int k = 0; k < n; ++k){
                dp1[i][j][k] = 0;
                for(int mid = 0; mid < n; ++mid){
                    dp1[i][j][k] += cnt[mid][i]*cnt[mid][j]%mod*cnt[mid][k]%mod;
                    if(dp1[i][j][k] >= mod)
                        dp1[i][j][k] -= mod;
                }
            }
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            for(int k = 0; k < n; ++k)
                for(int y = 0; y < n; ++y)
                    dp2[i][j][k][y] = dp1[i][j][k]*dp1[j][k][y]%mod;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            for(int y = 0; y < n; ++y){
                dp3[i][j][y] = 0;
                for(int k = 0; k < n; ++k){
                    dp3[i][j][y] += dp2[i][j][k][y]*dp1[i][k][y]%mod;
                    if(dp3[i][j][y] >= mod)
                        dp3[i][j][y] -= mod;
                }
            }
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            for(int y = 0; y < n; ++y)
                for(int fin = 0; fin < n; ++fin){
                    ans += dp3[i][j][y]*cnt[fin][i]%mod*cnt[fin][j]%mod*cnt[fin][y]%mod;
                    if(ans >= mod)
                        ans -= mod;
                }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    ll t;
    cin >> t;
    while(t--){
        string s;
        cin >> s;
        a[s.size()].pb(s);
    }
    ll cnt = 0;
    for(char i = 'a'; i <= 'z'; ++i)
        mpp[i] = cnt++;
    for(char i = 'A'; i <= 'Z'; ++i)
        mpp[i] = cnt++;
    for(char i = '0'; i <= '9'; ++i)
        mpp[i] = cnt++;
    for(ll i = 3; i <= 10; ++i)
        solve(i);
    cout << ans << '\n';
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 28268 KB Output is correct
2 Correct 352 ms 28364 KB Output is correct
3 Correct 350 ms 28360 KB Output is correct
4 Correct 353 ms 28216 KB Output is correct
5 Correct 350 ms 28256 KB Output is correct
6 Correct 351 ms 28376 KB Output is correct
7 Correct 378 ms 28404 KB Output is correct
8 Correct 370 ms 28296 KB Output is correct
9 Correct 354 ms 28304 KB Output is correct
10 Correct 360 ms 28272 KB Output is correct
11 Correct 371 ms 28232 KB Output is correct
12 Correct 360 ms 28400 KB Output is correct
13 Correct 360 ms 28236 KB Output is correct
14 Correct 359 ms 28400 KB Output is correct
15 Correct 348 ms 28388 KB Output is correct
16 Correct 349 ms 28376 KB Output is correct
17 Correct 355 ms 28212 KB Output is correct
18 Correct 352 ms 28324 KB Output is correct
19 Correct 369 ms 28264 KB Output is correct
20 Correct 359 ms 28292 KB Output is correct
21 Correct 359 ms 28180 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 28268 KB Output is correct
2 Correct 352 ms 28364 KB Output is correct
3 Correct 350 ms 28360 KB Output is correct
4 Correct 353 ms 28216 KB Output is correct
5 Correct 350 ms 28256 KB Output is correct
6 Correct 351 ms 28376 KB Output is correct
7 Correct 378 ms 28404 KB Output is correct
8 Correct 370 ms 28296 KB Output is correct
9 Correct 354 ms 28304 KB Output is correct
10 Correct 360 ms 28272 KB Output is correct
11 Correct 371 ms 28232 KB Output is correct
12 Correct 360 ms 28400 KB Output is correct
13 Correct 360 ms 28236 KB Output is correct
14 Correct 359 ms 28400 KB Output is correct
15 Correct 348 ms 28388 KB Output is correct
16 Correct 349 ms 28376 KB Output is correct
17 Correct 355 ms 28212 KB Output is correct
18 Correct 352 ms 28324 KB Output is correct
19 Correct 369 ms 28264 KB Output is correct
20 Correct 359 ms 28292 KB Output is correct
21 Correct 359 ms 28180 KB Output is correct
22 Correct 353 ms 27484 KB Output is correct
23 Correct 348 ms 27352 KB Output is correct
24 Correct 352 ms 27580 KB Output is correct
25 Correct 359 ms 27208 KB Output is correct
26 Correct 354 ms 27224 KB Output is correct
27 Correct 353 ms 27604 KB Output is correct
28 Correct 350 ms 27252 KB Output is correct
29 Correct 354 ms 27304 KB Output is correct
30 Correct 361 ms 27268 KB Output is correct
31 Correct 354 ms 27216 KB Output is correct
32 Correct 359 ms 27116 KB Output is correct
33 Correct 351 ms 27356 KB Output is correct
34 Correct 368 ms 27192 KB Output is correct
35 Correct 353 ms 27288 KB Output is correct
36 Correct 372 ms 27128 KB Output is correct
37 Correct 362 ms 27224 KB Output is correct
38 Correct 350 ms 27208 KB Output is correct
39 Correct 368 ms 27184 KB Output is correct
40 Correct 354 ms 27392 KB Output is correct
41 Correct 364 ms 27188 KB Output is correct
42 Correct 352 ms 27168 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 28268 KB Output is correct
2 Correct 352 ms 28364 KB Output is correct
3 Correct 350 ms 28360 KB Output is correct
4 Correct 353 ms 28216 KB Output is correct
5 Correct 350 ms 28256 KB Output is correct
6 Correct 351 ms 28376 KB Output is correct
7 Correct 378 ms 28404 KB Output is correct
8 Correct 370 ms 28296 KB Output is correct
9 Correct 354 ms 28304 KB Output is correct
10 Correct 360 ms 28272 KB Output is correct
11 Correct 371 ms 28232 KB Output is correct
12 Correct 360 ms 28400 KB Output is correct
13 Correct 360 ms 28236 KB Output is correct
14 Correct 359 ms 28400 KB Output is correct
15 Correct 348 ms 28388 KB Output is correct
16 Correct 349 ms 28376 KB Output is correct
17 Correct 355 ms 28212 KB Output is correct
18 Correct 352 ms 28324 KB Output is correct
19 Correct 369 ms 28264 KB Output is correct
20 Correct 359 ms 28292 KB Output is correct
21 Correct 359 ms 28180 KB Output is correct
22 Correct 353 ms 27484 KB Output is correct
23 Correct 348 ms 27352 KB Output is correct
24 Correct 352 ms 27580 KB Output is correct
25 Correct 359 ms 27208 KB Output is correct
26 Correct 354 ms 27224 KB Output is correct
27 Correct 353 ms 27604 KB Output is correct
28 Correct 350 ms 27252 KB Output is correct
29 Correct 354 ms 27304 KB Output is correct
30 Correct 361 ms 27268 KB Output is correct
31 Correct 354 ms 27216 KB Output is correct
32 Correct 359 ms 27116 KB Output is correct
33 Correct 351 ms 27356 KB Output is correct
34 Correct 368 ms 27192 KB Output is correct
35 Correct 353 ms 27288 KB Output is correct
36 Correct 372 ms 27128 KB Output is correct
37 Correct 362 ms 27224 KB Output is correct
38 Correct 350 ms 27208 KB Output is correct
39 Correct 368 ms 27184 KB Output is correct
40 Correct 354 ms 27392 KB Output is correct
41 Correct 364 ms 27188 KB Output is correct
42 Correct 352 ms 27168 KB Output is correct
43 Incorrect 356 ms 27604 KB Output isn't correct
44 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 28268 KB Output is correct
2 Correct 352 ms 28364 KB Output is correct
3 Correct 350 ms 28360 KB Output is correct
4 Correct 353 ms 28216 KB Output is correct
5 Correct 350 ms 28256 KB Output is correct
6 Correct 351 ms 28376 KB Output is correct
7 Correct 378 ms 28404 KB Output is correct
8 Correct 370 ms 28296 KB Output is correct
9 Correct 354 ms 28304 KB Output is correct
10 Correct 360 ms 28272 KB Output is correct
11 Correct 371 ms 28232 KB Output is correct
12 Correct 360 ms 28400 KB Output is correct
13 Correct 360 ms 28236 KB Output is correct
14 Correct 359 ms 28400 KB Output is correct
15 Correct 348 ms 28388 KB Output is correct
16 Correct 349 ms 28376 KB Output is correct
17 Correct 355 ms 28212 KB Output is correct
18 Correct 352 ms 28324 KB Output is correct
19 Correct 369 ms 28264 KB Output is correct
20 Correct 359 ms 28292 KB Output is correct
21 Correct 359 ms 28180 KB Output is correct
22 Correct 353 ms 27484 KB Output is correct
23 Correct 348 ms 27352 KB Output is correct
24 Correct 352 ms 27580 KB Output is correct
25 Correct 359 ms 27208 KB Output is correct
26 Correct 354 ms 27224 KB Output is correct
27 Correct 353 ms 27604 KB Output is correct
28 Correct 350 ms 27252 KB Output is correct
29 Correct 354 ms 27304 KB Output is correct
30 Correct 361 ms 27268 KB Output is correct
31 Correct 354 ms 27216 KB Output is correct
32 Correct 359 ms 27116 KB Output is correct
33 Correct 351 ms 27356 KB Output is correct
34 Correct 368 ms 27192 KB Output is correct
35 Correct 353 ms 27288 KB Output is correct
36 Correct 372 ms 27128 KB Output is correct
37 Correct 362 ms 27224 KB Output is correct
38 Correct 350 ms 27208 KB Output is correct
39 Correct 368 ms 27184 KB Output is correct
40 Correct 354 ms 27392 KB Output is correct
41 Correct 364 ms 27188 KB Output is correct
42 Correct 352 ms 27168 KB Output is correct
43 Incorrect 356 ms 27604 KB Output isn't correct
44 Halted 0 ms 0 KB -