Submission #1125061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125061		ReaLNero	Languages (IOI10_languages)	C++20	63 / 100	555 ms	16696 KiB

lang

#include <stdlib.h>
#include <stdio.h>
#include <iostream>

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

#include <map>

using namespace std;

#define SZ 100

map<int, int> uniq_letter_to_lang;
map<int, int> uniq_digraph_to_lang;
int lang_to_letter_to_frequency[56][65536];
double norm_f[56];

int get_digraph(int* E){
   return E[0] * 65536 + E[1];
}

double norm(map<int, int>& m){
   double w = 0;
   for(auto ite : m){
      w += ite.second * ite.second;
   }
   return w;
}

double get_dot_product(map<int, int>& a, int b){
   double dot_product = 0.;
   for(auto &ite : a){
      dot_product += ite.second * lang_to_letter_to_frequency[b][ite.first];
   }
   dot_product /= norm(a) * norm_f[b];
   return dot_product;
}

int test_cases = 0;
void excerpt(int *E) {
   if(test_cases == 0){
      for(int i = 0; i < 56; i++){
         norm_f[i] = 0.;
         for(int j = 0; j < 65536; j++){
            lang_to_letter_to_frequency[i][j] = 0;
         }
      }
   }
   test_cases++;
   map<int, int> languages_to_unique_letters_shared;
   map<int, int> languages_to_unique_digraphs_shared;

   for(int i = 0; i < SZ; i++){
      auto ite = uniq_letter_to_lang.find(E[i]);
      if(ite == uniq_letter_to_lang.end() or ite->second == -1){
         continue;
      }

      languages_to_unique_letters_shared[ite->second]++;
   }
   for(int i = 0; i < SZ - 1; i++){
      auto ite = uniq_digraph_to_lang.find(get_digraph(&E[i]));
      if(ite == uniq_digraph_to_lang.end() or ite->second == -1){
         continue;
      }

      languages_to_unique_digraphs_shared[ite->second]++;
   }
   map<int, int> letter_to_frequency;
   for(int i = 0; i < SZ; i++){
      letter_to_frequency[E[i]]++;
   }

   int best_lang = 0;
   double best_score = -1.;
   for(int i = 0; i < 56; i++){
      int uniq_letter_score = languages_to_unique_letters_shared[i];
      int uniq_digraph_score = languages_to_unique_digraphs_shared[i];

      double curr_score = uniq_letter_score * 4. + uniq_digraph_score * 2;

      if(curr_score + 1. >= best_score){
         double dot_product = get_dot_product(letter_to_frequency, i);
         curr_score += dot_product * 1.;
      }

      if(best_score < curr_score){
         best_lang = i;
         best_score = curr_score;
      }
   }

   int resp = language(best_lang);

   for(int i = 0; i < SZ; i++){
      auto ite = uniq_letter_to_lang.find(E[i]);
      if(ite == uniq_letter_to_lang.end()){
         uniq_letter_to_lang[E[i]] = resp;
         continue;
      } else if(ite->second != resp){
         ite->second = -1;
      }
   }
   for(int i = 0; i < SZ - 1; i++){
      auto ite = uniq_digraph_to_lang.find(get_digraph(&E[i]));
      if(ite == uniq_digraph_to_lang.end()){
         uniq_digraph_to_lang[get_digraph(&E[i])] = resp;
         continue;
      } else if(ite->second != resp){
         ite->second = -1;
      }
   }

   for(int i = 0; i < SZ; i++){
      norm_f[resp] -= lang_to_letter_to_frequency[resp][E[i]] * lang_to_letter_to_frequency[resp][E[i]];
      lang_to_letter_to_frequency[resp][E[i]]++;
      norm_f[resp] += lang_to_letter_to_frequency[resp][E[i]] * lang_to_letter_to_frequency[resp][E[i]];
   }
}

• Subtask 1: 30 / 30
• Subtask 2: 33 / 70