oj.uz

Submission #360036

# Submission time Handle Problem Language Result Execution time Memory
360036 2021-01-27T12:21:09 Z mohamedsobhi777 Cubeword (CEOI19_cubeword) C++14
84 / 100
 878 ms 11564 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define vvi vector<vi>
#define vvii vector<vii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define uni(_) unique(_)
#define lb lower_bound
#define ub upper_bound
#define si set<int>
#define ms multiset<int>
#define qi queue<int>
#define pq prioriry_queue<int>
#define mi map<int, int>
#define inc(i, l, r) for (int i = l; i <= r; i++)
#define dec(i, l, r) for (int i = l; i >= r; i--)

using lll = __int128;
using ll = long long;
using ld = long double;

const int N = 1e5 + 7;
const ll mod = 998244353;
const ll inf = 2e18;

auto ra = [] {char *p = new char ; delete p ; return ll(p) ; };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (ra() | 1));
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> os;

int n;

int id(char c)
{
       if (c >= 'a' && c <= 'z')
              return c - 'a';
       if (c >= 'A' && c <= 'Z')
              return 26 + c - 'A';
       return 52 + c - '0';
}

const int S = 52;
int fr[S][S];
ll D[S][S][S];
ll ans;
vector<string> gbl[N];
int vis[S][S][S];

void solve(int ix)
{
       memset(D, 0, sizeof D);
       int z = sz(gbl[ix]);
       inc(a, 0, S - 1) inc(b, 0, S - 1) inc(c, 0, S - 1) inc(d, 0, S - 1)
       {
              D[b][c][d] += 1ll * fr[a][b] * fr[a][c] % mod * fr[a][d] % mod;
              D[b][c][d] %= mod;
       }

       inc(a, 0, S - 1) inc(b, 0, S - 1) inc(c, 0, S - 1) inc(d, 0, S - 1)
       {
              ans += 1ll * D[a][b][c] * D[a][b][d] % mod * D[b][c][d] % mod * D[a][c][d] % mod;
              ans %= mod;
       }
}

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif

       cin >> n;
       vector<string> vec;
       for (int i = 0; i < n; ++i)
       {
              string st, ts;
              cin >> st;
              ts = st;
              reverse(all(ts));
              gbl[sz(st)].pb(ts), gbl[sz(st)].pb(st);
       }
       for (int i = 3; i <= 10; ++i)
       {
              sort(all(gbl[i]));
              gbl[i].erase(unique(all(gbl[i])), gbl[i].end());
              for (int a = 0; a < S; ++a)
              {
                     for (int b = 0; b < S; ++b)
                     {
                            fr[a][b] = 0;
                     }
              }
              for (auto &u : gbl[i])
                     fr[id(u[0])][id(u[sz(u) - 1])]++;
              solve(i);
       }
       cout << ans;
       return 0;
}

Compilation message

cubeword.cpp: In function 'void solve(int)':
cubeword.cpp:71:12: warning: unused variable 'z' [-Wunused-variable]
   71 |        int z = sz(gbl[ix]);
      |            ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 840 ms 10496 KB Output is correct
