Submission #519981

#	Time	Username	Problem	Language	Result	Execution time	Memory
519981		tabr	The Big Prize (IOI17_prize)	C++17	97.39 / 100	58 ms	5304 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);
    auto Ask = [&](int i) {
        if (!res[i].empty()) {
            return res[i][0] + res[i][1];
        }
        res[i] = ask(i);
        return res[i][0] + res[i][1];
    };
    int mx = -1;
    function<void(int, int, int)> solve = [&](int low, int high, int cnt) {
        if (cnt == 0 || low == high) {
            return;
        }
        assert(cnt > 0);
        assert(cnt <= high - low);
        assert(Ask(low - 1) == mx);
        int mid = (high + low) >> 1;
        for (int i = mid; i < high; i++) {
            if (Ask(i) == mx) {
                int c = res[i][0] - res[low - 1][0] - (i - mid);
                solve(low, mid, c);
                solve(i + 1, high, cnt - c);
                return;
            }
            cnt--;
        }
        solve(low, mid, cnt);
    };
    for (int i = 0; i < 250; i++) {
        mx = max(mx, Ask(i));
        mx = max(mx, Ask(n - 1 - i));
    }
    int low = -1;
    int high = -1;
    for (int i = 250; i < n; i++) {
        if (Ask(i) == mx) {
            low = i + 1;
            break;
        }
    }
    for (int i = n - 251; i >= 0; i--) {
        if (Ask(i) == mx) {
            high = i;
            break;
        }
    }
    int cnt = mx;
    for (int i = 0; i < n; i++) {
        if (!res[i].empty() && Ask(i) < mx) {
            cnt--;
        }
    }
    solve(low, high, cnt);
    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: 77.39 / 80