Submission #635298

#	Time	Username	Problem	Language	Result	Execution time	Memory
635298		pedroslrey	Languages (IOI10_languages)	C++17	74 / 100	3085 ms	7564 KiB

lang

#include <bits/stdc++.h>

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

using namespace std;
using ld = long double;

const int MAXN = 65545;
const int LANG = 66;
const int WAIT = 200;

int alfa[MAXN][LANG];
set<int> appear[LANG];
int tmp[MAXN];
int cnt[LANG];

int iteration;

void excerpt(int *E) {
	//cerr << "\r" << iteration;
	++iteration;

	int guess = 1;
	if (iteration > WAIT) {
		set<int> xs;
		for (int *it = E; it < E + 100; ++it) {
			++tmp[*it];
			xs.insert(*it);
		}

		ld best = 1e18;
		for (int i = 0; i < 56; ++i) {
			if (!cnt[i]) continue;
			ld val = 0;
			for (int k: xs) {
				ld x = ((ld)alfa[k][i])/cnt[i] - tmp[k];
				val += x*x;
			}
			for (int k: appear[i]) {
				if (xs.count(k)) continue;
				ld x = ((ld)alfa[k][i])/cnt[i] - tmp[k];
				val += x*x;
			}

			if (val < best) {
				best = val;
				guess = i;
			}
		}

		for (int *it = E; it < E + 100; ++it)
			--tmp[*it];
	}

	int lan = language(guess);
	for (int *it = E; it < E + 100; ++it) {
		++alfa[*it][lan];
		appear[lan].insert(*it);
	}
	++cnt[lan];
}

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