oj.uz

Submission #635302

# Submission time Handle Problem Language Result Execution time Memory
635302 2022-08-26T00:24:18 Z pedroslrey Languages (IOI10_languages) C++17
74 / 100
 2779 ms 6920 KB 
#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 SZ = 4;
const int EPS = 2;

int alfa[MAXN][LANG];
set<int> appear[LANG];
int tmp1[MAXN], tmp2[MAXN];
int cnt[LANG];

int iteration;

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

	for (int *it = E; it < E + 100; ++it) {
		++tmp1[*it]; ++tmp2[*it];
	}

	set<int> xs;
	for (int i = 0; i < 100-SZ; ++i) {
		bool ok = true;
		for (int j = i; j < i + SZ; ++j)
			if (tmp1[E[j]] >= EPS) ok = false;

		if (ok) {
			for (int j = i; j < i + SZ; ++j)
				--tmp2[E[j]];
			i += 5;
		}
		else xs.insert(E[i]);
	}

	int guess = 1;
	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] - tmp2[k];
			val += x*x;
		}
		for (int k: appear[i]) {
			if (xs.count(k)) continue;
			ld x = ((ld)alfa[k][i])/cnt[i] - tmp2[k];
			val += x*x;
		}

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

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2779 ms 6852 KB Output is correct

Subtask #2
44.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 2607 ms 6920 KB Output is partially correct - 68.62%