oj.uz

Submission #953581

# Submission time Handle Problem Language Result Execution time Memory
953581 2024-03-26T09:25:36 Z mircea_007 Cubeword (CEOI19_cubeword) C++17
0 / 100
 1100 ms 15848 KB 
#pragma GCC optimize("O3,unroll-loops")

#include <iostream>
#include <string>
#include <unordered_set>
#include <algorithm>

#define MOD 998244353
using ll = long long;

#define SIGMA 64
const int MINLEN = 3;
const int MAXLEN = 10;

int char_idx[128];

int freq[MAXLEN + 1][SIGMA][SIGMA];
int lfreq[SIGMA][SIGMA];
int triangle[SIGMA][SIGMA][SIGMA];

int main() {
  int n;
  std::cin >> n;

  // hash map
  std::unordered_set<std::string> words;

  for( int i = 0 ; i < n ; i++ ){
    std::string w;
    std::cin >> w;

    words.insert( w );

    std::reverse( w.begin(), w.end() );

    words.insert( w );
  }

  {
    int idx = 0;
    for( int ch = 'a' ; ch <= 'z' ; ch++ )
      char_idx[ch] = idx++;
    for( int ch = 'A' ; ch <= 'Z' ; ch++ )
      char_idx[ch] = idx++;
    for( int ch = '0' ; ch <= '9' ; ch++ )
      char_idx[ch] = idx++;
  }

  for( std::string w : words )
    freq[(int)w.size()][char_idx[(int)w.front()]][char_idx[(int)w.back()]]++;

  int ret = 0;
  for( int len = MINLEN ; len <= MAXLEN ; len++ ){
    for( int a = 0 ; a < SIGMA ; a++ )
      for( int b = 0 ; b < SIGMA ; b++ )
        lfreq[a][b] = freq[len][a][b];
    
    for( int a = 0 ; a < SIGMA ; a++ ){
      for( int b = 0 ; b < SIGMA ; b++ )
        for( int c = 0 ; c < SIGMA ; c++ ){
          triangle[a][b][c] = 0;
          
          for( int mij = 0 ; mij < SIGMA ; mij++ )
            triangle[a][b][c] = (triangle[a][b][c] + (lfreq[a][mij] * (ll)lfreq[b][mij]) % MOD * (ll)lfreq[c][mij]) % MOD;
        }
    }

    // fixam 4 colturi neadiacente (oricare doua unite printr-o diagonala de latura)
    for( int a = 0 ; a < SIGMA ; a++ )
      for( int b = 0 ; b < SIGMA ; b++ )
        for( int c = 0 ; c < SIGMA ; c++ )
          for( int d = 0 ; d < SIGMA ; d++ )
            ret = (ret + (triangle[a][b][c] * (ll)triangle[b][c][d]) % MOD * (ll)triangle[a][c][d] % MOD * (ll)triangle[a][b][d]) % MOD;
  }

  printf( "%d\n", ret );
  
  return 0;
}

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1135 ms 15848 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 1135 ms 15848 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 1135 ms 15848 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 1135 ms 15848 KB Time limit exceeded
2 Halted 0 ms 0 KB -