Submission #1125060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125060		ReaLNero	Languages (IOI10_languages)	C++20	0 / 100	10090 ms	6904 KiB

lang

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

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

#include <map>

using namespace std;

#define SZ 100

int prev[1100000];

map<int, int> uniq_letter_to_lang;
map<int, int> uniq_digraph_to_lang;
map<int, int> lang_to_letter_to_frequency[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, map<int, int>& b){
   double dot_product = 0.;
   for(auto &ite : a){
      dot_product += ite.second * b[ite.first];
   }
   dot_product /= norm(a) * norm(b);
   return dot_product;
}

void excerpt(int *E) {
   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, lang_to_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++){
      lang_to_letter_to_frequency[resp][E[i]]++;
   }
}

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