oj.uz

답안 #205760

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
205760 2020-02-29T19:10:08 Z jasony123123 Languages (IOI10_languages) C++11
93 / 100
 3585 ms 12408 KB 
#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); }

const int LEN = 100, NLANGS = 56, MXSYMB = 1e6, MAXBUFFER = 200;

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;

unordered_map<ll,int> symbols;

int getSymbol(ll rep){
	auto iter = symbols.find(rep);
	if(iter != symbols.end()) return iter->second;
	int tmp = symbols.size();
	if(tmp >= MXSYMB){
		assert(0);
	}
	return symbols[rep] = tmp;
}

struct LangStats{
	int totalCnt;
	int pattCnt[MXSYMB];
	set<pii> highestOcc; // {cnt, pattern}

	LangStats(){
		totalCnt = 0;
	//	memset(pattCnt, 0, sizeof pattCnt);
	}

	void add(int pattern, int freq){
		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(int pattern){
		if(totalCnt == 0) return 0;
		return 1.0*pattCnt[pattern]/totalCnt;
	}
} ls[NLANGS];

int myDistr[MXSYMB];
void excerpt(int *E) {
	int mytotal = (LEN+LEN-1);
	unordered_set<int> occPatts;

	FOR(i,0,LEN) {
		int tmp = getSymbol(E[i]);
		occPatts.insert(tmp);
		myDistr[tmp]++;
		if(i+1<LEN){
			tmp = getSymbol(E[i]*65536LL+E[i+1]);
			occPatts.insert(tmp);
			myDistr[tmp]++;
		}		
	}

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

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

		for(auto p : occPatts)
			error += abs(1.0*myDistr[p]/mytotal - ls[l].getfreq(p));

		for(auto pp : ls[l].highestOcc)
			if(myDistr[pp.second] == 0)
				error+= ls[l].getfreq(pp.second);
		minn(best, {error, l});
	}

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

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3585 ms 12408 KB Output is correct

Subtask #2
63.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 3491 ms 12388 KB Output is partially correct - 85.41%