Submission #476823

#	Time	Username	Problem	Language	Result	Execution time	Memory
476823		WeissBlume	Languages (IOI10_languages)	C++17	101 / 100	1421 ms	183680 KiB

lang

#include"grader.h"
#include"lang.h"
#include<queue>
#include<cstdint>
#include<array>
#include<algorithm>
#include<unordered_map>
#define ALL(X) begin(X),end(X)
using namespace std;
constexpr uint32_t n = 100;
constexpr uint32_t m = 56;
constexpr uint32_t k = 5;

array<unordered_map<uint64_t, uint32_t>, k> kgram;
array<unordered_map<uint64_t, int64_t>, k> fs_kgram;
array<unordered_map<uint64_t, array<uint64_t, m>>, k> f_kgram;

void build_kgram(uint8_t k, int32_t *e) {
	kgram[k].clear();
	auto& counter = kgram[k];
	for (int i = k-1; i < n; i++) {
		__uint128_t h = 0;
		for (int j = k-1; j >= 0; j--)
			h = h << 16 | e[i-j];
		++counter[h % 0X9E3779B97F4A7C15UL];
	}
}

void build(int32_t *e) {
	for (int k: {2, 4}) build_kgram(k, e);
}

void update(auto lang) {
	for (int k = 2; k < ::k; k++) if (not kgram[k].empty()) {
		auto const& grams = kgram[k];
		auto& freqs = f_kgram[k];
		auto& fsums = fs_kgram[k];
		for (auto&[gram, count]: grams) {
			freqs[gram][lang] += 1;
			fsums[gram] += count;
		}
	}
}

auto guess() {
	array<double, m> score {};
	for (int k = 2; k < ::k; k++) if (not kgram[k].empty()) {
		auto const& grams = kgram[k];
		auto const& freqs = f_kgram.at(k);
		auto const& fsums = fs_kgram.at(k);
		for (auto&[gram, count]: grams) if (freqs.count(gram)) {
			auto const& freq = freqs.at(gram);
			auto const& sum = fsums.at(gram);
			for (int i = 0; i < m; i++)
				score[i] += count * (freq[i] / (1. + sum));
		}
	}
	return language(max_element(ALL(score)) - begin(score));
}

void excerpt(int32_t *e) {
	build(e);
	update(guess());
}

Compilation message (stderr)

lang.cpp: In function 'void build_kgram(uint8_t, int32_t*)':
lang.cpp:21:22: warning: comparison of integer expressions of different signedness: 'int' and 'const uint32_t' {aka 'const unsigned int'} [-Wsign-compare]
   21 |  for (int i = k-1; i < n; i++) {
      |                    ~~^~~
lang.cpp: At global scope:
lang.cpp:33:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   33 | void update(auto lang) {
      |             ^~~~
lang.cpp: In function 'auto guess()':
lang.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'const uint32_t' {aka 'const unsigned int'} [-Wsign-compare]
   47 |  for (int k = 2; k < ::k; k++) if (not kgram[k].empty()) {
      |                  ~~^~~~~
lang.cpp:54:22: warning: comparison of integer expressions of different signedness: 'int' and 'const uint32_t' {aka 'const unsigned int'} [-Wsign-compare]
   54 |    for (int i = 0; i < m; i++)
      |                    ~~^~~
lang.cpp: In instantiation of 'void update(auto:1) [with auto:1 = int]':
lang.cpp:63:16:   required from here
lang.cpp:34:20: warning: comparison of integer expressions of different signedness: 'int' and 'const uint32_t' {aka 'const unsigned int'} [-Wsign-compare]
   34 |  for (int k = 2; k < ::k; k++) if (not kgram[k].empty()) {
      |                  ~~^~~~~

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