oj.uz

Submission #198109

# Submission time Handle Problem Language Result Execution time Memory
198109 2020-01-24T18:08:24 Z model_code Cubeword (CEOI19_cubeword) Java 11
0 / 100
 1100 ms 44856 KB 
import java.io.*;
import java.util.*;
 
 
public class cubeword {
    public static final int M = 62;
    public static final int L = 10;
    public static final int MOD = 998244353;
    
    static int id(char c) {
        if (c >= 'a' && c <= 'z') {
            return c-'a';
        } else if (c >= 'A' && c <= 'Z') {
            return c-'A'+26;
        } else {
            return c-'0'+52;
        }
    }
    
    static int mul(int a, int b) {
        return (int)((long)(a)*(long)(b)%MOD);
    }
 
    public static void main(String[] args) throws IOException {
        int U[][][] = new int[L+1][M][M];
        int D[][][] = new int[M][M][M];
    
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(rd.readLine());
        Set<String> W = new HashSet<String>();
        for (int i = 0; i < N; ++i) {
            String S = rd.readLine();
            W.add(S);
            W.add(new StringBuffer(S).reverse().toString());
        }
 
        for (String S: W) {
            int a = id(S.charAt(0));
            int b = id(S.charAt(S.length()-1));
            int len = S.length();
            U[len][a][b]++;
        }
 
        long ans = 0;
        for (int x = 3; x <= L; ++x) {
            for (int i = 0; i < M; ++i) {
                for (int j = i; j < M; j++) {
                    for (int k = j; k < M; k++) {
                        D[i][j][k] = 0;
                    }
                }
            }
            for (int i = 0; i < M; ++i) {
                for (int j = i; j < M; j++) {
                    for (int k = j; k < M; k++) {
                        for (int l = 0; l < M; l++) {
                            D[i][j][k] = (D[i][j][k] + mul(U[x][i][l], mul(U[x][j][l], U[x][k][l]))) % MOD; 
                        }
                    }
                }
            }
 
            int Mul[] = new int[] { 24, 12, 12, 4, 12, 6, 4, 1 };
            for (int i = 0; i < M; i++) {
                for (int j = i; j < M; j++) {
                    for (int k = j; k < M; k++) {
                        for (int l = k; l < M; l++) {
                            int q = ((i==j)?4:0) + ((j==k)?2:0) + ((k==l)?1:0);
                            ans += (long)mul(mul(D[i][j][k], D[i][j][l]), mul(D[i][k][l], D[j][k][l])) % MOD * Mul[q];
                        }
                    }
                }
            }
            ans %= MOD;
        }
 
        System.out.println(ans % MOD);
    }
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 44220 KB Output is correct
2 Correct 1008 ms 43172 KB Output is correct
3 Correct 844 ms 44168 KB Output is correct
4 Correct 797 ms 44392 KB Output is correct
5 Correct 1051 ms 44856 KB Output is correct
6 Execution timed out 1103 ms 44496 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 44220 KB Output is correct
2 Correct 1008 ms 43172 KB Output is correct
3 Correct 844 ms 44168 KB Output is correct
4 Correct 797 ms 44392 KB Output is correct
5 Correct 1051 ms 44856 KB Output is correct
6 Execution timed out 1103 ms 44496 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 44220 KB Output is correct
2 Correct 1008 ms 43172 KB Output is correct
3 Correct 844 ms 44168 KB Output is correct
4 Correct 797 ms 44392 KB Output is correct
5 Correct 1051 ms 44856 KB Output is correct
6 Execution timed out 1103 ms 44496 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 44220 KB Output is correct
2 Correct 1008 ms 43172 KB Output is correct
3 Correct 844 ms 44168 KB Output is correct
4 Correct 797 ms 44392 KB Output is correct
5 Correct 1051 ms 44856 KB Output is correct
6 Execution timed out 1103 ms 44496 KB Time limit exceeded
7 Halted 0 ms 0 KB -