Submission #1125068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125068		ReaLNero	Languages (IOI10_languages)	C++20	95 / 100	1246 ms	30728 KiB

lang

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

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

#include <map>
#include <set>
#include <vector>

using namespace std;

#define SZ 100

map<int, int> uniq_letter_to_lang;
map<int, int> uniq_digraph_to_lang;
map<long, int> uniq_trigraph_to_lang;
map<long, int> uniq_quatgraph_to_lang;

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

long get_trigraph(int* E){
   return E[0] * 65536L * 65536L + E[1] * 65536L + E[2];
}

long get_quatgraph(int* E){
   return E[0] * 65536L * 65536L * 65536L + E[1] * 65536L * 65536L + E[2] * 65536L + E[3];
}

void excerpt(int *E) {
   int languages_to_unique_letters_shared[56];
   int languages_to_unique_digraphs_shared[56];
   int languages_to_unique_trigraphs_shared[56];
   int languages_to_unique_quatgraphs_shared[56];
   for(int i = 0; i < 56; i++){
      languages_to_unique_letters_shared[i] =
         languages_to_unique_digraphs_shared[i] =
         languages_to_unique_trigraphs_shared[i] =
         languages_to_unique_quatgraphs_shared[i] = 0;
   }

   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]++;
   }
   for(int i = 0; i < SZ - 2; i++){
      auto ite = uniq_trigraph_to_lang.find(get_trigraph(&E[i]));
      if(ite == uniq_trigraph_to_lang.end() or ite->second == -1){
         continue;
      }

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

      languages_to_unique_quatgraphs_shared[ite->second]++;
   }

   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];
      int uniq_trigraph_score = languages_to_unique_trigraphs_shared[i];
      int uniq_quatgraph_score = languages_to_unique_quatgraphs_shared[i];
      double curr_score = (
         uniq_letter_score / 100. +
         uniq_digraph_score / 99. +
         uniq_trigraph_score / 98. +
         uniq_quatgraph_score / 97.
      );

      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 - 2; i++){
      auto ite = uniq_trigraph_to_lang.find(get_trigraph(&E[i]));
      if(ite == uniq_trigraph_to_lang.end()){
         uniq_trigraph_to_lang[get_trigraph(&E[i])] = resp;
         continue;
      } else if(ite->second != resp){
         ite->second = -1;
      }
   }
   for(int i = 0; i < SZ - 3; i++){
      auto ite = uniq_quatgraph_to_lang.find(get_quatgraph(&E[i]));
      if(ite == uniq_quatgraph_to_lang.end()){
         uniq_quatgraph_to_lang[get_quatgraph(&E[i])] = resp;
         continue;
      } else if(ite->second != resp){
         ite->second = -1;
      }
   }
}

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