Submission #205482

#	Time	Username	Problem	Language	Result	Execution time	Memory
205482		jasony123123	Languages (IOI10_languages)	C++11	0 / 100	10097 ms	7408 KiB

lang

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

#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define v vector
typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

template<class Mt_T, class Int_T> struct Rand{
	Mt_T mt;
	Rand(){
		mt = Mt_T(chrono::steady_clock::now().time_since_epoch().count());
	}
	inline Int_T operator()(Int_T a, Int_T b){
		return uniform_int_distribution<Int_T>(a,b)(mt);
	}
};
Rand<mt19937_64, ll> rng;

const int LEN = 100, NLANGS = 56;
map<ll,int> langdistr[NLANGS];
int langtotal[NLANGS];


void excerpt(int *E) { 
	map<ll,int> mydistr;
	FOR(i,0,LEN) mydistr[E[i]]++;
	FOR(i,0,LEN-1) mydistr[0LL+E[i]*65536+E[i+1]]++;
	int mytotal = (LEN+LEN-1);

	pair<double, int> best = {1.0, rng(0,NLANGS-1)}; //1e18-80, 1-80.13 e-2-1.78*/

	FOR(l,0,NLANGS) if(!langdistr[l].empty()){
		double error = 0;
		for(auto pp : mydistr){
			if(langdistr[l].find(pp.first)!=langdistr[l].end())
				error += abs(1.0*pp.second/mytotal - 1.0*langdistr[l][pp.first]/langtotal[l]);
			else
				error += 1.0*pp.second/mytotal;
		}
		minn(best, {error, l});
	}

	int ans = language(best.second);
	for(auto pp : mydistr)
		langdistr[ans][pp.first] += pp.second;
	langtotal[ans] += mytotal;
}

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