oj.uz

Submission #57243

# Submission time Handle Problem Language Result Execution time Memory
57243 2018-07-14T10:46:44 Z Crown Languages (IOI10_languages) C++14
67 / 100
 4982 ms 15120 KB 
#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/ch;
			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] += 1.00*kk.Y/100;
	}
	for(auto &kk : mp[ans])
	{
		kk.Y /= cnt[ans];
	}
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4793 ms 15092 KB Output is correct

Subtask #2
37.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 4982 ms 15120 KB Output is partially correct - 62.81%