| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1302980 | goodpjw2008 | Languages (IOI10_languages) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "grader.h"
#include "lang.h"
#define int long long
using namespace std;
const int langs=56,buckets=1<<18,max_ngrams=4;
const float smooth=0.0625,prior=0.75;
const float table[4]={3,4,0.5,25.0};
float expf(float x){
float sum=1.0f;
float term=1.0f;
for(int i = 1; i <= 30; i++){
term*=x/i;
sum+=term;
}
return sum;
}
static inline __attribute__((always_inline)) float logf(float x){
for(int i = 0; i < 10; i++){
x-=(expf(x)-x)/expf(x);
}
return x;
}
struct naivebayes{
signed cnt[langs][buckets][4];
signed total[langs][4];
void train(signed *E, int L){
for(int i = 0; i < 100; i++){
int h=0;
for(int j = 0; j < max_ngrams; j++){
if(i+j>=100)break;
h=(h*283+E[i+j])&(buckets-1);
cnt[L][h][j]++;
total[L][j]++;
}
}
}
signed predict(signed *E){
float best=-1e300;
int blang=0,sum=0;
for(int i = 0; i < langs; i++)sum+=total[i][0]+total[i][1]+total[i][2]+total[i][3];
for(int L = 0; L < langs; L++){
float prob=logf((total[L][0]+total[L][1]+total[L][2]+total[L][3]+prior)/(sum+prior*langs));
for(int i = 0; i < 100; i++){
int h=0;
for(int j = 0; j < max_ngrams; j++){
if(i+j>=100)break;
h=(h*283+E[i+j])&(buckets-1);
prob+=table[j]*logf((cnt[L][h][j]+smooth)/(total[L][j]+smooth*buckets));
}
}
if(prob>=best){
best=prob;
blang=L;
}
}
return blang;
}
}NB;
void excerpt(signed *E){
int qu=language(NB.predict(E));
NB.train(E,qu);
}