Submission #519987

#	Time	Username	Problem	Language	Result	Execution time	Memory
519987		tabr	The Big Prize (IOI17_prize)	C++17	100 / 100	56 ms	5632 KiB

prize

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

#ifdef tabr
function<vector<int>(int)> ask;
#else
#include "prize.h"
#endif

int find_best(int n) {
    if (n <= 5000) {
        for (int i = 0; i < n; i++) {
            auto a = ask(i);
            if (a[0] + a[1] == 0) {
                return i;
            }
        }
        assert(false);
    }
    vector<vector<int>> res(n);
    map<int, map<int, int>> mp;
    auto Ask = [&](int i) {
        if (!res[i].empty()) {
            return res[i][0] + res[i][1];
        }
        res[i] = ask(i);
        mp[res[i][0] + res[i][1]][i] = res[i][0];
        return res[i][0] + res[i][1];
    };
    function<void(int, int)> solve = [&](int low, int high) {
        if (low == high) {
            return;
        }
        int mid = (high + low) >> 1;
        if (Ask(mid) == 0) {
            return;
        }
        mp[Ask(mid)][mid] = res[mid][0];
        auto iter = mp[Ask(mid)].find(mid);
        if (iter == mp[Ask(mid)].begin() || prev(iter)->second < res[mid][0]) {
            solve(low, mid);
        }
        if (iter == prev(mp[Ask(mid)].end()) || next(iter)->second > res[mid][0]) {
            solve(mid + 1, high);
        }
    };
    solve(0, n);
    for (int i = 0; i < n; i++) {
        if (!res[i].empty() && Ask(i) == 0) {
            return i;
        }
    }
    return -1;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin >> k;
    vector<int> c(k);
    for (int i = 0; i < k; i++) {
        cin >> c[i];
    }
    int n = accumulate(c.begin(), c.end(), 0);
    vector<int> p;
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < c[i]; j++) {
            p.emplace_back(i);
        }
    }
    mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
    shuffle(p.begin(), p.end(), rng);
    ask = [&](int i) {
        vector<int> res(2);
        for (int j = 0; j < i; j++) {
            if (p[j] < p[i]) {
                res[0]++;
            }
        }
        for (int j = i + 1; j < n; j++) {
            if (p[j] < p[i]) {
                res[1]++;
            }
        }
        return res;
    };
    debug(p);
    int id = find_best(n);
    debug(id);
    assert(p[id] == 0);
    return 0;
}
#endif

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80