Submission #588561

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
588561	2022-07-03T14:20:34 Z	CaroLinda	Languages (IOI10_languages)	C++14	96 / 100	3699 ms	9156 KB

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];
set<int> setChar[MAX_LANGUAGES];
set<int> curChar;


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: curSet)
      if(setLang[x].find(e) != setLang[x].end())
         ret+=6;

   int diff = 0;

   for(auto &e: curChar){
      if(setChar[x].find(e) != setChar[x].end())
         ret++;    
   }  

   return ret;
}

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

   for(auto &e: curChar)
      if(setChar[x].find(e) != setChar[x].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);

   curChar.clear();
   for(auto &e: thisVector)
      curChar.insert(e);

   int s = 0, p = -1;

   vector<int> v;

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

         v.push_back(p);

         continue;

         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(!v.empty()){
      s = comp(v[0]);
      p = v[0];
      
      for(auto &e: v){
         int ss = comp(e);
         if(ss > s){
            s = ss;
            p = e;
         }
      }

      //p = max_element(f.begin(),f.end())-f.begin();
   }

   if(p == -1){
      p = 0;
      s = comp(0);
      for(int i = 1; i < 56; i++){
         if(compChar(i) < 15) continue;

         int ss = comp(i);

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

   int ret = language(p);

   putToSet(setLang[ret], thisVector);

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

Compilation message

lang.cpp: In function 'int comp(int)':
lang.cpp:57:8: warning: unused variable 'diff' [-Wunused-variable]
   57 |    int diff = 0;
      |        ^~~~

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3699 ms	9156 KB	Output is correct

Subtask #2

66.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	3668 ms	9140 KB	Output is partially correct - 88.25%