Submission #57241

#	Time	Username	Problem	Language	Result	Execution time	Memory
57241		Crown	Languages (IOI10_languages)	C++14	0 / 100	5101 ms	15252 KiB

lang

#include "grader.h"
#include "lang.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;

#define SZ 100
#define lng 55
#define ch 65535

const ll all = 1LL*ch*ch;

map<ll, double> mp[60];
int cnt[60];
map<ll, int> freq;

void excerpt(int *E)
{
	freq.clear();
	for(int i = 0; i< 100; i++)
	{
		ll help = E[i];
		freq[help]++;
	}
	int best = -1;
	double bestdiff = 1e18;
	for(int lang = 0; lang<= 55; lang++)
	{
		double diff = 0;
		for(auto kk : freq)
		{
			ll chunk = kk.X;
			double f = 1.00*kk.Y/100;
			double here;
			if(cnt[lang] == 0) here = 1.00/all;
			else here = mp[lang][chunk];
			diff += (here-f)*(here-f);
		}
		if(diff< bestdiff)
		{
			bestdiff = diff;
			best = lang;
		}
	}
	//printf("best is %d\n", best);
	int ans = language(best);
	for(auto &kk : mp[ans])
	{
		kk.Y *= cnt[ans];
	}
	cnt[ans]++;
	for(auto kk : freq)
	{
		mp[ans][kk.X] += kk.Y;
	}
	for(auto &kk : mp[ans])
	{
		kk.Y /= cnt[ans];
	}
}

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