oj.uz

Submission #832832

# Submission time Handle Problem Language Result Execution time Memory
832832 2023-08-21T15:52:40 Z finn__ Languages (IOI10_languages) C++17
93 / 100
 2344 ms 132116 KB 
#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];
int64_t freq[L];

void excerpt(int *E)
{
    int64_t 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 * 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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2254 ms 132116 KB Output is correct

Subtask #2
63.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 2344 ms 132100 KB Output is partially correct - 84.93%