oj.uz

Submission #832829

# Submission time Handle Problem Language Result Execution time Memory
832829 2023-08-21T15:51:55 Z finn__ Languages (IOI10_languages) C++17
61 / 100
 2261 ms 132136 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];
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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2253 ms 132084 KB Output is correct

Subtask #2
31.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 2261 ms 132136 KB Output is partially correct - 57.24%