oj.uz

Submission #373210

# Submission time Handle Problem Language Result Execution time Memory
373210 2021-03-03T18:28:54 Z ACmachine Cubeword (CEOI19_cubeword) C++17
84 / 100
 985 ms 19764 KB 
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)

const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;

template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "[";  REP(i, U) out << v[i] << ", ";  out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}

template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }

const int mod = 998244353;
int main(){
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL); cout.tie(NULL);
 	const int alpha = 52;
    vector<int> cnv(150);
    REP(i, 26) cnv['a' + i] = i;
    REP(i, 26) {
        cnv['A' + i] = 26 + i;
    }
    REP(i, 10){
        cnv['0' + i] = 52 + i;
    }
    int n; cin >> n;
    vector<string> strings(n);
    cin >> strings;
    REP(i, n){
        string ns = strings[i];
        reverse(all(ns));
        strings.pb(ns);
    }
    sort(all(strings));
    strings.erase(unique(all(strings)), strings.end());
    ll D[alpha][alpha][alpha];
    ll cn[alpha][alpha];
    auto solve = [&](vector<string> &a){
        int nn = a.size();
        memset(D, 0, sizeof(D));
        memset(cn, 0, sizeof(cn));
        for(string x : a){
            int f = cnv[x[0]]; int s = cnv[x.back()];
            cn[f][s]++;
        }
        REP(i, alpha){
            REP(j, alpha){
                REP(k, alpha){
                    REP(g, alpha){
                        D[j][k][g] += (cn[i][j] * cn[i][k] * cn[i][g]) % mod;
                        D[j][k][g] %= mod;
                    }
                }
            }
        }
        ll res = 0;
        REP(a, alpha){
            REP(b, alpha){
                REP(c, alpha){
                    REP(d, alpha){
                        res += (((((D[a][d][c] * D[a][d][b]) % mod) * D[a][c][b]) % mod) * D[d][c][b]) % mod;
                        res %= mod;
                    }
                }
            }
        }
        return res;
    };
    vector<vector<string>> todo(11);
    REP(i, strings.size()) todo[strings[i].length()].pb(strings[i]);
    ll ans = 0;
    FOR(i, 3, 11, 1){
        if(todo[i].size() > 0)
            ans += solve(todo[i]);
        ans %= mod;
    }
    cout << ans << "\n";
    return 0;
}

Compilation message

cubeword.cpp: In lambda function:
cubeword.cpp:83:13: warning: unused variable 'nn' [-Wunused-variable]
   83 |         int nn = a.size();
      |             ^~
cubeword.cpp: In function 'int main()':
cubeword.cpp:19:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
cubeword.cpp:21:18: note: in expansion of macro 'FOR'
   21 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
cubeword.cpp:114:5: note: in expansion of macro 'REP'
  114 |     REP(i, strings.size()) todo[strings[i].length()].pb(strings[i]);
      |     ^~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 936 ms 18996 KB Output is correct
