Submission #591742

#	Time	Username	Problem	Language	Result	Execution time	Memory
591742		ogibogi2004	Languages (IOI10_languages)	C++14	71 / 100	6039 ms	34444 KiB

lang

#include <bits/stdc++.h>

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

const int MAX_SYMBOLS = 65545;
const int MAX_LANGS=56;
using namespace std;

double freq[MAX_LANGS][MAX_SYMBOLS];
int seen[MAX_LANGS];
unordered_set<int>symbols[MAX_LANGS];
set<int>where_seen[MAX_SYMBOLS];
set<pair<int,int> >srichki[MAX_LANGS];
double weight[MAX_SYMBOLS];
int cnt_seen=0;
void excerpt(int *E)
{
    double f1[MAX_SYMBOLS];
    unordered_set<int>s1;
    for(int i=0;i<100;i++)s1.insert(i);
    for(int i=0;i<MAX_SYMBOLS;i++)f1[i]=0;
    if(cnt_seen==0)
    {
        for(int i=0;i<MAX_SYMBOLS;i++)weight[i]=1;
    }
    for(int i=0;i<100;i++)
    {
        f1[E[i]-1]+=1.0;
    }
    for(int i=0;i<MAX_SYMBOLS;i++)
    {
        f1[i]/=100.0;
    }
    int guess=0;
    double mindiff=2e9;
    vector<pair<double,int> >poss;
    for(int i=0;i<MAX_LANGS;i++)
    {
        if(seen[i]==0)continue;
        double err=0;
        for(auto j:symbols[i])
        {
            //if(where_seen[j].size()>50)continue;
            if(freq[i][j]>0&&f1[j]>0)err+=(freq[i][j]-f1[j])*weight[j];
            else err+=1.1*(freq[i][j]-f1[j])*weight[j];
            //if(freq[i][j]==0&&f1[j]>0)err+=1e5;
        }
        for(auto j:s1)
        {
            //if(where_seen[j].size()>50)continue;
            if(freq[i][j]==0)err+=1.1*f1[j]*weight[j];
            //if(freq[i][j]==0&&f1[j]>0)err+=1e5;
        }
        if(err<mindiff)
        {
            guess=i;
            mindiff=err;
        }

    }
    for(int i=0;i<100;i++)
    {
        if(where_seen[E[i]].size()==1&&freq[(*where_seen[E[i]].begin())][E[i]]>0.01)
        {
            guess=(*where_seen[E[i]].begin());
            break;
        }
    }
    int l=language(guess);
    int s=seen[l];
    double c1=1.0*s/(s+1.0);
    double c2=1.0/(s+1.0);
    for(int i=0;i<MAX_SYMBOLS;i++)
    {
        if(f1[i]>0)where_seen[i].insert(l);
        if(f1[i]>0&&freq[l][i]==0)symbols[l].insert(i);
        freq[l][i]=freq[l][i]*c1+f1[i]*c2;
    }
    cnt_seen++;
    for(int j=0;j<100;j++)
    {
        int i=E[j];
        if(where_seen[i].size()>0)weight[i]=1.0;
    }
    //for(int j=0;j<99;j++)srichki[l].insert({E[j],E[j+1]});
    seen[l]+=1;
}

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