oj.uz

Submission #949552

# Submission time Handle Problem Language Result Execution time Memory
949552 2024-03-19T10:35:39 Z gaga999 Cubeword (CEOI19_cubeword) C++17
100 / 100
 903 ms 25752 KB 
#include <cstdio>
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stdlib.h>
#include <cstring>
#include <string.h>
#include <string>
#include <sstream>
#include <assert.h>
#include <climits>
#include <sstream>
#include <numeric>
#include <time.h>
#include <limits.h>
#include <list>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <iomanip>
#include <complex>
#include <chrono>
#include <fstream>
#include <functional>
#include <unistd.h>
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt")
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define init(a, b) memset((a), (b), sizeof(a))
#define cpy(a, b) memcpy((a), (b), sizeof(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define size(x) (int)x.size()
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
typedef complex<double> cd;
const int M = 998244353;

// random_device rm;
// mt19937 rg(rm());
// default_random_engine rg(rm());
// uniform_int_distribution<int> rd(INT_MIN, INT_MAX);
// uniform_real_distribution<double> rd(0, M_PI);

void db() { cerr << "\n"; }
template <class T, class... U>
void db(T a, U... b) { cerr << a << " ", db(b...); }

inline char gc()
{
    const static int SZ = 1 << 16;
    static char buf[SZ], *p1, *p2;
    if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2))
        return -1;
    return *p1++;
}
void rd() {}
template <typename T, typename... U>
void rd(T &x, U &...y)
{
    x = 0;
    bool f = 0;
    char c = gc();
    while (!isdigit(c))
        f ^= !(c ^ 45), c = gc();
    while (isdigit(c))
        x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
    f && (x = -x), rd(y...);
}

template <typename T>
void prt(T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        prt(x / 10);
    putchar((x % 10) ^ 48);
}
int ct[8][62][62], dp[8][62][62][62];
bool ok[8];

inline int gv(char c)
{
    if (isdigit(c))
        return c - '0';
    if ('a' <= c && c <= 'z')
        return c - 'a' + 10;
    return c - 'A' + 36;
}

signed main()
{
    AC;
    int n;
    cin >> n;
    unordered_set<string> st[8][62][62];
    string s;
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        int ln = s.length() - 3;
        for (char &c : s)
            c = gv(c);
        ok[ln] = 1;
        st[ln][s.front()][s.back()].insert(s);
        reverse(iter(s));
        st[ln][s.front()][s.back()].insert(s);
    }
    for (int l = 0; l < 8; l++)
        for (int i = 0; i < 62; i++)
            for (int j = 0; j < 62; j++)
                ct[l][i][j] = size(st[l][i][j]);
    int ans = 0;
    for (int l = 0; l < 8; l++)
    {
        if (!ok[l])
            continue;
        for (int i = 0; i < 62; i++)
        {
            for (int a = 0; a < 62; a++)
            {
                if (!ct[l][i][a])
                    continue;
                for (int b = 0; b < 62; b++)
                {
                    if (!ct[l][i][b])
                        continue;
                    for (int c = 0; c < 62; c++)
                    {
                        (dp[l][a][b][c] += 1ll * ct[l][i][a] * ct[l][i][b] % M * ct[l][i][c] % M) %= M;
                    }
                }
            }
        }
        for (int i = 0; i < 62; i++)
        {
            for (int a = 0; a < 62; a++)
            {
                for (int b = 0; b < 62; b++)
                {
                    for (int c = 0; c < 62; c++)
                    {
                        ans = (1ll * dp[l][a][b][c] * dp[l][a][b][i] % M * dp[l][i][c][a] % M * dp[l][i][c][b] + ans) % M;
                    }
                }
            }
        }
    }
    cout << ans << '\n';
}

Compilation message

cubeword.cpp: In function 'int main()':
cubeword.cpp:138:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  138 |         st[ln][s.front()][s.back()].insert(s);
      |                ~~~~~~~^~
