Submission #594860

#	Time	Username	Problem	Language	Result	Execution time	Memory
594860		skittles1412	Languages (IOI10_languages)	C++17	90 / 100	3122 ms	5864 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];

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])));
        }
    }
    if (!(cowng() % 1000)) {
        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]++;
    }
}

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