oj.uz

Submission #446333

# Submission time Handle Problem Language Result Execution time Memory
446333 2021-07-21T14:53:23 Z urd05 Cubeword (CEOI19_cubeword) C++17
0 / 100
 1100 ms 6436 KB 
#include <bits/stdc++.h>
using namespace std;

const int mod=998244353;

int ctn(char c) {
    if (c>='a'&&c<='z') {
        return c-'a';
    }
    if (c>='A'&&c<='Z') {
        return c-'A'+26;
    }
    return c-'0'+52;
}

bool ispalin(char str[],int l) {
    for(int i=0;i<l;i++) {
        if (str[i]!=str[l-1-i]) {
            return false;
        }
    }
    return true;
}

long long val[62][62];
char str[100000][11];
long long num[62][62][62];
set<string> st;

void mstr(char c[],int l) {
    string ret;
    for(int i=0;i<l;i++) {
        ret.push_back(c[i]);
    }
    st.insert(ret);
    string emp;
    for(int i=0;i<l;i++) {
        emp.push_back(c[l-1-i]);
    }
    st.insert(emp);
}

string makestr(char c[],int l) {
    string ret;
    for(int i=0;i<l;i++) {
        ret.push_back(c[i]);
    }
    return ret;
}

string makeinvstr(char c[],int l) {
    string ret;
    for(int i=0;i<l;i++) {
        ret.push_back(c[l-1-i]);
    }
    return ret;
}

int main(void) {
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%s",str[i]);
    }
    long long ret=0;
    for(int nm=3;nm<=10;nm++) {
        st.clear();
        memset(val,0,sizeof(val));
        memset(num,0,sizeof(num));
        for(int i=0;i<n;i++) {
            int l=strlen(str[i]);
            if (l!=nm) {
                continue;
            }
            int s=ctn(str[i][0]);
            int e=ctn(str[i][l-1]);
            if (st.find(makestr(str[i],l))==st.end()) {
                val[s][e]++;
            }
            if (!ispalin(str[i],l)&&st.find(makeinvstr(str[i],l))==st.end()) {
                val[e][s]++;
            }
            mstr(str[i],l);
        }
        for(int i=0;i<62;i++) {
            for(int j=0;j<62;j++) {
                for(int k=0;k<62;k++) {
                    for(int l=0;l<62;l++) {
                        num[j][k][l]+=val[i][j]*val[i][k]*val[i][l];
                        num[j][k][l]%=mod;
                    }
                }
            }
        }
        for(int i=0;i<62;i++) {
            for(int j=0;j<62;j++) {
                for(int k=0;k<62;k++) {
                    for(int l=0;l<62;l++) {
                        long long x=((num[i][j][k]*num[i][j][l])%mod)*((num[i][k][l]*num[j][k][l])%mod);
                        x%=mod;
                        ret+=x;
                        ret%=mod;
                    }
                }
            }
        }
    }
    printf("%lld",ret);
}

Compilation message

cubeword.cpp: In function 'int main()':
cubeword.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
cubeword.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf("%s",str[i]);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1195 ms 6436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1195 ms 6436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1195 ms 6436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1195 ms 6436 KB Time limit exceeded
2 Halted 0 ms 0 KB -