oj.uz

답안 #660084

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660084 2022-11-20T10:32:06 Z 600Mihnea Cubeword (CEOI19_cubeword) C++17
0 / 100
 1100 ms 7324 KB 
bool home = 0;
#include <bits/stdc++.h>

using namespace std;

const int MODULO = 998244353;

int get_char_id(char ch) {
  assert(('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z') || ('0' <= ch && ch <= '9'));
  if ('a' <= ch && ch <= 'z') {
    return ch - 'a';
  }
  if ('A' <= ch && ch <= 'Z') {
    return 1 + get_char_id('z') + ch - 'A';
  }
  return 1 + get_char_id('Z') + ch - '0';
}

const int MAX_WORD_LENGTH = 10;
///const int ALPHABET_SIZE = 2 * 26 + 10;
const int ALPHABET_SIZE = 16;
vector<string> words[MAX_WORD_LENGTH + 1];
int cnt_words[ALPHABET_SIZE][ALPHABET_SIZE];
int cnt3[ALPHABET_SIZE][ALPHABET_SIZE][ALPHABET_SIZE];

int main() {
  if (home == 0) {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  } else {
    freopen ("input.txt", "r", stdin);
  }

  {
    size_t num_samples;
    cin >> num_samples;
    for (size_t sample_index = 0; sample_index < num_samples; sample_index++) {
      string word;
      cin >> word;
      words[word.size()].push_back(word);
    }
  }
  int solution = 0;
  for (size_t word_length = 1; word_length <= MAX_WORD_LENGTH; word_length++) {
    if (words[word_length].empty()) {
      continue;
    }
    size_t word_count = words[word_length].size();
    for (size_t word_index = 0; word_index < word_count; word_index++) {
      string reverse_word = words[word_length][word_index];
      reverse(reverse_word.begin(), reverse_word.end());
      words[word_length].push_back(reverse_word);
    }
    sort(words[word_length].begin(), words[word_length].end());
    words[word_length].resize(unique(words[word_length].begin(), words[word_length].end()) - words[word_length].begin());
    word_count = words[word_length].size();
    for (size_t first_letter = 0; first_letter < ALPHABET_SIZE; first_letter++) {
      for (size_t last_letter = 0; last_letter < ALPHABET_SIZE; last_letter++) {
        cnt_words[first_letter][last_letter] = 0;
      }
    }
    for (size_t word_index = 0; word_index < word_count; word_index++) {
      cnt_words[get_char_id(words[word_length][word_index][0])][get_char_id(words[word_length][word_index].back())]++;
    }
    for (size_t a = 0; a < ALPHABET_SIZE; a++) {
      for (size_t b = 0; b < ALPHABET_SIZE; b++) {
        for (size_t c = 0; c < ALPHABET_SIZE; c++) {
          cnt3[a][b][c] = 0;
          for (size_t d = 0; d < ALPHABET_SIZE; d++) {
            cnt3[a][b][c] = (cnt3[a][b][c] + 1LL * cnt_words[d][a] * cnt_words[d][b] * cnt_words[d][c]) % MODULO;
          }
        }
      }
    }
    for (size_t a = 0; a < ALPHABET_SIZE; a++) {
      for (size_t b = 0; b < ALPHABET_SIZE; b++) {
        for (size_t c = 0; c < ALPHABET_SIZE; c++) {
          for (size_t d = 0; d < ALPHABET_SIZE; d++) {
            for (size_t e = 0; e < ALPHABET_SIZE; e++) {
              for (size_t f = 0; f < ALPHABET_SIZE; f++) {
                solution = (solution + 1LL * cnt_words[a][d] * cnt_words[a][f] * cnt_words[b][d] % MODULO * cnt_words[b][e] * cnt_words[c][f] * cnt_words[c][e] % MODULO * cnt3[a][b][c] % MODULO * cnt3[d][e][f]) % MODULO;
              }
            }
          }
        }
      }
    }
    continue;
    vector<array<int, 5>> all;

    for (size_t corner1 = 0; corner1 < ALPHABET_SIZE; corner1++) {
      for (size_t corner2 = 0; corner2 < ALPHABET_SIZE; corner2++) {
        if (cnt_words[corner1][corner2] == 0) {
          continue;
        }
        for (size_t corner3 = 0; corner3 < ALPHABET_SIZE; corner3++) {
          if (cnt_words[corner2][corner3] == 0) {
            continue;
          }
          for (size_t corner4 = 0; corner4 < ALPHABET_SIZE; corner4++) {
            if (cnt_words[corner3][corner4] == 0) {
              continue;
            }
            if (cnt_words[corner1][corner4] == 0) {
              continue;
            }
            int prod = 1LL * cnt_words[corner1][corner2] % MODULO * cnt_words[corner2][corner3] % MODULO * cnt_words[corner3][corner4] % MODULO * cnt_words[corner4][corner1] % MODULO;
            all.push_back({corner1, corner2, corner3, corner4, prod});
          }
        }
      }
    }
    for (size_t i = 0; i < all.size(); i++) {
      size_t corner1 = all[i][0];
      size_t corner2 = all[i][1];
      size_t corner3 = all[i][2];
      size_t corner4 = all[i][3];
      int prod_i = all[i][4];
      for (size_t j = 0; j < all.size(); j++) {
        size_t corner5 = all[j][0];
        size_t corner6 = all[j][1];
        size_t corner7 = all[j][2];
        size_t corner8 = all[j][3];
        int prod_j = all[j][4];
        solution = (solution + 1LL * prod_i * prod_j % MODULO
           * cnt_words[corner1][corner5] % MODULO * cnt_words[corner2][corner6] % MODULO * cnt_words[corner3][corner7] % MODULO * cnt_words[corner4][corner8]) % MODULO;
      }
    }
    if (0) {
      cout << " ---> ";
      for (auto &word : words[word_length]) {
        cout << word << " ";
      }
      cout << "\n";
    }
  }
  cout << solution << "\n";

  return 0;
}

Compilation message

cubeword.cpp: In function 'int main()':
cubeword.cpp:107:28: warning: narrowing conversion of 'corner1' from 'size_t' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  107 |             all.push_back({corner1, corner2, corner3, corner4, prod});
      |                            ^~~~~~~
cubeword.cpp:107:37: warning: narrowing conversion of 'corner2' from 'size_t' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  107 |             all.push_back({corner1, corner2, corner3, corner4, prod});
      |                                     ^~~~~~~
cubeword.cpp:107:46: warning: narrowing conversion of 'corner3' from 'size_t' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  107 |             all.push_back({corner1, corner2, corner3, corner4, prod});
      |                                              ^~~~~~~
cubeword.cpp:107:55: warning: narrowing conversion of 'corner4' from 'size_t' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  107 |             all.push_back({corner1, corner2, corner3, corner4, prod});
      |                                                       ^~~~~~~
cubeword.cpp:30:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen ("input.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1192 ms 7324 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1192 ms 7324 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1192 ms 7324 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1192 ms 7324 KB Time limit exceeded
2 Halted 0 ms 0 KB -