Submission #591757

#	Time	Username	Problem	Language	Result	Execution time	Memory
591757		ogibogi2004	Languages (IOI10_languages)	C++14	95 / 100	7320 ms	22216 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];
set<pair<int,pair<int,int> > >srichki1[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;
        }

    }
    int cnt_special[MAX_LANGS];
    memset(cnt_special,0,sizeof(cnt_special));
    for(int i=0;i<100;i++)
    {
        if(where_seen[E[i]].size()==1&&freq[(*where_seen[E[i]].begin())][E[i]]>0.005)
        {
            cnt_special[(*where_seen[E[i]].begin())]++;
        }
    }
    for(int i=0;i<MAX_LANGS;i++)
    {
        if(cnt_special[i]>1)
        {
            guess=i;
        }
    }
    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;
}*/
void excerpt(int *E)
{
    double f1[MAX_SYMBOLS];
    int guess=0;
    int maxs=-1;
    for(int l=0;l<MAX_LANGS;l++)
    {
        if(seen[l]==0)continue;
        int cnts=0;
        /*for(int j=0;j<99;j++)
        {
            if(srichki[l].find({E[j],E[j+1]})!=srichki[l].end())
            {
                cnts++;
            }
        }*/
        for(int j=0;j<98;j++)
        {
            if(srichki1[l].find({E[j],{E[j+1],E[j+2]}})!=srichki1[l].end())
            {
                cnts++;
            }
        }
        if(cnts>maxs)
        {
            maxs=cnts;
            guess=l;
        }
    }
    int l=language(guess);
    /*for(int j=0;j<99;j++)
    {
        srichki[l].insert({E[j],E[j+1]});
    }*/
    for(int j=0;j<98;j++)
    {
        srichki1[l].insert({E[j],{E[j+1],E[j+2]}});
    }
    seen[l]++;
}

Compilation message (stderr)

lang.cpp: In function 'void excerpt(int*)':
lang.cpp:100:12: warning: unused variable 'f1' [-Wunused-variable]
  100 |     double f1[MAX_SYMBOLS];
      |            ^~

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