Submission #706560

#	Time	Username	Problem	Language	Result	Execution time	Memory
706560		SamNguyen	Languages (IOI10_languages)	C++14	80 / 100	581 ms	14676 KiB

lang

#include <stdlib.h>
#include <stdio.h>

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

#include <bits/stdc++.h>
using namespace std;
using ld = long double;

template <class T1, class T2>
inline bool maximise(T1 &x, T2 y) {
	if (x < y) { x = y; return true; }
	return false;
}

template <int DIM>
struct Vector {
private:
	ld x[DIM];

public:
	Vector() {
		for (int i = 0; i < DIM; i++)
			x[i] = 0;
	}

	inline ld& operator [] (int i) {
		return x[i];
	}

	inline ld operator [] (int i) const {
		return x[i];
	}

	Vector operator + (const Vector &oth) const { 
		Vector res;
		for (int i = 0; i < DIM; i++)
			res.x[i] = x[i] + oth.x[i];
		return res;
	}

	Vector operator - (const Vector &oth) const { 
		Vector res;
		for (int i = 0; i < DIM; i++)
			res.x[i] = x[i] - oth.x[i];
		return res;
	}

	Vector operator * (ld k) const { 
		Vector res;
		for (int i = 0; i < DIM; i++)
			res.x[i] = x[i] * k;
		return res;
	}

	inline ld abs() const {
		ld res = 0;
		for (int i = 0; i < DIM; i++)
			res += x[i] * x[i];
		return sqrtl(res);
	}

	inline Vector unify() {
		ld len = abs();
		if (len == 0)
			return *this;
		return (*this) * (1.0 / len);
	}
};

template <int DIM>
ld dot(const Vector<DIM> &A, const Vector<DIM> &B) {
	ld res = 0;
	for (int i = 0; i < DIM; i++)
		res += A[i] * B[i];
	return res;
}

const int LEN = 100;
const int NUM_LANG = 56;
const int NUM_CHAR = 65356;

bool IS_FIRST_RUN = true;
int freq[NUM_LANG][NUM_CHAR];

void excerpt(int *txt) {
	if (IS_FIRST_RUN) {
		memset(freq, 0, sizeof freq);
		IS_FIRST_RUN = false;
	}

	Vector<NUM_LANG> vec;
	set<int> chars(txt, txt + LEN);
	for (int c : chars) {
		Vector<NUM_LANG> delta;
		for (int x = 0; x < NUM_LANG; x++) 
			delta[x] += freq[x][c];

		vec = vec + delta.unify();
	}
	vec = vec.unify();

	/*
	cout << "vec = ";
	for (int x = 0; x < NUM_LANG; x++) 
		cout << vec[x] << " ";
	cout << endl;
	*/

	ld best = -1.1;	
	int lang = -1;
	for (int x = 0; x < NUM_LANG; x++) {
		Vector<NUM_LANG> u;
		u[x] = 1;
		
		if (maximise(best, dot(u, vec)))
			lang = x;
	}

	//cout << "lang = " << lang << endl;

	int ans = language(lang);
	for (int i = 0; i < LEN; i++) {
		freq[ans][txt[i]] += 2;
		freq[lang][txt[i]] -= 1;
	}
}

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