Submission #301280

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
301280	2020-09-17T19:45:41 Z	fishy15	Languages (IOI10_languages)	C++17	80 / 100	8041 ms	133320 KB

lang

#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <array>
#include <algorithm>
#include <utility>
#include <map>
#include <queue>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <unordered_map>
#include "lang.h"
#include "grader.h"

#define ll long long
#define ld long double
#define eps 1e-8
#define MOD 1000000007

#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f

// change if necessary
#define MAXN 70000

using namespace std;

// replace this back when submit
const int LEN = 100;
const int LANGS = 56;

struct hash_pair {
    template <class T, class U>
    size_t operator() (const pair<T, U> &p) const {
        auto h1 = p.first;
        auto h2 = p.second;
        return h1 + (1 << 16) * h2;
    }
};

using m = unordered_map<int, int>;
using mm = unordered_map<pair<int, int>, int, hash_pair>;

struct val {
    int tot;
    int freq1[MAXN];
    mm freq2;
    val() : tot(0) {}
    ld qry(const m &cnt1, const mm &cnt2) {
        if (tot == 0) return INFLL;
        ld ans = 0;
        for (auto p : cnt1) {
            ld actual_f = 1.0 * freq1[p.first] / tot;
            ld given_f = 1.0 * p.second / LEN;
            ld val = fabs(actual_f - given_f) * 100;
            ans += val * val;
        }
        for (auto p : cnt2) {
            ld actual_f = 1.0 * freq2[p.first] / tot;
            ld given_f = 1.0 * p.second / LEN;
            ld val = fabs(actual_f - given_f) * 100;
            ans += val * val;
        }
        return ans;
    }
    void upd(int arr[LEN]) {
        tot += LEN;
        for (int i = 0; i < LEN; i++) {
            freq1[arr[i]]++;
        }
        for (int i = 0; i < LEN - 1; i++) {
            freq2[{arr[i], arr[i + 1]}]++;
        }
    }
};

val langs[LANGS];

void excerpt(int arr[LEN]) {
    ld min_val = INFLL;
    int ans = 0;
    m cnt1;
    mm cnt2;
    for (int i = 0; i < LEN; i++) cnt1[arr[i]]++;
    for (int i = 0; i < LEN - 1; i++) {
        cnt2[{arr[i], arr[i + 1]}]++;
    }
    for (int i = 0; i < LANGS; i++) {
        ld val = langs[i].qry(cnt1, cnt2);
        if (val < min_val) {
            min_val = val;
            ans = i;
        }
    }

    int correct = language(ans);
    langs[correct].upd(arr);
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8041 ms	133320 KB	Output is correct

Subtask #2

50.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	7963 ms	132928 KB	Output is partially correct - 73.62%