oj.uz

Submission #752156

# Submission time Handle Problem Language Result Execution time Memory
752156 2023-06-02T11:24:46 Z Sam_a17 Cubeword (CEOI19_cubeword) C++17
84 / 100
 1100 ms 9024 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt(x) __builtin_popcount(x)
 
#define pb push_back
#define popf pop_front
#define popb pop_back
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(unordered_map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if (str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const long long mod = 998244353;
int n;
vector<string> vec[20];
 
long long add(long long a, long long b) {
  a += b;
  if(a > mod) {
    a -= mod;
  }
  return a;
}
 
long long mult(long long a, long long b) {
  return (a * b) % mod;
}
 
long long sub(long long a, long long b) {
  return (a - b + 2 * mod) % mod;
}
 
long long dp[62][62][62];
 
unordered_map<char, int> mp;
 
long long q[62][62];
int m = 61;
 
long long answ = 0;
 
void solve(int len) {
  memset(dp, 0, sizeof(dp));
  memset(q, 0, sizeof(q));
  
  for(auto i: vec[len]) {
    int first = mp[i[0]];
    int last = mp[i[len - 1]];
 
    q[first][last]++;
  }
 
  for(int start = 0; start <= m; start++) {
    for(int i = 0; i <= m; i++) {
      for(int j = 0; j <= m; j++) {
        for(int k = 0; k <= m; k++) {
          long long get = mult(q[start][i], mult(q[start][j], q[start][k]));
          dp[i][j][k] = add(dp[i][j][k], get);
        }
      }
    }
  }
 
  for(int i = 0; i <= m; i++) {
    for(int j = 0; j <= m; j++) {
      for(int k = 0; k <= m; k++) {
        if(!dp[i][j][k]) continue;
        
        for(int e = 0; e <= m; e++) {
          if(!dp[i][j][e]) continue;
          long long pt = mult(dp[i][j][e], dp[i][j][k]);
          pt = mult(pt, dp[j][e][k]);
          pt = mult(pt, dp[i][e][k]);
          answ = add(answ, pt);
        }
      }
    }
  }
}
 
void solve_() {
  cin >> n;
 
  for(int i = 1; i <= n; i++) {
    string s; cin >> s;
    vec[sz(s)].push_back(s);
    reverse(all(s));
    vec[sz(s)].push_back(s);
  }
 
 
  mp.reserve(1000);
 
  for(char i = 'a'; i <= 'z'; i++) {
    mp[i] = i - 'a';
  }
 
  for(char i = 'A'; i <= 'Z'; i++) {
    mp[i] = 26 + (i - 'A');
  }
 
  for(char i = '0'; i <= '9'; i++) {
    mp[i] = 52 + (i - '0');
  }
 
  for(int i = 3; i <= 10; i++) {
    sort(all(vec[i]));
    uniq(vec[i]);
    solve(i);
  }
 
  cout << answ << '\n';
}
 
int main() {
  setIO();
 
  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

cubeword.cpp: In function 'void setIO(std::string)':
cubeword.cpp:66:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cubeword.cpp:67:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 8824 KB Output is correct
2 Correct 699 ms 8864 KB Output is correct
3 Correct 602 ms 8780 KB Output is correct
4 Correct 585 ms 8888 KB Output is correct
5 Correct 549 ms 8872 KB Output is correct
6 Correct 624 ms 9024 KB Output is correct
7 Correct 661 ms 8848 KB Output is correct
8 Correct 599 ms 8780 KB Output is correct
9 Correct 659 ms 8852 KB Output is correct
10 Correct 608 ms 8888 KB Output is correct
11 Correct 685 ms 8964 KB Output is correct
12 Correct 622 ms 8888 KB Output is correct
13 Correct 587 ms 8892 KB Output is correct
14 Correct 601 ms 8736 KB Output is correct
15 Correct 579 ms 8820 KB Output is correct
16 Correct 578 ms 8832 KB Output is correct
17 Correct 574 ms 8984 KB Output is correct
18 Correct 552 ms 8736 KB Output is correct
19 Correct 560 ms 8836 KB Output is correct
20 Correct 561 ms 8804 KB Output is correct
21 Correct 566 ms 8876 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 8824 KB Output is correct
2 Correct 699 ms 8864 KB Output is correct
3 Correct 602 ms 8780 KB Output is correct
4 Correct 585 ms 8888 KB Output is correct
5 Correct 549 ms 8872 KB Output is correct
6 Correct 624 ms 9024 KB Output is correct
7 Correct 661 ms 8848 KB Output is correct
8 Correct 599 ms 8780 KB Output is correct
9 Correct 659 ms 8852 KB Output is correct
10 Correct 608 ms 8888 KB Output is correct
11 Correct 685 ms 8964 KB Output is correct
12 Correct 622 ms 8888 KB Output is correct
13 Correct 587 ms 8892 KB Output is correct
14 Correct 601 ms 8736 KB Output is correct
15 Correct 579 ms 8820 KB Output is correct
16 Correct 578 ms 8832 KB Output is correct
17 Correct 574 ms 8984 KB Output is correct
18 Correct 552 ms 8736 KB Output is correct
19 Correct 560 ms 8836 KB Output is correct
20 Correct 561 ms 8804 KB Output is correct
21 Correct 566 ms 8876 KB Output is correct
22 Correct 566 ms 8536 KB Output is correct
23 Correct 556 ms 8632 KB Output is correct
24 Correct 553 ms 8724 KB Output is correct
25 Correct 618 ms 8832 KB Output is correct
26 Correct 582 ms 8696 KB Output is correct
27 Correct 581 ms 8864 KB Output is correct
28 Correct 565 ms 8628 KB Output is correct
29 Correct 573 ms 8636 KB Output is correct
30 Correct 562 ms 8716 KB Output is correct
31 Correct 568 ms 8632 KB Output is correct
32 Correct 586 ms 8624 KB Output is correct
33 Correct 569 ms 8640 KB Output is correct
34 Correct 550 ms 8728 KB Output is correct
35 Correct 551 ms 8860 KB Output is correct
36 Correct 564 ms 8736 KB Output is correct
37 Correct 579 ms 8632 KB Output is correct
38 Correct 554 ms 8784 KB Output is correct
39 Correct 566 ms 8768 KB Output is correct
40 Correct 592 ms 8696 KB Output is correct
41 Correct 546 ms 8924 KB Output is correct
42 Correct 577 ms 8648 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 8824 KB Output is correct
2 Correct 699 ms 8864 KB Output is correct
3 Correct 602 ms 8780 KB Output is correct
4 Correct 585 ms 8888 KB Output is correct
5 Correct 549 ms 8872 KB Output is correct
6 Correct 624 ms 9024 KB Output is correct
7 Correct 661 ms 8848 KB Output is correct
8 Correct 599 ms 8780 KB Output is correct
9 Correct 659 ms 8852 KB Output is correct
10 Correct 608 ms 8888 KB Output is correct
11 Correct 685 ms 8964 KB Output is correct
12 Correct 622 ms 8888 KB Output is correct
13 Correct 587 ms 8892 KB Output is correct
14 Correct 601 ms 8736 KB Output is correct
15 Correct 579 ms 8820 KB Output is correct
16 Correct 578 ms 8832 KB Output is correct
17 Correct 574 ms 8984 KB Output is correct
18 Correct 552 ms 8736 KB Output is correct
19 Correct 560 ms 8836 KB Output is correct
20 Correct 561 ms 8804 KB Output is correct
21 Correct 566 ms 8876 KB Output is correct
22 Correct 566 ms 8536 KB Output is correct
23 Correct 556 ms 8632 KB Output is correct
24 Correct 553 ms 8724 KB Output is correct
25 Correct 618 ms 8832 KB Output is correct
26 Correct 582 ms 8696 KB Output is correct
27 Correct 581 ms 8864 KB Output is correct
28 Correct 565 ms 8628 KB Output is correct
29 Correct 573 ms 8636 KB Output is correct
30 Correct 562 ms 8716 KB Output is correct
31 Correct 568 ms 8632 KB Output is correct
32 Correct 586 ms 8624 KB Output is correct
33 Correct 569 ms 8640 KB Output is correct
34 Correct 550 ms 8728 KB Output is correct
35 Correct 551 ms 8860 KB Output is correct
36 Correct 564 ms 8736 KB Output is correct
37 Correct 579 ms 8632 KB Output is correct
38 Correct 554 ms 8784 KB Output is correct
39 Correct 566 ms 8768 KB Output is correct
40 Correct 592 ms 8696 KB Output is correct
41 Correct 546 ms 8924 KB Output is correct
42 Correct 577 ms 8648 KB Output is correct
43 Correct 630 ms 8636 KB Output is correct
44 Correct 622 ms 8636 KB Output is correct
45 Correct 621 ms 8632 KB Output is correct
46 Correct 617 ms 8636 KB Output is correct
47 Correct 646 ms 8684 KB Output is correct
48 Correct 618 ms 9016 KB Output is correct
49 Correct 632 ms 9016 KB Output is correct
50 Correct 633 ms 9024 KB Output is correct
51 Correct 637 ms 8884 KB Output is correct
52 Correct 605 ms 8588 KB Output is correct
53 Correct 634 ms 8576 KB Output is correct
54 Correct 623 ms 8900 KB Output is correct
55 Correct 611 ms 9016 KB Output is correct
56 Correct 610 ms 8640 KB Output is correct
57 Correct 628 ms 8892 KB Output is correct
58 Correct 616 ms 9016 KB Output is correct
59 Correct 651 ms 8900 KB Output is correct
60 Correct 660 ms 8936 KB Output is correct
61 Correct 637 ms 8632 KB Output is correct
62 Correct 841 ms 8908 KB Output is correct
63 Correct 657 ms 8892 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 8824 KB Output is correct
2 Correct 699 ms 8864 KB Output is correct
3 Correct 602 ms 8780 KB Output is correct
4 Correct 585 ms 8888 KB Output is correct
5 Correct 549 ms 8872 KB Output is correct
6 Correct 624 ms 9024 KB Output is correct
7 Correct 661 ms 8848 KB Output is correct
8 Correct 599 ms 8780 KB Output is correct
9 Correct 659 ms 8852 KB Output is correct
10 Correct 608 ms 8888 KB Output is correct
11 Correct 685 ms 8964 KB Output is correct
12 Correct 622 ms 8888 KB Output is correct
13 Correct 587 ms 8892 KB Output is correct
14 Correct 601 ms 8736 KB Output is correct
15 Correct 579 ms 8820 KB Output is correct
16 Correct 578 ms 8832 KB Output is correct
17 Correct 574 ms 8984 KB Output is correct
18 Correct 552 ms 8736 KB Output is correct
19 Correct 560 ms 8836 KB Output is correct
20 Correct 561 ms 8804 KB Output is correct
21 Correct 566 ms 8876 KB Output is correct
22 Correct 566 ms 8536 KB Output is correct
23 Correct 556 ms 8632 KB Output is correct
24 Correct 553 ms 8724 KB Output is correct
25 Correct 618 ms 8832 KB Output is correct
26 Correct 582 ms 8696 KB Output is correct
27 Correct 581 ms 8864 KB Output is correct
28 Correct 565 ms 8628 KB Output is correct
29 Correct 573 ms 8636 KB Output is correct
30 Correct 562 ms 8716 KB Output is correct
31 Correct 568 ms 8632 KB Output is correct
32 Correct 586 ms 8624 KB Output is correct
33 Correct 569 ms 8640 KB Output is correct
34 Correct 550 ms 8728 KB Output is correct
35 Correct 551 ms 8860 KB Output is correct
36 Correct 564 ms 8736 KB Output is correct
37 Correct 579 ms 8632 KB Output is correct
38 Correct 554 ms 8784 KB Output is correct
39 Correct 566 ms 8768 KB Output is correct
40 Correct 592 ms 8696 KB Output is correct
41 Correct 546 ms 8924 KB Output is correct
42 Correct 577 ms 8648 KB Output is correct
43 Correct 630 ms 8636 KB Output is correct
44 Correct 622 ms 8636 KB Output is correct
45 Correct 621 ms 8632 KB Output is correct
46 Correct 617 ms 8636 KB Output is correct
47 Correct 646 ms 8684 KB Output is correct
48 Correct 618 ms 9016 KB Output is correct
49 Correct 632 ms 9016 KB Output is correct
50 Correct 633 ms 9024 KB Output is correct
51 Correct 637 ms 8884 KB Output is correct
52 Correct 605 ms 8588 KB Output is correct
53 Correct 634 ms 8576 KB Output is correct
54 Correct 623 ms 8900 KB Output is correct
55 Correct 611 ms 9016 KB Output is correct
56 Correct 610 ms 8640 KB Output is correct
57 Correct 628 ms 8892 KB Output is correct
58 Correct 616 ms 9016 KB Output is correct
59 Correct 651 ms 8900 KB Output is correct
60 Correct 660 ms 8936 KB Output is correct
61 Correct 637 ms 8632 KB Output is correct
62 Correct 841 ms 8908 KB Output is correct
63 Correct 657 ms 8892 KB Output is correct
64 Execution timed out 1141 ms 8880 KB Time limit exceeded
65 Halted 0 ms 0 KB -