Submission #519977

#	Time	Username	Problem	Language	Result	Execution time	Memory
519977		tabr	The Big Prize (IOI17_prize)	C++17	0 / 100	61 ms	28988 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);
    int B = (int) sqrt(n);
    set<int> st;
    for (int i = 0; i <= n; i++) {
        st.emplace(i);
    }
    auto Ask = [&](int i) {
        if (!res[i].empty()) {
            return res[i][0] + res[i][1];
        }
        st.erase(i);
        res[i] = ask(i);
        return res[i][0] + res[i][1];
    };
    vector<int> sz(B + 1);
    for (int i = 0; i < B; i++) {
        sz[i + 1] = sz[i] + (n + i) / B;
    }
    int mx = -1;
    for (int i = 0; i < B; i++) {
        mx = max(mx, Ask(sz[i]));
    }
    for (int i = 0; i < B; i++) {
        for (int j = sz[i]; j < sz[i + 1]; j++) {
            if (Ask(j) == mx) {
                break;
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (!res[i].empty() && Ask(i) == 0) {
            return i;
        }
    }
    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 k = 0; k < B; k++) {
        int low = *st.lower_bound(sz[k]) - 1;
        int high = *st.lower_bound(sz[k + 1]) - 1;
        int cnt = 0;
        if (low == high) {
            continue;
        }
        if (high == n - 1) {
            low++;
            for (int i = n - 1; i >= 0; i--) {
                if (Ask(i) == mx) {
                    high = i;
                    cnt = res[high][0] - res[low][0];
                    break;
                }
            }
        } else {
            cnt = res[high][0] - res[low][0] - (high - sz[k + 1]);
            low++;
            high = sz[k + 1];
        }
        solve(low, high, cnt);
        for (int i = sz[k]; i < sz[k + 1]; i++) {
            if (!res[i].empty() && Ask(i) == 0) {
                return i;
            }
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        if (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: 0 / 20
• Subtask 2: 0 / 80