Submission #1018141

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018141		socpite	Languages (IOI10_languages)	C++14	68 / 100	8920 ms	139932 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[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;
   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);
         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;
      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 += 200;
      sum += sum2;
      if(sum > best){
         b2 = sum2;
         best = sum;
         pos = i;
      }
   }
   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);
}

Compilation message (stderr)

lang.cpp: In function 'void excerpt(int*)':
lang.cpp:42:26: warning: variable 'b2' set but not used [-Wunused-but-set-variable]
   42 |    long double best = 0, b2 = 0;
      |                          ^~

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