Submission #594875

#	Time	Username	Problem	Language	Result	Execution time	Memory
594875		skittles1412	Languages (IOI10_languages)	C++17	101 / 100	3765 ms	39220 KiB

lang

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

using ld = long double;

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

int language(int L);

mt19937 cowng(chrono::steady_clock::now().time_since_epoch().count());

int cnts[65536][57], occur[56], space, totw;
map<vector<int>, array<int, 57>> wcnts;

void excerpt(int* arr) {
    ld poss[56];
    fill(begin(poss), end(poss), 1);
    for (int i = 0; i < 100; i++) {
        for (int j = 0; j < 56; j++) {
            poss[j] += log(
                max(ld(1e-5), ld(cnts[arr[i]][j]) / max(1, cnts[arr[i]][56]) /
                                  max(1, occur[j])));
        }
    }
    vector<vector<int>> words;
    for (int l = 0, r = 0; l < 100; l = r) {
        for (; l < 100 && arr[l] == space; l++)
            ;
        if (l == 100) {
            break;
        }
        for (r = l; r < 100 && arr[r] != space; r++)
            ;
        if (r - l < 1) {
            continue;
        }
        words.emplace_back(arr + l, arr + r);
    }
    totw += sz(words);
    for (auto& a : words) {
        auto& cur = wcnts[a];
        int tot = accumulate(begin(cur), end(cur), 0);
        for (int i = 0; i < 56; i++) {
            poss[i] += 800 * ld(cur[i]) / max(1, tot) / max(1, occur[i]);
        }
    }
    if (!(cowng() % 1000)) {
        vector<pair<int, vector<int>>> most;
        for (auto& [k, w] : wcnts) {
            most.emplace_back(accumulate(begin(w), end(w), 0), k);
        }
        sort(begin(most), end(most), greater<>());
        for (int i = 0; i < 10; i++) {
            cerr << double(most[i].first) / totw;
            for (auto& a : most[i].second) {
                cerr << " " << char(a);
            }
            cerr << endl;
        }
        for (int i = 0; i < 56; i++) {
            cerr << poss[i] << " \n"[i == 55];
        }
    }
    // int pick = cowng() % accumulate(begin(poss), end(poss), 0), psum = 0,
    // guess; for (int i = 0; i < 56; i++) {
    //     psum += poss[i];
    //     if (pick < psum) {
    //         guess = i;
    //         break;
    //     }
    // }
    // double opt = *max_element(begin(poss), end(poss));
    // vector<int> cands;
    // for (int i = 0; i < 56; i++) {
    //     if (poss[i] > opt - 0.0001) {
    //         cands.push_back(i);
    //     }
    // }
    // int ans = language(cands[cowng() % sz(cands)]);
    int ans = language(max_element(begin(poss), end(poss)) - poss);
    occur[ans]++;
    for (int i = 0; i < 100; i++) {
        cnts[arr[i]][ans]++;
        cnts[arr[i]][56]++;
        if (cnts[arr[i]][56] > cnts[space][56]) {
            space = arr[i];
        }
    }
    for (auto& a : words) {
        wcnts[a][ans]++;
    }
}

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