Submission #588224

#	Time	Username	Problem	Language	Result	Execution time	Memory
588224		CaroLinda	Languages (IOI10_languages)	C++14	55 / 100	8499 ms	1680 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 = 100;

using namespace std;
 
int vezes = 0;
int spaceChar = -1;
int freq[MAX_SYMBOLS];
vector< vector<int> > lang;
map<long long, int> mp[MAX];
vector<int> ans;
map<long long, int> curMp;
int foi[MAX_LANGUAGES];

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

void putToMap(map<ll,int> &m, vector<int> &v){
   long long cur = 0;

   m.clear();

   for(auto &e : v){
      if(e == spaceChar){
         m[cur]++;
         cur = 0;
      }
      else cur = ( (cur * PRIME) + e+1 ) % MOD;
   }

   m[cur]++;
}

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

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

   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();

   vezes++;

   if(vezes == MAGIC){
      vezes = 0;

      for(int i = 0; i < lang.size(); i++)
         putToMap(mp[i], lang[i]);
   }
 
   putToMap(curMp, thisVector);

   int tenta = 1;

   if(!lang.empty()){
      vector<pair<int,int> > v;

      int aux = 0;
      int cmpWinner = comp(0);

      for(int i = 1; i < ans.size(); i++){
         int s = comp(i);
         if(s > cmpWinner){
            cmpWinner = s;
            aux = i;
         }
      }

      tenta = ans[aux];
   }

   int ret = language(tenta);

   if( (++foi[ret]) > 5 ) return;

   putToMap(mp[lang.size()], thisVector);
   lang.push_back(thisVector)  ;
   ans.push_back(ret);
}

Compilation message (stderr)

lang.cpp: In function 'void excerpt(int*)':
lang.cpp:71:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |       for(int i = 0; i < lang.size(); i++)
      |                      ~~^~~~~~~~~~~~~
lang.cpp:85:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |       for(int i = 1; i < ans.size(); i++){
      |                      ~~^~~~~~~~~~~~

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