2 Correct 806 ms 11328 KB Output is correct
3 Correct 810 ms 11320 KB Output is correct
4 Correct 818 ms 11416 KB Output is correct
5 Correct 878 ms 11360 KB Output is correct
6 Correct 805 ms 11564 KB Output is correct
7 Correct 847 ms 11284 KB Output is correct
8 Correct 838 ms 11316 KB Output is correct
9 Correct 803 ms 11380 KB Output is correct
10 Correct 803 ms 11416 KB Output is correct
11 Correct 867 ms 11420 KB Output is correct
12 Correct 833 ms 11424 KB Output is correct
13 Correct 800 ms 11420 KB Output is correct
14 Correct 828 ms 11264 KB Output is correct
15 Correct 823 ms 11284 KB Output is correct
16 Correct 819 ms 11360 KB Output is correct
17 Correct 799 ms 11384 KB Output is correct
18 Correct 851 ms 11268 KB Output is correct
19 Correct 814 ms 11480 KB Output is correct
20 Correct 810 ms 11384 KB Output is correct
21 Correct 812 ms 11408 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 840 ms 10496 KB Output is correct
2 Correct 806 ms 11328 KB Output is correct
3 Correct 810 ms 11320 KB Output is correct
4 Correct 818 ms 11416 KB Output is correct
5 Correct 878 ms 11360 KB Output is correct
6 Correct 805 ms 11564 KB Output is correct
7 Correct 847 ms 11284 KB Output is correct
8 Correct 838 ms 11316 KB Output is correct
9 Correct 803 ms 11380 KB Output is correct
10 Correct 803 ms 11416 KB Output is correct
11 Correct 867 ms 11420 KB Output is correct
12 Correct 833 ms 11424 KB Output is correct
13 Correct 800 ms 11420 KB Output is correct
14 Correct 828 ms 11264 KB Output is correct
15 Correct 823 ms 11284 KB Output is correct
16 Correct 819 ms 11360 KB Output is correct
17 Correct 799 ms 11384 KB Output is correct
18 Correct 851 ms 11268 KB Output is correct
19 Correct 814 ms 11480 KB Output is correct
20 Correct 810 ms 11384 KB Output is correct
21 Correct 812 ms 11408 KB Output is correct
22 Correct 839 ms 10992 KB Output is correct
23 Correct 811 ms 11136 KB Output is correct
24 Correct 796 ms 11300 KB Output is correct
25 Correct 797 ms 11296 KB Output is correct
26 Correct 795 ms 11216 KB Output is correct
27 Correct 814 ms 11320 KB Output is correct
28 Correct 794 ms 11132 KB Output is correct
29 Correct 817 ms 11084 KB Output is correct
30 Correct 790 ms 11184 KB Output is correct
31 Correct 788 ms 11076 KB Output is correct
32 Correct 787 ms 10988 KB Output is correct
33 Correct 803 ms 11096 KB Output is correct
34 Correct 799 ms 11176 KB Output is correct
35 Correct 793 ms 11324 KB Output is correct
36 Correct 821 ms 11300 KB Output is correct
37 Correct 798 ms 11004 KB Output is correct
38 Correct 800 ms 11288 KB Output is correct
39 Correct 794 ms 11348 KB Output is correct
40 Correct 797 ms 11264 KB Output is correct
41 Correct 789 ms 11260 KB Output is correct
42 Correct 793 ms 11104 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 840 ms 10496 KB Output is correct
2 Correct 806 ms 11328 KB Output is correct
3 Correct 810 ms 11320 KB Output is correct
4 Correct 818 ms 11416 KB Output is correct
5 Correct 878 ms 11360 KB Output is correct
6 Correct 805 ms 11564 KB Output is correct
7 Correct 847 ms 11284 KB Output is correct
8 Correct 838 ms 11316 KB Output is correct
9 Correct 803 ms 11380 KB Output is correct
10 Correct 803 ms 11416 KB Output is correct
11 Correct 867 ms 11420 KB Output is correct
12 Correct 833 ms 11424 KB Output is correct
13 Correct 800 ms 11420 KB Output is correct
14 Correct 828 ms 11264 KB Output is correct
15 Correct 823 ms 11284 KB Output is correct
16 Correct 819 ms 11360 KB Output is correct
17 Correct 799 ms 11384 KB Output is correct
18 Correct 851 ms 11268 KB Output is correct
19 Correct 814 ms 11480 KB Output is correct
20 Correct 810 ms 11384 KB Output is correct
21 Correct 812 ms 11408 KB Output is correct
22 Correct 839 ms 10992 KB Output is correct
23 Correct 811 ms 11136 KB Output is correct
24 Correct 796 ms 11300 KB Output is correct
25 Correct 797 ms 11296 KB Output is correct
26 Correct 795 ms 11216 KB Output is correct
27 Correct 814 ms 11320 KB Output is correct
28 Correct 794 ms 11132 KB Output is correct
29 Correct 817 ms 11084 KB Output is correct
30 Correct 790 ms 11184 KB Output is correct
31 Correct 788 ms 11076 KB Output is correct
32 Correct 787 ms 10988 KB Output is correct
33 Correct 803 ms 11096 KB Output is correct
34 Correct 799 ms 11176 KB Output is correct
35 Correct 793 ms 11324 KB Output is correct
36 Correct 821 ms 11300 KB Output is correct
37 Correct 798 ms 11004 KB Output is correct
38 Correct 800 ms 11288 KB Output is correct
39 Correct 794 ms 11348 KB Output is correct
40 Correct 797 ms 11264 KB Output is correct
41 Correct 789 ms 11260 KB Output is correct
42 Correct 793 ms 11104 KB Output is correct
43 Correct 793 ms 10964 KB Output is correct
44 Correct 792 ms 11048 KB Output is correct
45 Correct 793 ms 11052 KB Output is correct
46 Correct 797 ms 11048 KB Output is correct
47 Correct 798 ms 11056 KB Output is correct
48 Correct 811 ms 11440 KB Output is correct
49 Correct 802 ms 11464 KB Output is correct
50 Correct 824 ms 11444 KB Output is correct
51 Correct 795 ms 11328 KB Output is correct
52 Correct 790 ms 11044 KB Output is correct
53 Correct 787 ms 11040 KB Output is correct
54 Correct 799 ms 11324 KB Output is correct
55 Correct 795 ms 11304 KB Output is correct
56 Correct 797 ms 11016 KB Output is correct
57 Correct 799 ms 11432 KB Output is correct
58 Correct 788 ms 11476 KB Output is correct
59 Correct 837 ms 11228 KB Output is correct
60 Correct 791 ms 11340 KB Output is correct
61 Correct 788 ms 11132 KB Output is correct
62 Correct 792 ms 11432 KB Output is correct
63 Correct 794 ms 11384 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 840 ms 10496 KB Output is correct
2 Correct 806 ms 11328 KB Output is correct
3 Correct 810 ms 11320 KB Output is correct
4 Correct 818 ms 11416 KB Output is correct
5 Correct 878 ms 11360 KB Output is correct
6 Correct 805 ms 11564 KB Output is correct
7 Correct 847 ms 11284 KB Output is correct
8 Correct 838 ms 11316 KB Output is correct
9 Correct 803 ms 11380 KB Output is correct
10 Correct 803 ms 11416 KB Output is correct
11 Correct 867 ms 11420 KB Output is correct
12 Correct 833 ms 11424 KB Output is correct
13 Correct 800 ms 11420 KB Output is correct
14 Correct 828 ms 11264 KB Output is correct
15 Correct 823 ms 11284 KB Output is correct
16 Correct 819 ms 11360 KB Output is correct
17 Correct 799 ms 11384 KB Output is correct
18 Correct 851 ms 11268 KB Output is correct
19 Correct 814 ms 11480 KB Output is correct
20 Correct 810 ms 11384 KB Output is correct
21 Correct 812 ms 11408 KB Output is correct
22 Correct 839 ms 10992 KB Output is correct
23 Correct 811 ms 11136 KB Output is correct
24 Correct 796 ms 11300 KB Output is correct
25 Correct 797 ms 11296 KB Output is correct
26 Correct 795 ms 11216 KB Output is correct
27 Correct 814 ms 11320 KB Output is correct
28 Correct 794 ms 11132 KB Output is correct
29 Correct 817 ms 11084 KB Output is correct
30 Correct 790 ms 11184 KB Output is correct
31 Correct 788 ms 11076 KB Output is correct
32 Correct 787 ms 10988 KB Output is correct
33 Correct 803 ms 11096 KB Output is correct
34 Correct 799 ms 11176 KB Output is correct
35 Correct 793 ms 11324 KB Output is correct
36 Correct 821 ms 11300 KB Output is correct
37 Correct 798 ms 11004 KB Output is correct
38 Correct 800 ms 11288 KB Output is correct
39 Correct 794 ms 11348 KB Output is correct
40 Correct 797 ms 11264 KB Output is correct
41 Correct 789 ms 11260 KB Output is correct
42 Correct 793 ms 11104 KB Output is correct
43 Correct 793 ms 10964 KB Output is correct
44 Correct 792 ms 11048 KB Output is correct
45 Correct 793 ms 11052 KB Output is correct
46 Correct 797 ms 11048 KB Output is correct
47 Correct 798 ms 11056 KB Output is correct
48 Correct 811 ms 11440 KB Output is correct
49 Correct 802 ms 11464 KB Output is correct
50 Correct 824 ms 11444 KB Output is correct
51 Correct 795 ms 11328 KB Output is correct
52 Correct 790 ms 11044 KB Output is correct
53 Correct 787 ms 11040 KB Output is correct
54 Correct 799 ms 11324 KB Output is correct
55 Correct 795 ms 11304 KB Output is correct
56 Correct 797 ms 11016 KB Output is correct
57 Correct 799 ms 11432 KB Output is correct
58 Correct 788 ms 11476 KB Output is correct
59 Correct 837 ms 11228 KB Output is correct
60 Correct 791 ms 11340 KB Output is correct
61 Correct 788 ms 11132 KB Output is correct
62 Correct 792 ms 11432 KB Output is correct
63 Correct 794 ms 11384 KB Output is correct
64 Incorrect 791 ms 11208 KB Output isn't correct
65 Halted 0 ms 0 KB -