Submission #588546

#	Time	Username	Problem	Language	Result	Execution time	Memory
588546		CaroLinda	Languages (IOI10_languages)	C++14	83 / 100	4090 ms	1260 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;


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 = 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]++ <= 20)
      putToSet(setLang[ret], thisVector);
}

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