oj.uz

Submission #446289

# Submission time Handle Problem Language Result Execution time Memory
446289 2021-07-21T13:27:28 Z qwerasdfzxcl Cubeword (CEOI19_cubeword) C++14
21 / 100
 1016 ms 8532 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const int MOD = 998244353;
int cnt[101][10][10];
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};

ll calc(int len){
    ll ret = 1;
    for (int i=0;i<12;i++){
        ret *= cnt[len][a[b[i]]][a[c[i]]];
        ret %= MOD;
    }
    return ret;
}

bool nxt(int mx){
    bool flag = 1;
    for (int i=0;i<8;i++) if (a[i]!=mx-1) flag = 0;
    if (flag) return 0;
    a[7]++;
    for (int i=7;i>0;i--){
        if (a[i]!=mx) break;
        a[i] = 0;
        a[i-1]++;
    }
    return 1;
}

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;
    for (int i=0;i<n;i++){
        string s;
        cin >> s;
        cnt[(int)s.size()][s[0]-'a'][s.back()-'a']++;
        cnt[(int)s.size()][s.back()-'a'][s[0]-'a']++;
        if (st.find(s)!=st.end()){
            cnt[(int)s.size()][s[0]-'a'][s.back()-'a']--;
            cnt[(int)s.size()][s.back()-'a'][s[0]-'a']--;
            continue;
        }
        reverse(s.begin(), s.end());
        if (st.find(s)!=st.end()){
            cnt[(int)s.size()][s[0]-'a'][s.back()-'a']--;
            cnt[(int)s.size()][s.back()-'a'][s[0]-'a']--;
            continue;
        }
        if (chk(s)) cnt[(int)s.size()][s.back()-'a'][s[0]-'a']--;
        st.insert(s);
    }
    ll ans = 0;
    for (int len=3;len<=10;len++){
        for (int i=0;i<8;i++) a[i] = 0;
        while(true){
            ans = (ans+calc(len))%MOD;
            /*if (calc(len)){
                for (int i=0;i<8;i++) printf("%d ", a[i]);
                printf("\n");
            }*/
            if (!nxt(6)) break;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 7556 KB Output is correct
2 Correct 991 ms 8440 KB Output is correct
3 Correct 997 ms 8404 KB Output is correct
4 Correct 990 ms 8404 KB Output is correct
5 Correct 993 ms 8532 KB Output is correct
6 Correct 987 ms 8404 KB Output is correct
7 Correct 985 ms 8404 KB Output is correct
8 Correct 995 ms 8368 KB Output is correct
9 Correct 986 ms 8404 KB Output is correct
10 Correct 990 ms 8400 KB Output is correct
11 Correct 986 ms 8396 KB Output is correct
12 Correct 983 ms 8404 KB Output is correct
13 Correct 1008 ms 8404 KB Output is correct
14 Correct 985 ms 8404 KB Output is correct
15 Correct 986 ms 8404 KB Output is correct
16 Correct 995 ms 8332 KB Output is correct
17 Correct 998 ms 8352 KB Output is correct
18 Correct 990 ms 8404 KB Output is correct
19 Correct 1000 ms 8436 KB Output is correct
20 Correct 982 ms 8404 KB Output is correct
21 Correct 999 ms 8408 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 7556 KB Output is correct
2 Correct 991 ms 8440 KB Output is correct
3 Correct 997 ms 8404 KB Output is correct
4 Correct 990 ms 8404 KB Output is correct
5 Correct 993 ms 8532 KB Output is correct
6 Correct 987 ms 8404 KB Output is correct
7 Correct 985 ms 8404 KB Output is correct
8 Correct 995 ms 8368 KB Output is correct
9 Correct 986 ms 8404 KB Output is correct
10 Correct 990 ms 8400 KB Output is correct
11 Correct 986 ms 8396 KB Output is correct
12 Correct 983 ms 8404 KB Output is correct
13 Correct 1008 ms 8404 KB Output is correct
14 Correct 985 ms 8404 KB Output is correct
15 Correct 986 ms 8404 KB Output is correct
16 Correct 995 ms 8332 KB Output is correct
17 Correct 998 ms 8352 KB Output is correct
18 Correct 990 ms 8404 KB Output is correct
19 Correct 1000 ms 8436 KB Output is correct
20 Correct 982 ms 8404 KB Output is correct
21 Correct 999 ms 8408 KB Output is correct
22 Incorrect 1016 ms 8384 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 7556 KB Output is correct
2 Correct 991 ms 8440 KB Output is correct
3 Correct 997 ms 8404 KB Output is correct
4 Correct 990 ms 8404 KB Output is correct
5 Correct 993 ms 8532 KB Output is correct
6 Correct 987 ms 8404 KB Output is correct
7 Correct 985 ms 8404 KB Output is correct
8 Correct 995 ms 8368 KB Output is correct
9 Correct 986 ms 8404 KB Output is correct
10 Correct 990 ms 8400 KB Output is correct
11 Correct 986 ms 8396 KB Output is correct
12 Correct 983 ms 8404 KB Output is correct
13 Correct 1008 ms 8404 KB Output is correct
14 Correct 985 ms 8404 KB Output is correct
15 Correct 986 ms 8404 KB Output is correct
16 Correct 995 ms 8332 KB Output is correct
17 Correct 998 ms 8352 KB Output is correct
18 Correct 990 ms 8404 KB Output is correct
19 Correct 1000 ms 8436 KB Output is correct
20 Correct 982 ms 8404 KB Output is correct
21 Correct 999 ms 8408 KB Output is correct
22 Incorrect 1016 ms 8384 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 7556 KB Output is correct
2 Correct 991 ms 8440 KB Output is correct
3 Correct 997 ms 8404 KB Output is correct
4 Correct 990 ms 8404 KB Output is correct
5 Correct 993 ms 8532 KB Output is correct
6 Correct 987 ms 8404 KB Output is correct
7 Correct 985 ms 8404 KB Output is correct
8 Correct 995 ms 8368 KB Output is correct
9 Correct 986 ms 8404 KB Output is correct
10 Correct 990 ms 8400 KB Output is correct
11 Correct 986 ms 8396 KB Output is correct
12 Correct 983 ms 8404 KB Output is correct
13 Correct 1008 ms 8404 KB Output is correct
14 Correct 985 ms 8404 KB Output is correct
15 Correct 986 ms 8404 KB Output is correct
16 Correct 995 ms 8332 KB Output is correct
17 Correct 998 ms 8352 KB Output is correct
18 Correct 990 ms 8404 KB Output is correct
19 Correct 1000 ms 8436 KB Output is correct
20 Correct 982 ms 8404 KB Output is correct
21 Correct 999 ms 8408 KB Output is correct
22 Incorrect 1016 ms 8384 KB Output isn't correct
23 Halted 0 ms 0 KB -