Submission #832829

#	Time	Username	Problem	Language	Result	Execution time	Memory
832829		finn__	Languages (IOI10_languages)	C++17	61 / 100	2261 ms	132136 KiB

lang

#pragma GCC optimize("O3")

#include <bits/stdc++.h>

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

using namespace std;

constexpr size_t N = 100, L = 56, M = 4;
constexpr int64_t BASE = 998244353, MOD = (1LL << 61) - 1;

int64_t hash_subarray(int *E, size_t n)
{
    int64_t h = 0;
    for (size_t i = 0; i < n; ++i)
        h = (h * (__int128_t)BASE + E[i]) % MOD;
    return h;
}

map<int64_t, array<int, 56>> y[M];
int freq[L];

void excerpt(int *E)
{
    int score[L];
    memset(score, 0, sizeof score);
    for (size_t l = 1; l <= M; ++l)
        for (size_t i = 0; i + l <= N; ++i)
        {
            int64_t h = hash_subarray(E + i, l);
            auto it = y[l - 1].find(h);
            if (it != y[l - 1].end())
            {
                for (size_t j = 0; j < L; ++j)
                    score[j] += it->second[j] * (1 << l);
            }
        }

    size_t ans = 0;
    for (size_t i = 0; i < L; ++i)
        if (freq[i] && (!freq[ans] || (double)score[i] / (double)freq[i] > (double)score[ans] / (double)freq[ans]))
            ans = i;
    size_t correct_ans = language(ans);
    freq[correct_ans]++;

    for (size_t l = 1; l <= M; ++l)
        for (size_t i = 0; i + l <= N; ++i)
        {
            int64_t h = hash_subarray(E + i, l);
            y[l - 1][h][correct_ans]++;
        }
}

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