#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.08,prior=1.0;
const int table[4]={5,6,0,1};
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=log((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]*log((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);
}
