oj.uz

Submission #1093472

# Submission time Handle Problem Language Result Execution time Memory
1093472 2024-09-27T00:36:51 Z Lemser Cubeword (CEOI19_cubeword) C++14
100 / 100
 884 ms 36304 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("popcnt")
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
 
#define endl '\n'
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
 
#define fore(i,l,r) for(auto i=l;i<r;i++)
#define fo(i,n) fore(i,0,n)
#define forex(i,r,l) for(auto i=r; i>=l;i--)
#define ffo(i,n) forex(i,n-1,0)
 
bool cmin(int &a, int b){if(b<a){a=b;return 1;}return 0;}
bool cmax(int &a, int b){if(b>a){a=b;return 1;}return 0;}
void valid(ll in){cout<<((in)?"YES\n":"NO\n");}
ll lcm(ll a, ll b){return (a/gcd(a,b))*b;}
ll gauss(ll n){return (n*(n+1))/2;}
const int N = 1e5 + 7, LOG=20,mod=998244353;
int n,X=0;
ll cnt[11][64][64][64], cnt2[11][64][64];
string s[N];
map<char, int> let;
void test_case(){
    cin>>n;
    set<string> st;
    fo(i,n){
        cin>>s[i];
        int t=sz(s[i]);
        st.insert(s[i]);
        reverse(all(s[i]));
        st.insert(s[i]);
    }
    for(auto e:st)cnt2[sz(e)][let[e[0]]][let[e.back()]]++;
    fore(t, 3, 11){
        fo(d,X){
            fo(a,X){
                if(cnt2[t][d][a]==0)continue;
                fo(b,X){
                    if(cnt2[t][b][d]==0)continue;
                    fo(c,X){
                        if(cnt2[t][d][c]==0)continue;
                        ll aa=cnt2[t][d][a];
                        aa=aa*cnt2[t][b][d];
                        aa=aa*cnt2[t][d][c];
                        cnt[t][a][b][c]=(cnt[t][a][b][c]+aa)%mod;
                    }
                }
            }
        }
    }
    ll ans=0;
    fore(t, 3, 11){
        fo(a,X){
            fo(b,X){
                fo(c,X){
                    fo(d,X){
                        if(min({cnt[t][a][b][c],cnt[t][d][a][b],cnt[t][d][c][b],cnt[t][a][d][c]})==0)continue;
                        ll aa=cnt[t][a][b][c];
                        aa=aa*cnt[t][d][a][b];
                        if(aa>=mod)aa%=mod;
                        ll aa2=cnt[t][d][c][b];
                        aa2=aa2*cnt[t][a][d][c];
                        if(aa2>=mod)aa2%=mod;
                        ans=ans+(aa*aa2)%mod;
                        if(ans>=mod)ans-=mod;
                    }
                }
            }
        }
    }
    ans%=mod;
    cout<<ans<<endl;
}
int main(){cin.tie(0)->sync_with_stdio(0);
    for(char a='a';a<='z';a++)let[a]=X++;
    for(char a='A';a<='Z';a++)let[a]=X++;
    for(char a='0';a<='9';a++)let[a]=X++;
    int t=1;
    // cin >> t;
    while(t--)test_case();
}

Compilation message

cubeword.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
cubeword.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
cubeword.cpp: In function 'void test_case()':
cubeword.cpp:50:13: warning: unused variable 't' [-Wunused-variable]
   50 |         int t=sz(s[i]);
      |             ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 19284 KB Output is correct
