Submission #1018174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018174		socpite	Languages (IOI10_languages)	C++14	75 / 100	8563 ms	140948 KiB

lang

#include<bits/stdc++.h>
using namespace std;

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

const int lang_cnt = 56;
const int char_cnt = (1<<16);

const int base = 69420;
const int mod = 1e9+7;

int app[char_cnt];
int vis[lang_cnt];

int total_all[char_cnt];
int total_len[lang_cnt], total_word[lang_cnt];

int total[lang_cnt][char_cnt];
int cnt;
map<pair<int, int>, int> ptotal[lang_cnt];
set<int> dict[lang_cnt];

int common, ccnt;

void excerpt(int *E) {
   map<int, int> mp;
   map<pair<int, int>, int> pmt;
   set<int> words;
   int crr = 0, spacecnt = 0;
   for(int i = 0; i < 100; i++){
      mp[E[i]]++;
      if(i)pmt[{E[i-1], E[i]}]++;
      if(E[i] == common){
         words.insert(crr);
         spacecnt++;
         crr = 0;
      }
      else {
         crr = (1LL*crr + E[i])%mod;
      }
   }
   if(crr)words.insert(crr);
   long double best = 0, b2 = 0;
   int pos = 0;
   for(int i = 0; i < lang_cnt; i++){
      if(!vis[i])continue;
      long double sum = 0, sum2 = 0, sum_len = 0, sum_word = 0;
      for(auto v: mp){
         if(v.first == common)continue;
         if(total[i][v.first])sum += (long double)v.second*total[i][v.first]*cnt/app[v.first]/vis[i];
      }
      for(auto v: pmt){
         if(v.first.first == common)continue;
         sum2 += (long double)v.second*v.second*ptotal[i][v.first]/vis[i] / (v.first.second == common ? 5 : 1);
      }
      for(auto v: words)if(dict[i].find(v) != dict[i].end())sum_word += 50;

      sum_len += ((long double)20 - abs((long double)(100 - spacecnt)/(spacecnt+1) - (long double)(total_len[i])/total_word[i]))*10;
      sum = sqrt(sum) + sqrt(sum2) + sqrt(sum_len) + sqrt(sum_word);
      if(sum > best){
         b2 = best;
         best = sum;
         pos = i;
      }
      else if(sum > b2)b2 = sum;
   }
   int id = language(pos);
   // cout << id << " " << best << " " << b2 << "\n";
   // for(auto v: pmt){
   //    if(v.first.first == common || v.first.second == common)continue;
   //    if(ptotal[id][v.first])cout << "PAIR " << v.first.first << " " << v.first.second << endl;
   // }
   if(!vis[id])cnt++;
   vis[id]++;
   for(auto v: mp){
      if(!total[id][v.first])app[v.first]++;
      total[id][v.first] += v.second;
      total_all[v.first] += v.second;
      if(total_all[v.first] > ccnt){
         ccnt = total_all[v.first];
         common = v.first;
      }
   }
   for(auto v: pmt)ptotal[id][v.first]+=v.second*v.second;
   for(auto v: words)dict[id].insert(v);

   total_len[id] += 100 - spacecnt;
   total_word[id] += spacecnt + 1;
}

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