cubeword.cpp:138:33: warning: array subscript has type 'char' [-Wchar-subscripts]
  138 |         st[ln][s.front()][s.back()].insert(s);
      |                           ~~~~~~^~
cubeword.cpp:140:23: warning: array subscript has type 'char' [-Wchar-subscripts]
  140 |         st[ln][s.front()][s.back()].insert(s);
      |                ~~~~~~~^~
cubeword.cpp:140:33: warning: array subscript has type 'char' [-Wchar-subscripts]
  140 |         st[ln][s.front()][s.back()].insert(s);
      |                           ~~~~~~^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 15880 KB Output is correct
2 Correct 600 ms 15956 KB Output is correct
3 Correct 599 ms 16004 KB Output is correct
4 Correct 586 ms 15884 KB Output is correct
5 Correct 584 ms 15712 KB Output is correct
6 Correct 584 ms 15800 KB Output is correct
7 Correct 581 ms 15696 KB Output is correct
8 Correct 580 ms 15708 KB Output is correct
9 Correct 591 ms 15852 KB Output is correct
10 Correct 616 ms 15908 KB Output is correct
11 Correct 611 ms 15836 KB Output is correct
12 Correct 595 ms 15824 KB Output is correct
13 Correct 584 ms 15736 KB Output is correct
14 Correct 606 ms 16044 KB Output is correct
15 Correct 582 ms 15740 KB Output is correct
16 Correct 600 ms 15888 KB Output is correct
17 Correct 601 ms 15920 KB Output is correct
18 Correct 598 ms 15912 KB Output is correct
19 Correct 576 ms 15700 KB Output is correct
20 Correct 606 ms 15700 KB Output is correct
21 Correct 600 ms 15672 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 15880 KB Output is correct
2 Correct 600 ms 15956 KB Output is correct
3 Correct 599 ms 16004 KB Output is correct
4 Correct 586 ms 15884 KB Output is correct
5 Correct 584 ms 15712 KB Output is correct
6 Correct 584 ms 15800 KB Output is correct
7 Correct 581 ms 15696 KB Output is correct
8 Correct 580 ms 15708 KB Output is correct
9 Correct 591 ms 15852 KB Output is correct
10 Correct 616 ms 15908 KB Output is correct
11 Correct 611 ms 15836 KB Output is correct
12 Correct 595 ms 15824 KB Output is correct
13 Correct 584 ms 15736 KB Output is correct
14 Correct 606 ms 16044 KB Output is correct
15 Correct 582 ms 15740 KB Output is correct
16 Correct 600 ms 15888 KB Output is correct
17 Correct 601 ms 15920 KB Output is correct
18 Correct 598 ms 15912 KB Output is correct
19 Correct 576 ms 15700 KB Output is correct
20 Correct 606 ms 15700 KB Output is correct
21 Correct 600 ms 15672 KB Output is correct
22 Correct 596 ms 17608 KB Output is correct
23 Correct 618 ms 17436 KB Output is correct
24 Correct 602 ms 17456 KB Output is correct
25 Correct 598 ms 17208 KB Output is correct
26 Correct 627 ms 17316 KB Output is correct
27 Correct 594 ms 17236 KB Output is correct
28 Correct 623 ms 17200 KB Output is correct
29 Correct 617 ms 17328 KB Output is correct
30 Correct 600 ms 17360 KB Output is correct
31 Correct 595 ms 17368 KB Output is correct
32 Correct 594 ms 17356 KB Output is correct
33 Correct 601 ms 17236 KB Output is correct
34 Correct 587 ms 17448 KB Output is correct
35 Correct 586 ms 17220 KB Output is correct
36 Correct 603 ms 17448 KB Output is correct
37 Correct 596 ms 17488 KB Output is correct
38 Correct 616 ms 17328 KB Output is correct
39 Correct 587 ms 17236 KB Output is correct
40 Correct 597 ms 17236 KB Output is correct
41 Correct 593 ms 17232 KB Output is correct
42 Correct 599 ms 17492 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 15880 KB Output is correct
2 Correct 600 ms 15956 KB Output is correct
3 Correct 599 ms 16004 KB Output is correct
4 Correct 586 ms 15884 KB Output is correct
5 Correct 584 ms 15712 KB Output is correct
6 Correct 584 ms 15800 KB Output is correct
7 Correct 581 ms 15696 KB Output is correct
8 Correct 580 ms 15708 KB Output is correct
9 Correct 591 ms 15852 KB Output is correct
10 Correct 616 ms 15908 KB Output is correct
11 Correct 611 ms 15836 KB Output is correct
12 Correct 595 ms 15824 KB Output is correct
13 Correct 584 ms 15736 KB Output is correct
14 Correct 606 ms 16044 KB Output is correct
15 Correct 582 ms 15740 KB Output is correct
16 Correct 600 ms 15888 KB Output is correct
17 Correct 601 ms 15920 KB Output is correct
18 Correct 598 ms 15912 KB Output is correct
19 Correct 576 ms 15700 KB Output is correct
20 Correct 606 ms 15700 KB Output is correct
21 Correct 600 ms 15672 KB Output is correct
22 Correct 596 ms 17608 KB Output is correct
23 Correct 618 ms 17436 KB Output is correct
24 Correct 602 ms 17456 KB Output is correct
25 Correct 598 ms 17208 KB Output is correct
26 Correct 627 ms 17316 KB Output is correct
27 Correct 594 ms 17236 KB Output is correct
28 Correct 623 ms 17200 KB Output is correct
29 Correct 617 ms 17328 KB Output is correct
30 Correct 600 ms 17360 KB Output is correct
31 Correct 595 ms 17368 KB Output is correct
32 Correct 594 ms 17356 KB Output is correct
33 Correct 601 ms 17236 KB Output is correct
34 Correct 587 ms 17448 KB Output is correct
35 Correct 586 ms 17220 KB Output is correct
36 Correct 603 ms 17448 KB Output is correct
37 Correct 596 ms 17488 KB Output is correct
38 Correct 616 ms 17328 KB Output is correct
39 Correct 587 ms 17236 KB Output is correct
40 Correct 597 ms 17236 KB Output is correct
41 Correct 593 ms 17232 KB Output is correct
42 Correct 599 ms 17492 KB Output is correct
43 Correct 632 ms 20564 KB Output is correct
44 Correct 622 ms 20472 KB Output is correct
45 Correct 620 ms 20732 KB Output is correct
46 Correct 617 ms 20612 KB Output is correct
47 Correct 617 ms 20448 KB Output is correct
48 Correct 621 ms 20484 KB Output is correct
49 Correct 623 ms 20520 KB Output is correct
50 Correct 629 ms 20536 KB Output is correct
51 Correct 625 ms 20816 KB Output is correct
52 Correct 646 ms 20560 KB Output is correct
53 Correct 629 ms 20564 KB Output is correct
54 Correct 657 ms 20684 KB Output is correct
55 Correct 631 ms 20764 KB Output is correct
56 Correct 624 ms 20564 KB Output is correct
57 Correct 618 ms 20372 KB Output is correct
58 Correct 628 ms 20380 KB Output is correct
59 Correct 642 ms 20448 KB Output is correct
60 Correct 624 ms 20392 KB Output is correct
61 Correct 625 ms 20528 KB Output is correct
62 Correct 634 ms 20592 KB Output is correct
63 Correct 627 ms 20564 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 15880 KB Output is correct
2 Correct 600 ms 15956 KB Output is correct
3 Correct 599 ms 16004 KB Output is correct
4 Correct 586 ms 15884 KB Output is correct
5 Correct 584 ms 15712 KB Output is correct
6 Correct 584 ms 15800 KB Output is correct
7 Correct 581 ms 15696 KB Output is correct
8 Correct 580 ms 15708 KB Output is correct
9 Correct 591 ms 15852 KB Output is correct
10 Correct 616 ms 15908 KB Output is correct
11 Correct 611 ms 15836 KB Output is correct
12 Correct 595 ms 15824 KB Output is correct
13 Correct 584 ms 15736 KB Output is correct
14 Correct 606 ms 16044 KB Output is correct
15 Correct 582 ms 15740 KB Output is correct
16 Correct 600 ms 15888 KB Output is correct
17 Correct 601 ms 15920 KB Output is correct
18 Correct 598 ms 15912 KB Output is correct
19 Correct 576 ms 15700 KB Output is correct
20 Correct 606 ms 15700 KB Output is correct
21 Correct 600 ms 15672 KB Output is correct
22 Correct 596 ms 17608 KB Output is correct
23 Correct 618 ms 17436 KB Output is correct
24 Correct 602 ms 17456 KB Output is correct
25 Correct 598 ms 17208 KB Output is correct
26 Correct 627 ms 17316 KB Output is correct
27 Correct 594 ms 17236 KB Output is correct
28 Correct 623 ms 17200 KB Output is correct
29 Correct 617 ms 17328 KB Output is correct
30 Correct 600 ms 17360 KB Output is correct
31 Correct 595 ms 17368 KB Output is correct
32 Correct 594 ms 17356 KB Output is correct
33 Correct 601 ms 17236 KB Output is correct
34 Correct 587 ms 17448 KB Output is correct
35 Correct 586 ms 17220 KB Output is correct
36 Correct 603 ms 17448 KB Output is correct
37 Correct 596 ms 17488 KB Output is correct
38 Correct 616 ms 17328 KB Output is correct
39 Correct 587 ms 17236 KB Output is correct
40 Correct 597 ms 17236 KB Output is correct
41 Correct 593 ms 17232 KB Output is correct
42 Correct 599 ms 17492 KB Output is correct
43 Correct 632 ms 20564 KB Output is correct
44 Correct 622 ms 20472 KB Output is correct
45 Correct 620 ms 20732 KB Output is correct
46 Correct 617 ms 20612 KB Output is correct
47 Correct 617 ms 20448 KB Output is correct
48 Correct 621 ms 20484 KB Output is correct
49 Correct 623 ms 20520 KB Output is correct
50 Correct 629 ms 20536 KB Output is correct
51 Correct 625 ms 20816 KB Output is correct
52 Correct 646 ms 20560 KB Output is correct
53 Correct 629 ms 20564 KB Output is correct
54 Correct 657 ms 20684 KB Output is correct
55 Correct 631 ms 20764 KB Output is correct
56 Correct 624 ms 20564 KB Output is correct
57 Correct 618 ms 20372 KB Output is correct
58 Correct 628 ms 20380 KB Output is correct
59 Correct 642 ms 20448 KB Output is correct
60 Correct 624 ms 20392 KB Output is correct
61 Correct 625 ms 20528 KB Output is correct
62 Correct 634 ms 20592 KB Output is correct
63 Correct 627 ms 20564 KB Output is correct
64 Correct 890 ms 25428 KB Output is correct
65 Correct 895 ms 25400 KB Output is correct
66 Correct 860 ms 25412 KB Output is correct
67 Correct 877 ms 25588 KB Output is correct
68 Correct 875 ms 25684 KB Output is correct
69 Correct 893 ms 25748 KB Output is correct
70 Correct 894 ms 25752 KB Output is correct
71 Correct 882 ms 25652 KB Output is correct
72 Correct 882 ms 25632 KB Output is correct
73 Correct 859 ms 25648 KB Output is correct
74 Correct 893 ms 25608 KB Output is correct
75 Correct 903 ms 25580 KB Output is correct
76 Correct 871 ms 25568 KB Output is correct
77 Correct 857 ms 25672 KB Output is correct
78 Correct 859 ms 25564 KB Output is correct
79 Correct 881 ms 25424 KB Output is correct
80 Correct 855 ms 25680 KB Output is correct
81 Correct 876 ms 25420 KB Output is correct
82 Correct 871 ms 25644 KB Output is correct
83 Correct 861 ms 25424 KB Output is correct
84 Correct 857 ms 25436 KB Output is correct