Submission #588214

#	Time	Username	Problem	Language	Result	Execution time	Memory
588214		CaroLinda	Languages (IOI10_languages)	C++14	46 / 100	1978 ms	7424 KiB

lang

#include <bits/stdc++.h>

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

const int MAX_SYMBOLS = 65545;
const int MAX_LANGUAGES = 60;

using namespace std;

int freq[MAX_SYMBOLS];
vector<int> lan[MAX_SYMBOLS];
vector< vector<int> > samples[MAX_LANGUAGES];
map<int,int> mp[MAX_LANGUAGES];
map<int,int> curMp;

int compability(int lang){
   int ret = 0;

   for(auto &e : mp[lang])
      ret += min(e.second, curMp[e.first]);

   return ret;
}

void excerpt(int *E) {
   srand(time(0));

   curMp.clear();

   vector<int> thisVector;
   for(int i = 0; i < 100; i++)
      thisVector.push_back(E[i]);

   vector<int> space(56);
   iota(space.begin(),space.end(),0);

   for(int i = 0; i < 100; i++){
      freq[E[i]]++;
      curMp[E[i]]++;
   }

   for(int i = 0; i < 100; i++){
      if(lan[E[i]].empty())
         continue;

      if(lan[E[i]].size() < space.size())
         swap(space, lan[E[i]]);
   }

   vector<pair<int,int> > aux;
   for(auto &e : space) 
      aux.push_back(make_pair(compability(e), e));

   sort(aux.begin(),aux.end());

   int actualAnswer = language(aux.back().second);

   samples[actualAnswer].push_back(thisVector);
   mp[actualAnswer].clear();

   for(auto &e : thisVector)
      mp[actualAnswer][e]++;

   for(int i = 0; i < 100; i++){
      vector<int> &ptr = lan[E[i]];

      ptr.push_back(actualAnswer);
      
      sort(ptr.begin(), ptr.end());

      ptr.erase(unique(ptr.begin(),ptr.end()), ptr.end());
   }
}

• Subtask 1: 30 / 30
• Subtask 2: 16 / 80