제출 #706567

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
706567		SamNguyen	Languages (IOI10_languages)	C++14	83 / 100	704 ms	14612 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) {
		for (int x = 0; x < NUM_LANG; x++) 
		for (int c = 0; c < NUM_CHAR; c++)
			freq[x][c] = 0;
		IS_FIRST_RUN = false;
	}

	Vector<NUM_LANG> vec;
	map<int, int> mp;
	for (int i = 0; i < LEN; i++) 
		mp[txt[i]]++;

	for (const auto &e : mp) {
		int ch, cnt;
		tie(ch, cnt) = e;
		
		Vector<NUM_LANG> delta;
		for (int x = 0; x < NUM_LANG; x++) 
			delta[x] = freq[x][ch];

		vec = vec + delta.unify() * pow(cnt, 0.8);
	}

	vec = vec.unify();

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

	ld best = -1e20;
	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;
	}

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

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