#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
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()) {
| ~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1421 ms |
183524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1404 ms |
183680 KB |
Output is correct - 92.26% |
