Submission #588554

#	Time	Username	Problem	Language	Result	Execution time	Memory
588554		CaroLinda	Languages (IOI10_languages)	C++14	91 / 100	5119 ms	5928 KiB

lang

#include <bits/stdc++.h>
 
#include "grader.h"
#include "lang.h"

#define ll long long

const int MAX = 1e4+10; 
const int MAX_SYMBOLS = 65545;
const int MAX_LANGUAGES = 60;
const long long PRIME = 37;
const long long MOD = 1e9+7;
const int MAGIC = -1;

using namespace std;
 
int vezes = 0;
int qtd[MAX_LANGUAGES];
int spaceChar = -1;
int freq[MAX_SYMBOLS];
vector< vector<int> > lang;
vector<int> ans;

//set section
set<ll> setLang[MAX_LANGUAGES];
set<ll> curSet;
set<int> c[MAX_SYMBOLS];


int get(){
   return max_element(freq, freq+MAX_SYMBOLS)-freq;
}

void putToSet(set<ll> &s, vector<int> &v){
   ll cur = 0;

   for(auto &e : v){
      if(e == spaceChar){
         s.insert(cur);
         cur = 0;
      }
      else cur = ( (cur * PRIME) + e+1 ) % MOD;
   }

   s.insert(cur);
}

int comp(int x){
   int ret = 0;

   for(auto &e: setLang[x])
      if(curSet.find(e) != curSet.end())
         ret++;

   return ret;
}
 
void excerpt(int *E) {
   srand(time(0));
  
   vector<int> thisVector;
   for(int i = 0; i < 100; i++){
      thisVector.push_back(E[i]);
      freq[E[i]]++;
   }

   spaceChar = get();
   
   curSet.clear();
   putToSet(curSet, thisVector);

   int s = 0, p = -1;

   for(auto &i: thisVector)
      if(c[i].size() == 1 && !c[i].empty()){
         p = *c[i].begin();
         s = comp(p);

         auto it = c[i].begin();

         for(++it; it != c[i].end(); it++){
            int ss = comp(*it);

            if(ss > s){
               s = ss;
               p = *it;
            }
         }
         break; 
      }

   if(p == -1){
      p = 0;
      for(int i = 0; i < 56; i++){
         int ss = comp(i);

         if(ss > s){
            s = ss;
            p = i;
         }
      }
   }

   int ret = language(p);

   if(qtd[ret]++ <= 50)
      putToSet(setLang[ret], thisVector);

   for(auto &i: thisVector)
      c[i].insert(ret);
}

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