oj.uz

Submission #446310

# Submission time Handle Problem Language Result Execution time Memory
446310 2021-07-21T14:19:28 Z qwerasdfzxcl Cubeword (CEOI19_cubeword) C++14
84 / 100
 1100 ms 23108 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
#define MX 62

typedef long long ll;
using namespace std;
const int MOD = 998244353;
int cnt[101][101][101];
int a[8], b[12] = {0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6, 7}, c[12] = {1, 2, 3, 0, 4, 5, 6, 7, 5, 6, 7, 4};
int mp[505], val[11][101][101][101];

bool chk(string &s){
    int n = s.size();
    for (int i=0;i<n;i++){
        int j = n-1-i;
        if (i>j) break;
        if (s[i]!=s[j]) return 0;
    }
    return 1;
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    unordered_set<string> st[11];

    for (int i='a';i<='z';i++){
        mp[i] = i-'a';
    }
    for (int i='A';i<='Z';i++){
        mp[i] = i-'A'+26;
    }
    for (int i='0';i<='9';i++){
        mp[i] = i-'0'+52;
    }
    for (int i=0;i<n;i++){
        string s;
        cin >> s;
        int idx1 = mp[s[0]], idx2 = mp[s.back()], len = s.size();
        cnt[len][idx1][idx2]++;
        cnt[len][idx2][idx1]++;
        if (st[len].find(s)!=st[len].end()){
            cnt[len][idx1][idx2]--;
            cnt[len][idx2][idx1]--;
            continue;
        }
        reverse(s.begin(), s.end());
        if (st[len].find(s)!=st[len].end()){
            cnt[len][idx1][idx2]--;
            cnt[len][idx2][idx1]--;
            continue;
        }
        if (chk(s)) cnt[(int)s.size()][idx2][idx1]--;
        st[len].insert(s);
    }

    for (register int len=3;len<=10;len++){
        for (register int i=0;i<MX;i++){
            for (register int j=0;j<MX;j++){
                for (register int k=0;k<MX;k++){
                    for (register int l=0;l<MX;l++){
                        ll tmp = (ll)cnt[len][i][l] * cnt[len][j][l];
                        if (tmp>=MOD) tmp %= MOD;
                        tmp *= cnt[len][k][l];
                        if (tmp>=MOD) tmp %= MOD;
                        val[len][i][j][k] += tmp;
                        if (val[len][i][j][k]>=MOD) val[len][i][j][k] -= MOD;
                    }
                }
            }
        }
    }
    int ans = 0;
    for (register int len=3;len<=10;len++){
        for (register int i=0;i<MX;i++){
            for (register int j=0;j<MX;j++){
                for (register int k=0;k<MX;k++){
                    for (register int l=0;l<MX;l++){
                        ll tmp = val[len][i][j][k];
                        tmp = tmp*val[len][i][j][l];
                        if (tmp>=MOD) tmp %= MOD;
                        tmp = tmp*val[len][i][k][l];
                        if (tmp>=MOD) tmp %= MOD;
                        tmp = tmp*val[len][j][k][l];
                        if (tmp>=MOD) tmp %= MOD;
                        ans += tmp;
                        if (ans>=MOD) ans -= MOD;
                    }
                }
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message

cubeword.cpp: In function 'int main()':
cubeword.cpp:42:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |         int idx1 = mp[s[0]], idx2 = mp[s.back()], len = s.size();
      |                           ^
cubeword.cpp:42:46: warning: array subscript has type 'char' [-Wchar-subscripts]
   42 |         int idx1 = mp[s[0]], idx2 = mp[s.back()], len = s.size();
      |                                        ~~~~~~^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 22084 KB Output is correct
2 Correct 793 ms 21948 KB Output is correct
3 Correct 730 ms 22072 KB Output is correct
4 Correct 726 ms 21936 KB Output is correct
5 Correct 757 ms 21956 KB Output is correct
6 Correct 723 ms 22028 KB Output is correct
7 Correct 741 ms 21912 KB Output is correct
8 Correct 814 ms 22124 KB Output is correct
9 Correct 791 ms 22008 KB Output is correct
10 Correct 729 ms 21964 KB Output is correct
11 Correct 762 ms 22044 KB Output is correct
12 Correct 718 ms 22008 KB Output is correct
13 Correct 729 ms 22016 KB Output is correct
14 Correct 772 ms 22024 KB Output is correct
15 Correct 767 ms 22016 KB Output is correct
16 Correct 763 ms 22012 KB Output is correct
17 Correct 807 ms 22080 KB Output is correct
18 Correct 730 ms 21916 KB Output is correct
19 Correct 738 ms 22008 KB Output is correct
20 Correct 738 ms 21908 KB Output is correct
21 Correct 783 ms 22008 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 22084 KB Output is correct
2 Correct 793 ms 21948 KB Output is correct
3 Correct 730 ms 22072 KB Output is correct
4 Correct 726 ms 21936 KB Output is correct
5 Correct 757 ms 21956 KB Output is correct
6 Correct 723 ms 22028 KB Output is correct
7 Correct 741 ms 21912 KB Output is correct
8 Correct 814 ms 22124 KB Output is correct
9 Correct 791 ms 22008 KB Output is correct
10 Correct 729 ms 21964 KB Output is correct
11 Correct 762 ms 22044 KB Output is correct
12 Correct 718 ms 22008 KB Output is correct
13 Correct 729 ms 22016 KB Output is correct
14 Correct 772 ms 22024 KB Output is correct
15 Correct 767 ms 22016 KB Output is correct
16 Correct 763 ms 22012 KB Output is correct
17 Correct 807 ms 22080 KB Output is correct
18 Correct 730 ms 21916 KB Output is correct
19 Correct 738 ms 22008 KB Output is correct
20 Correct 738 ms 21908 KB Output is correct
21 Correct 783 ms 22008 KB Output is correct
22 Correct 795 ms 22520 KB Output is correct
23 Correct 741 ms 22600 KB Output is correct
24 Correct 780 ms 22516 KB Output is correct
25 Correct 747 ms 22560 KB Output is correct
26 Correct 780 ms 22384 KB Output is correct
27 Correct 776 ms 22512 KB Output is correct
28 Correct 749 ms 22596 KB Output is correct
29 Correct 819 ms 22512 KB Output is correct
30 Correct 854 ms 22436 KB Output is correct
31 Correct 768 ms 22512 KB Output is correct
32 Correct 743 ms 22468 KB Output is correct
33 Correct 768 ms 22456 KB Output is correct
34 Correct 733 ms 22528 KB Output is correct
35 Correct 773 ms 22508 KB Output is correct
36 Correct 851 ms 22516 KB Output is correct
37 Correct 732 ms 22620 KB Output is correct
38 Correct 733 ms 22560 KB Output is correct
39 Correct 734 ms 22512 KB Output is correct
40 Correct 734 ms 22520 KB Output is correct
41 Correct 747 ms 22796 KB Output is correct
42 Correct 811 ms 22512 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 22084 KB Output is correct
2 Correct 793 ms 21948 KB Output is correct
3 Correct 730 ms 22072 KB Output is correct
4 Correct 726 ms 21936 KB Output is correct
5 Correct 757 ms 21956 KB Output is correct
6 Correct 723 ms 22028 KB Output is correct
7 Correct 741 ms 21912 KB Output is correct
8 Correct 814 ms 22124 KB Output is correct
9 Correct 791 ms 22008 KB Output is correct
10 Correct 729 ms 21964 KB Output is correct
11 Correct 762 ms 22044 KB Output is correct
12 Correct 718 ms 22008 KB Output is correct
13 Correct 729 ms 22016 KB Output is correct
14 Correct 772 ms 22024 KB Output is correct
15 Correct 767 ms 22016 KB Output is correct
16 Correct 763 ms 22012 KB Output is correct
17 Correct 807 ms 22080 KB Output is correct
18 Correct 730 ms 21916 KB Output is correct
19 Correct 738 ms 22008 KB Output is correct
20 Correct 738 ms 21908 KB Output is correct
21 Correct 783 ms 22008 KB Output is correct
22 Correct 795 ms 22520 KB Output is correct
23 Correct 741 ms 22600 KB Output is correct
24 Correct 780 ms 22516 KB Output is correct
25 Correct 747 ms 22560 KB Output is correct
26 Correct 780 ms 22384 KB Output is correct
27 Correct 776 ms 22512 KB Output is correct
28 Correct 749 ms 22596 KB Output is correct
29 Correct 819 ms 22512 KB Output is correct
30 Correct 854 ms 22436 KB Output is correct
31 Correct 768 ms 22512 KB Output is correct
32 Correct 743 ms 22468 KB Output is correct
33 Correct 768 ms 22456 KB Output is correct
34 Correct 733 ms 22528 KB Output is correct
35 Correct 773 ms 22508 KB Output is correct
36 Correct 851 ms 22516 KB Output is correct
37 Correct 732 ms 22620 KB Output is correct
38 Correct 733 ms 22560 KB Output is correct
39 Correct 734 ms 22512 KB Output is correct
40 Correct 734 ms 22520 KB Output is correct
41 Correct 747 ms 22796 KB Output is correct
42 Correct 811 ms 22512 KB Output is correct
43 Correct 806 ms 22720 KB Output is correct
44 Correct 800 ms 22684 KB Output is correct
45 Correct 794 ms 22640 KB Output is correct
46 Correct 805 ms 22716 KB Output is correct
47 Correct 810 ms 22724 KB Output is correct
48 Correct 803 ms 22844 KB Output is correct
49 Correct 800 ms 22848 KB Output is correct
50 Correct 791 ms 22724 KB Output is correct
51 Correct 779 ms 22716 KB Output is correct
52 Correct 775 ms 22852 KB Output is correct
53 Correct 783 ms 22760 KB Output is correct
54 Correct 781 ms 22724 KB Output is correct
55 Correct 797 ms 22624 KB Output is correct
56 Correct 780 ms 22720 KB Output is correct
57 Correct 805 ms 22724 KB Output is correct
58 Correct 800 ms 22720 KB Output is correct
59 Correct 776 ms 22752 KB Output is correct
60 Correct 851 ms 22732 KB Output is correct
61 Correct 807 ms 22844 KB Output is correct
62 Correct 767 ms 22856 KB Output is correct
63 Correct 786 ms 22852 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 728 ms 22084 KB Output is correct
2 Correct 793 ms 21948 KB Output is correct
3 Correct 730 ms 22072 KB Output is correct
4 Correct 726 ms 21936 KB Output is correct
5 Correct 757 ms 21956 KB Output is correct
6 Correct 723 ms 22028 KB Output is correct
7 Correct 741 ms 21912 KB Output is correct
8 Correct 814 ms 22124 KB Output is correct
9 Correct 791 ms 22008 KB Output is correct
10 Correct 729 ms 21964 KB Output is correct
11 Correct 762 ms 22044 KB Output is correct
12 Correct 718 ms 22008 KB Output is correct
13 Correct 729 ms 22016 KB Output is correct
14 Correct 772 ms 22024 KB Output is correct
15 Correct 767 ms 22016 KB Output is correct
16 Correct 763 ms 22012 KB Output is correct
17 Correct 807 ms 22080 KB Output is correct
18 Correct 730 ms 21916 KB Output is correct
19 Correct 738 ms 22008 KB Output is correct
20 Correct 738 ms 21908 KB Output is correct
21 Correct 783 ms 22008 KB Output is correct
22 Correct 795 ms 22520 KB Output is correct
23 Correct 741 ms 22600 KB Output is correct
24 Correct 780 ms 22516 KB Output is correct
25 Correct 747 ms 22560 KB Output is correct
26 Correct 780 ms 22384 KB Output is correct
27 Correct 776 ms 22512 KB Output is correct
28 Correct 749 ms 22596 KB Output is correct
29 Correct 819 ms 22512 KB Output is correct
30 Correct 854 ms 22436 KB Output is correct
31 Correct 768 ms 22512 KB Output is correct
32 Correct 743 ms 22468 KB Output is correct
33 Correct 768 ms 22456 KB Output is correct
34 Correct 733 ms 22528 KB Output is correct
35 Correct 773 ms 22508 KB Output is correct
36 Correct 851 ms 22516 KB Output is correct
37 Correct 732 ms 22620 KB Output is correct
38 Correct 733 ms 22560 KB Output is correct
39 Correct 734 ms 22512 KB Output is correct
40 Correct 734 ms 22520 KB Output is correct
41 Correct 747 ms 22796 KB Output is correct
42 Correct 811 ms 22512 KB Output is correct
43 Correct 806 ms 22720 KB Output is correct
44 Correct 800 ms 22684 KB Output is correct
45 Correct 794 ms 22640 KB Output is correct
46 Correct 805 ms 22716 KB Output is correct
47 Correct 810 ms 22724 KB Output is correct
48 Correct 803 ms 22844 KB Output is correct
49 Correct 800 ms 22848 KB Output is correct
50 Correct 791 ms 22724 KB Output is correct
51 Correct 779 ms 22716 KB Output is correct
52 Correct 775 ms 22852 KB Output is correct
53 Correct 783 ms 22760 KB Output is correct
54 Correct 781 ms 22724 KB Output is correct
55 Correct 797 ms 22624 KB Output is correct
56 Correct 780 ms 22720 KB Output is correct
57 Correct 805 ms 22724 KB Output is correct
58 Correct 800 ms 22720 KB Output is correct
59 Correct 776 ms 22752 KB Output is correct
60 Correct 851 ms 22732 KB Output is correct
61 Correct 807 ms 22844 KB Output is correct
62 Correct 767 ms 22856 KB Output is correct
63 Correct 786 ms 22852 KB Output is correct
64 Correct 1087 ms 22856 KB Output is correct
65 Correct 1056 ms 22960 KB Output is correct
66 Correct 1057 ms 22960 KB Output is correct
67 Correct 1070 ms 23108 KB Output is correct
68 Correct 1084 ms 22964 KB Output is correct
69 Correct 1080 ms 23076 KB Output is correct
70 Correct 1066 ms 22956 KB Output is correct
71 Correct 1088 ms 22980 KB Output is correct
72 Correct 1067 ms 22980 KB Output is correct
73 Correct 1066 ms 22980 KB Output is correct
74 Correct 1058 ms 22980 KB Output is correct
75 Correct 1083 ms 22980 KB Output is correct
76 Correct 1048 ms 22852 KB Output is correct
77 Correct 1062 ms 22964 KB Output is correct
78 Correct 1058 ms 22980 KB Output is correct
79 Execution timed out 1106 ms 23060 KB Time limit exceeded
80 Halted 0 ms 0 KB -