2 Correct 831 ms 19396 KB Output is correct
3 Correct 813 ms 19264 KB Output is correct
4 Correct 797 ms 19400 KB Output is correct
5 Correct 809 ms 19276 KB Output is correct
6 Correct 807 ms 19404 KB Output is correct
7 Correct 810 ms 19228 KB Output is correct
8 Correct 795 ms 19220 KB Output is correct
9 Correct 837 ms 19404 KB Output is correct
10 Correct 793 ms 19420 KB Output is correct
11 Correct 794 ms 19404 KB Output is correct
12 Correct 792 ms 19396 KB Output is correct
13 Correct 789 ms 19284 KB Output is correct
14 Correct 793 ms 19280 KB Output is correct
15 Correct 784 ms 19420 KB Output is correct
16 Correct 807 ms 19280 KB Output is correct
17 Correct 787 ms 19284 KB Output is correct
18 Correct 800 ms 19316 KB Output is correct
19 Correct 832 ms 19280 KB Output is correct
20 Correct 811 ms 19416 KB Output is correct
21 Correct 787 ms 19280 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 19284 KB Output is correct
2 Correct 831 ms 19396 KB Output is correct
3 Correct 813 ms 19264 KB Output is correct
4 Correct 797 ms 19400 KB Output is correct
5 Correct 809 ms 19276 KB Output is correct
6 Correct 807 ms 19404 KB Output is correct
7 Correct 810 ms 19228 KB Output is correct
8 Correct 795 ms 19220 KB Output is correct
9 Correct 837 ms 19404 KB Output is correct
10 Correct 793 ms 19420 KB Output is correct
11 Correct 794 ms 19404 KB Output is correct
12 Correct 792 ms 19396 KB Output is correct
13 Correct 789 ms 19284 KB Output is correct
14 Correct 793 ms 19280 KB Output is correct
15 Correct 784 ms 19420 KB Output is correct
16 Correct 807 ms 19280 KB Output is correct
17 Correct 787 ms 19284 KB Output is correct
18 Correct 800 ms 19316 KB Output is correct
19 Correct 832 ms 19280 KB Output is correct
20 Correct 811 ms 19416 KB Output is correct
21 Correct 787 ms 19280 KB Output is correct
22 Correct 796 ms 21168 KB Output is correct
23 Correct 804 ms 20980 KB Output is correct
24 Correct 791 ms 21080 KB Output is correct
25 Correct 794 ms 21160 KB Output is correct
26 Correct 808 ms 21076 KB Output is correct
27 Correct 778 ms 21160 KB Output is correct
28 Correct 783 ms 21076 KB Output is correct
29 Correct 779 ms 21072 KB Output is correct
30 Correct 788 ms 21332 KB Output is correct
31 Correct 784 ms 21076 KB Output is correct
32 Correct 779 ms 21076 KB Output is correct
33 Correct 801 ms 21156 KB Output is correct
34 Correct 782 ms 21072 KB Output is correct
35 Correct 796 ms 21012 KB Output is correct
36 Correct 827 ms 21172 KB Output is correct
37 Correct 826 ms 21136 KB Output is correct
38 Correct 794 ms 21328 KB Output is correct
39 Correct 797 ms 21024 KB Output is correct
40 Correct 788 ms 21164 KB Output is correct
41 Correct 790 ms 21120 KB Output is correct
42 Correct 780 ms 21168 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 19284 KB Output is correct
2 Correct 831 ms 19396 KB Output is correct
3 Correct 813 ms 19264 KB Output is correct
4 Correct 797 ms 19400 KB Output is correct
5 Correct 809 ms 19276 KB Output is correct
6 Correct 807 ms 19404 KB Output is correct
7 Correct 810 ms 19228 KB Output is correct
8 Correct 795 ms 19220 KB Output is correct
9 Correct 837 ms 19404 KB Output is correct
10 Correct 793 ms 19420 KB Output is correct
11 Correct 794 ms 19404 KB Output is correct
12 Correct 792 ms 19396 KB Output is correct
13 Correct 789 ms 19284 KB Output is correct
14 Correct 793 ms 19280 KB Output is correct
15 Correct 784 ms 19420 KB Output is correct
16 Correct 807 ms 19280 KB Output is correct
17 Correct 787 ms 19284 KB Output is correct
18 Correct 800 ms 19316 KB Output is correct
19 Correct 832 ms 19280 KB Output is correct
20 Correct 811 ms 19416 KB Output is correct
21 Correct 787 ms 19280 KB Output is correct
22 Correct 796 ms 21168 KB Output is correct
23 Correct 804 ms 20980 KB Output is correct
24 Correct 791 ms 21080 KB Output is correct
25 Correct 794 ms 21160 KB Output is correct
26 Correct 808 ms 21076 KB Output is correct
27 Correct 778 ms 21160 KB Output is correct
28 Correct 783 ms 21076 KB Output is correct
29 Correct 779 ms 21072 KB Output is correct
30 Correct 788 ms 21332 KB Output is correct
31 Correct 784 ms 21076 KB Output is correct
32 Correct 779 ms 21076 KB Output is correct
33 Correct 801 ms 21156 KB Output is correct
34 Correct 782 ms 21072 KB Output is correct
35 Correct 796 ms 21012 KB Output is correct
36 Correct 827 ms 21172 KB Output is correct
37 Correct 826 ms 21136 KB Output is correct
38 Correct 794 ms 21328 KB Output is correct
39 Correct 797 ms 21024 KB Output is correct
40 Correct 788 ms 21164 KB Output is correct
41 Correct 790 ms 21120 KB Output is correct
42 Correct 780 ms 21168 KB Output is correct
43 Correct 819 ms 25936 KB Output is correct
44 Correct 814 ms 26064 KB Output is correct
45 Correct 846 ms 25940 KB Output is correct
46 Correct 824 ms 25936 KB Output is correct
47 Correct 804 ms 25940 KB Output is correct
48 Correct 819 ms 25884 KB Output is correct
49 Correct 815 ms 25936 KB Output is correct
50 Correct 841 ms 26048 KB Output is correct
51 Correct 806 ms 25856 KB Output is correct
52 Correct 808 ms 25936 KB Output is correct
53 Correct 804 ms 25936 KB Output is correct
54 Correct 811 ms 25940 KB Output is correct
55 Correct 814 ms 25940 KB Output is correct
56 Correct 807 ms 25940 KB Output is correct
57 Correct 824 ms 25896 KB Output is correct
58 Correct 828 ms 26048 KB Output is correct
59 Correct 821 ms 26204 KB Output is correct
60 Correct 802 ms 25940 KB Output is correct
61 Correct 798 ms 25940 KB Output is correct
62 Correct 801 ms 26124 KB Output is correct
63 Correct 801 ms 26044 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 19284 KB Output is correct
2 Correct 831 ms 19396 KB Output is correct
3 Correct 813 ms 19264 KB Output is correct
4 Correct 797 ms 19400 KB Output is correct
5 Correct 809 ms 19276 KB Output is correct
6 Correct 807 ms 19404 KB Output is correct
7 Correct 810 ms 19228 KB Output is correct
8 Correct 795 ms 19220 KB Output is correct
9 Correct 837 ms 19404 KB Output is correct
10 Correct 793 ms 19420 KB Output is correct
11 Correct 794 ms 19404 KB Output is correct
12 Correct 792 ms 19396 KB Output is correct
13 Correct 789 ms 19284 KB Output is correct
14 Correct 793 ms 19280 KB Output is correct
15 Correct 784 ms 19420 KB Output is correct
16 Correct 807 ms 19280 KB Output is correct
17 Correct 787 ms 19284 KB Output is correct
18 Correct 800 ms 19316 KB Output is correct
19 Correct 832 ms 19280 KB Output is correct
20 Correct 811 ms 19416 KB Output is correct
21 Correct 787 ms 19280 KB Output is correct
22 Correct 796 ms 21168 KB Output is correct
23 Correct 804 ms 20980 KB Output is correct
24 Correct 791 ms 21080 KB Output is correct
25 Correct 794 ms 21160 KB Output is correct
26 Correct 808 ms 21076 KB Output is correct
27 Correct 778 ms 21160 KB Output is correct
28 Correct 783 ms 21076 KB Output is correct
29 Correct 779 ms 21072 KB Output is correct
30 Correct 788 ms 21332 KB Output is correct
31 Correct 784 ms 21076 KB Output is correct
32 Correct 779 ms 21076 KB Output is correct
33 Correct 801 ms 21156 KB Output is correct
34 Correct 782 ms 21072 KB Output is correct
35 Correct 796 ms 21012 KB Output is correct
36 Correct 827 ms 21172 KB Output is correct
37 Correct 826 ms 21136 KB Output is correct
38 Correct 794 ms 21328 KB Output is correct
39 Correct 797 ms 21024 KB Output is correct
40 Correct 788 ms 21164 KB Output is correct
41 Correct 790 ms 21120 KB Output is correct
42 Correct 780 ms 21168 KB Output is correct
43 Correct 819 ms 25936 KB Output is correct
44 Correct 814 ms 26064 KB Output is correct
45 Correct 846 ms 25940 KB Output is correct
46 Correct 824 ms 25936 KB Output is correct
47 Correct 804 ms 25940 KB Output is correct
48 Correct 819 ms 25884 KB Output is correct
49 Correct 815 ms 25936 KB Output is correct
50 Correct 841 ms 26048 KB Output is correct
51 Correct 806 ms 25856 KB Output is correct
52 Correct 808 ms 25936 KB Output is correct
53 Correct 804 ms 25936 KB Output is correct
54 Correct 811 ms 25940 KB Output is correct
55 Correct 814 ms 25940 KB Output is correct
56 Correct 807 ms 25940 KB Output is correct
57 Correct 824 ms 25896 KB Output is correct
58 Correct 828 ms 26048 KB Output is correct
59 Correct 821 ms 26204 KB Output is correct
60 Correct 802 ms 25940 KB Output is correct
61 Correct 798 ms 25940 KB Output is correct
62 Correct 801 ms 26124 KB Output is correct
63 Correct 801 ms 26044 KB Output is correct
64 Correct 843 ms 35920 KB Output is correct
65 Correct 846 ms 35924 KB Output is correct
66 Correct 855 ms 35924 KB Output is correct
67 Correct 854 ms 35920 KB Output is correct
68 Correct 856 ms 35924 KB Output is correct
69 Correct 869 ms 36180 KB Output is correct
70 Correct 852 ms 36048 KB Output is correct
71 Correct 853 ms 36104 KB Output is correct
72 Correct 854 ms 36180 KB Output is correct
73 Correct 852 ms 36088 KB Output is correct
74 Correct 872 ms 35928 KB Output is correct
75 Correct 853 ms 36180 KB Output is correct
76 Correct 851 ms 36092 KB Output is correct
77 Correct 848 ms 36000 KB Output is correct
78 Correct 854 ms 35876 KB Output is correct
79 Correct 844 ms 36076 KB Output is correct
80 Correct 884 ms 36304 KB Output is correct
81 Correct 843 ms 35920 KB Output is correct
82 Correct 842 ms 36176 KB Output is correct
83 Correct 863 ms 35940 KB Output is correct
84 Correct 849 ms 35868 KB Output is correct