oj.uz

Submission #235439

# Submission time Handle Problem Language Result Execution time Memory
235439 2020-05-28T09:26:59 Z dolphingarlic Languages (IOI10_languages) C++14
94 / 100
 9286 ms 158780 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("sse4,avx2,fma,avx")
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

#include "grader.h"
#include "lang.h"

const int SZ = 100, LANGS = 56;
const float LETTER_WEIGHT = 1, BIGRAM_WEIGHT = 2, TRIGRAM_WEIGHT = 3;

unordered_map<ll, float> prev_letters[LANGS];
int prev_cnt[LANGS];

void excerpt(int *E) {
   unordered_map<ll, float> curr_letters;
   FOR(i, 2, SZ) {
      curr_letters[E[i]]++;
      curr_letters[(E[i - 1] << 15) + E[i]]++;
      curr_letters[(E[i - 2] << 31) + (E[i - 1] << 15) + E[i]]++;
   }
   
   int best_lang = 0;
   float best_diff = 1e18;
   FOR(i, 0, LANGS) if (prev_cnt[i]) {
      float curr_diff = 0;
      for (pair<ll, float> j : curr_letters) {
         curr_diff += __builtin_popcount(j.first) * abs(j.second - (prev_letters[i][j.first] / prev_cnt[i]));
      }
      if (curr_diff < best_diff) {
         best_diff = curr_diff;
         best_lang = i;
      }
   }

   int correct = language(best_lang);
   prev_cnt[correct]++;
   for (pair<ll, float> i : curr_letters) {
      prev_letters[correct][i.first] += i.second;
   }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8786 ms 158772 KB Output is correct

Subtask #2
64.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 9286 ms 158780 KB Output is partially correct - 85.82%