2 Correct 938 ms 18740 KB Output is correct
3 Correct 915 ms 18808 KB Output is correct
4 Correct 985 ms 18996 KB Output is correct
5 Correct 913 ms 18868 KB Output is correct
6 Correct 912 ms 19124 KB Output is correct
7 Correct 919 ms 19636 KB Output is correct
8 Correct 921 ms 19508 KB Output is correct
9 Correct 900 ms 19764 KB Output is correct
10 Correct 911 ms 19252 KB Output is correct
11 Correct 909 ms 18740 KB Output is correct
12 Correct 910 ms 19368 KB Output is correct
13 Correct 928 ms 19636 KB Output is correct
14 Correct 909 ms 19308 KB Output is correct
15 Correct 903 ms 18740 KB Output is correct
16 Correct 922 ms 18612 KB Output is correct
17 Correct 910 ms 18740 KB Output is correct
18 Correct 933 ms 18776 KB Output is correct
19 Correct 903 ms 18740 KB Output is correct
20 Correct 904 ms 19632 KB Output is correct
21 Correct 918 ms 19124 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 936 ms 18996 KB Output is correct
2 Correct 938 ms 18740 KB Output is correct
3 Correct 915 ms 18808 KB Output is correct
4 Correct 985 ms 18996 KB Output is correct
5 Correct 913 ms 18868 KB Output is correct
6 Correct 912 ms 19124 KB Output is correct
7 Correct 919 ms 19636 KB Output is correct
8 Correct 921 ms 19508 KB Output is correct
9 Correct 900 ms 19764 KB Output is correct
10 Correct 911 ms 19252 KB Output is correct
11 Correct 909 ms 18740 KB Output is correct
12 Correct 910 ms 19368 KB Output is correct
13 Correct 928 ms 19636 KB Output is correct
14 Correct 909 ms 19308 KB Output is correct
15 Correct 903 ms 18740 KB Output is correct
16 Correct 922 ms 18612 KB Output is correct
17 Correct 910 ms 18740 KB Output is correct
18 Correct 933 ms 18776 KB Output is correct
19 Correct 903 ms 18740 KB Output is correct
20 Correct 904 ms 19632 KB Output is correct
21 Correct 918 ms 19124 KB Output is correct
22 Correct 902 ms 16692 KB Output is correct
23 Correct 911 ms 17184 KB Output is correct
24 Correct 931 ms 16564 KB Output is correct
25 Correct 904 ms 16932 KB Output is correct
26 Correct 904 ms 16676 KB Output is correct
27 Correct 930 ms 17188 KB Output is correct
28 Correct 902 ms 16564 KB Output is correct
29 Correct 914 ms 17876 KB Output is correct
30 Correct 909 ms 16948 KB Output is correct
31 Correct 898 ms 16804 KB Output is correct
32 Correct 894 ms 16564 KB Output is correct
33 Correct 909 ms 17204 KB Output is correct
34 Correct 893 ms 17204 KB Output is correct
35 Correct 907 ms 16828 KB Output is correct
36 Correct 909 ms 17588 KB Output is correct
37 Correct 941 ms 17332 KB Output is correct
38 Correct 906 ms 16988 KB Output is correct
39 Correct 914 ms 16436 KB Output is correct
40 Correct 911 ms 16272 KB Output is correct
41 Correct 894 ms 16820 KB Output is correct
42 Correct 914 ms 16164 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 936 ms 18996 KB Output is correct
2 Correct 938 ms 18740 KB Output is correct
3 Correct 915 ms 18808 KB Output is correct
4 Correct 985 ms 18996 KB Output is correct
5 Correct 913 ms 18868 KB Output is correct
6 Correct 912 ms 19124 KB Output is correct
7 Correct 919 ms 19636 KB Output is correct
8 Correct 921 ms 19508 KB Output is correct
9 Correct 900 ms 19764 KB Output is correct
10 Correct 911 ms 19252 KB Output is correct
11 Correct 909 ms 18740 KB Output is correct
12 Correct 910 ms 19368 KB Output is correct
13 Correct 928 ms 19636 KB Output is correct
14 Correct 909 ms 19308 KB Output is correct
15 Correct 903 ms 18740 KB Output is correct
16 Correct 922 ms 18612 KB Output is correct
17 Correct 910 ms 18740 KB Output is correct
18 Correct 933 ms 18776 KB Output is correct
19 Correct 903 ms 18740 KB Output is correct
20 Correct 904 ms 19632 KB Output is correct
21 Correct 918 ms 19124 KB Output is correct
22 Correct 902 ms 16692 KB Output is correct
23 Correct 911 ms 17184 KB Output is correct
24 Correct 931 ms 16564 KB Output is correct
25 Correct 904 ms 16932 KB Output is correct
26 Correct 904 ms 16676 KB Output is correct
27 Correct 930 ms 17188 KB Output is correct
28 Correct 902 ms 16564 KB Output is correct
29 Correct 914 ms 17876 KB Output is correct
30 Correct 909 ms 16948 KB Output is correct
31 Correct 898 ms 16804 KB Output is correct
32 Correct 894 ms 16564 KB Output is correct
33 Correct 909 ms 17204 KB Output is correct
34 Correct 893 ms 17204 KB Output is correct
35 Correct 907 ms 16828 KB Output is correct
36 Correct 909 ms 17588 KB Output is correct
37 Correct 941 ms 17332 KB Output is correct
38 Correct 906 ms 16988 KB Output is correct
39 Correct 914 ms 16436 KB Output is correct
40 Correct 911 ms 16272 KB Output is correct
41 Correct 894 ms 16820 KB Output is correct
42 Correct 914 ms 16164 KB Output is correct
43 Correct 911 ms 17424 KB Output is correct
44 Correct 924 ms 17504 KB Output is correct
45 Correct 910 ms 17460 KB Output is correct
46 Correct 909 ms 17588 KB Output is correct
47 Correct 942 ms 17460 KB Output is correct
48 Correct 917 ms 17036 KB Output is correct
49 Correct 897 ms 17284 KB Output is correct
50 Correct 912 ms 17332 KB Output is correct
51 Correct 892 ms 16948 KB Output is correct
52 Correct 902 ms 17588 KB Output is correct
53 Correct 906 ms 16820 KB Output is correct
54 Correct 904 ms 17476 KB Output is correct
55 Correct 897 ms 16948 KB Output is correct
56 Correct 900 ms 16536 KB Output is correct
57 Correct 904 ms 17460 KB Output is correct
58 Correct 903 ms 17504 KB Output is correct
59 Correct 912 ms 16900 KB Output is correct
60 Correct 931 ms 17492 KB Output is correct
61 Correct 944 ms 17316 KB Output is correct
62 Correct 898 ms 16948 KB Output is correct
63 Correct 900 ms 17588 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 936 ms 18996 KB Output is correct
2 Correct 938 ms 18740 KB Output is correct
3 Correct 915 ms 18808 KB Output is correct
4 Correct 985 ms 18996 KB Output is correct
5 Correct 913 ms 18868 KB Output is correct
6 Correct 912 ms 19124 KB Output is correct
7 Correct 919 ms 19636 KB Output is correct
8 Correct 921 ms 19508 KB Output is correct
9 Correct 900 ms 19764 KB Output is correct
10 Correct 911 ms 19252 KB Output is correct
11 Correct 909 ms 18740 KB Output is correct
12 Correct 910 ms 19368 KB Output is correct
13 Correct 928 ms 19636 KB Output is correct
14 Correct 909 ms 19308 KB Output is correct
15 Correct 903 ms 18740 KB Output is correct
16 Correct 922 ms 18612 KB Output is correct
17 Correct 910 ms 18740 KB Output is correct
18 Correct 933 ms 18776 KB Output is correct
19 Correct 903 ms 18740 KB Output is correct
20 Correct 904 ms 19632 KB Output is correct
21 Correct 918 ms 19124 KB Output is correct
22 Correct 902 ms 16692 KB Output is correct
23 Correct 911 ms 17184 KB Output is correct
24 Correct 931 ms 16564 KB Output is correct
25 Correct 904 ms 16932 KB Output is correct
26 Correct 904 ms 16676 KB Output is correct
27 Correct 930 ms 17188 KB Output is correct
28 Correct 902 ms 16564 KB Output is correct
29 Correct 914 ms 17876 KB Output is correct
30 Correct 909 ms 16948 KB Output is correct
31 Correct 898 ms 16804 KB Output is correct
32 Correct 894 ms 16564 KB Output is correct
33 Correct 909 ms 17204 KB Output is correct
34 Correct 893 ms 17204 KB Output is correct
35 Correct 907 ms 16828 KB Output is correct
36 Correct 909 ms 17588 KB Output is correct
37 Correct 941 ms 17332 KB Output is correct
38 Correct 906 ms 16988 KB Output is correct
39 Correct 914 ms 16436 KB Output is correct
40 Correct 911 ms 16272 KB Output is correct
41 Correct 894 ms 16820 KB Output is correct
42 Correct 914 ms 16164 KB Output is correct
43 Correct 911 ms 17424 KB Output is correct
44 Correct 924 ms 17504 KB Output is correct
45 Correct 910 ms 17460 KB Output is correct
46 Correct 909 ms 17588 KB Output is correct
47 Correct 942 ms 17460 KB Output is correct
48 Correct 917 ms 17036 KB Output is correct
49 Correct 897 ms 17284 KB Output is correct
50 Correct 912 ms 17332 KB Output is correct
51 Correct 892 ms 16948 KB Output is correct
52 Correct 902 ms 17588 KB Output is correct
53 Correct 906 ms 16820 KB Output is correct
54 Correct 904 ms 17476 KB Output is correct
55 Correct 897 ms 16948 KB Output is correct
56 Correct 900 ms 16536 KB Output is correct
57 Correct 904 ms 17460 KB Output is correct
58 Correct 903 ms 17504 KB Output is correct
59 Correct 912 ms 16900 KB Output is correct
60 Correct 931 ms 17492 KB Output is correct
61 Correct 944 ms 17316 KB Output is correct
62 Correct 898 ms 16948 KB Output is correct
63 Correct 900 ms 17588 KB Output is correct
64 Incorrect 894 ms 17460 KB Output isn't correct
65 Halted 0 ms 0 KB -