| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1353860 | FaresSTH | Languages (IOI10_languages) | C++20 | 0 ms | 0 KiB |
#include "lang.h"
#include <map>
// We use 'static' so the data persists through all 10,000 calls.
// 1. Unigram frequency: How often does this number appear?
static int unigram[56][65536];
// 2. Bigram frequency: How often do these TWO numbers appear in a row?
// Since 65536 * 65536 is too big for an array, we use a map.
// To save speed/memory, we'll pack the two 16-bit numbers into one 32-bit long.
static std::map<int, int> bigram[56];
void excerpt(int E[]) {
int best_lang = 0;
double max_score = -1.0;
for (int l = 0; l < 56; l++) {
double current_score = 0;
for (int i = 0; i < 100; i++) {
// Add score for the single character
current_score += unigram[l][E[i]];
// Add score for the pair of characters (Bigram)
if (i > 0) {
// Combine two 16-bit numbers into one 32-bit key
int key = (E[i-1] << 16) | E[i];
if (bigram[l].count(key)) {
// Bigrams are much more "valuable" for identification,
// so we give them a higher weight (multiplied by 5).
current_score += bigram[l][key] * 5;
}
}
}
if (current_score > max_score) {
max_score = current_score;
best_lang = l;
}
}
// Call language() exactly once and get the true answer
int actual_l = language(best_lang);
// Update our memory with the truth
for (int i = 0; i < 100; i++) {
unigram[actual_l][E[i]]++;
if (i > 0) {
int key = (E[i-1] << 16) | E[i];
bigram[actual_l][key]++;
}
}
}