Submission #205526

#	Time	Username	Problem	Language	Result	Execution time	Memory
205526		jasony123123	Languages (IOI10_languages)	C++11	0 / 100	10009 ms	5584 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 double FREQFACTOR = 10;

struct LangStats{
	static const int MAXBUFFER = 100;

	map<ll,int> pattCnt;
	int totalCnt = 0;
	set<pair<int, ll>> highestOcc; // {cnt, pattern}

	void add(ll pattern, int freq){ // O(LOG[10000*200])
		totalCnt += freq;
		highestOcc.erase({pattCnt[pattern], pattern});
		pattCnt[pattern] += freq;
		highestOcc.insert({pattCnt[pattern], pattern});
		while(highestOcc.size() > MAXBUFFER)
			highestOcc.erase(highestOcc.begin());
	}

	double getfreq(ll pattern){ // O(LOG[10000*200])
		if(pattCnt.find(pattern) == pattCnt.end()) return 0;
		else return FREQFACTOR*pattCnt[pattern]/totalCnt;
	}
};


const int LEN = 100, NLANGS = 56;

LangStats ls[NLANGS];

void excerpt(int *E) {  // 56*(200+MAXBUFFER)*LOG[10000*200]
	map<ll,int> myDistr;
	int mytotal = (LEN+LEN-1);

	FOR(i,0,LEN) myDistr[E[i]]++;
	FOR(i,0,LEN-1) myDistr[E[i]*65536LL+E[i+1]]++;

	pair<double, int> best = {1e18, rng(0,NLANGS-1)};

	FOR(l,0,NLANGS) if(ls[l].totalCnt > 0){
		double error = 0;

		for(auto pp : myDistr)
			error += abs(FREQFACTOR*pp.second/mytotal - ls[l].getfreq(pp.first));

		for(auto pp : ls[l].highestOcc) 
			if(myDistr.find(pp.second) == myDistr.end())
				error += ls[l].getfreq(pp.second);

		minn(best, {error, l});
	}

	int ans = language(best.second);
	for(auto pp : myDistr)
		ls[ans].add(pp.first, pp.second);
}

/*
int nsamp = 0;
array<int, LEN> samples[10000];
v<int> correct[NLANGS];

double fitness(int sampid, int langid){ // higher is more similar
	double total = 0;
	int cnt = 0;

	auto dot_product = [&](int sa, int sb){
		double ret = 0;
		double dena = 0, denb = 0;
		FOR(i,0,LEN) {
			dena += 1.0*samples[sa][i]*samples[sa][i];
			denb += 1.0*samples[sb][i]*samples[sb][i];
		}
		dena = sqrt(dena), denb = sqrt(denb);

		FOR(i,0,LEN) ret += 1.0*samples[sa][i]*samples[sb][i]/(dena*denb+1e-5);
		ret = abs(ret);
		return ret;
	};

	if(correct[langid].size() < MXPROCESS){
		for(auto id : correct[langid])
			total += dot_product(sampid, id), cnt++;
	}
	else{
		FOR(r,0,MXPROCESS){
			int i = rng(0, correct[langid].size()-1);
			total += dot_product(sampid, correct[langid][i]), cnt++;
		}
	}

	return total/cnt;
}

void excerpt(int *E) { 
	FOR(i,0,LEN) samples[nsamp][i] = E[i];
	nsamp++;

	pair<double, int> guess = {-1, rand()%NLANGS};
	FOR(l,0,NLANGS) if(!correct[l].empty())
		maxx(guess, {fitness(nsamp-1, l), l});

	int ans = language(guess.second);
	correct[ans].push_back(nsamp-1);
}
*/

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