Submission #187329

#	Time	Username	Problem	Language	Result	Execution time	Memory
187329		popovicirobert	The Big Prize (IOI17_prize)	C++14	100 / 100	71 ms	5548 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

static const int MAXN = (int) 2e5;

static bool mark[MAXN];
static vector <int> qry[MAXN];

static inline vector <int> myask(int pos) {
    if(mark[pos] == 0) {
        qry[pos] = ask(pos);
    }
    mark[pos] = 1;
    return qry[pos];
}


static int solve(int l, int r, int numl, int numr, int mx) {
    if(l > r) return -1;

    int mid = (l + r) / 2;

    int ll = mid, rr = mid;
    while(ll >= l && myask(ll)[0] + myask(ll)[1] < mx) {
        auto cur = myask(ll);
        if(cur[0] + cur[1] == 0) return ll;
        ll--;
    }
    while(rr <= r && myask(rr)[0] + myask(rr)[1] < mx) {
        auto cur = myask(rr);
        if(cur[0] + cur[1] == 0) return rr;
        rr++;
    }

    auto x = myask(max(ll, l)), y = myask(min(rr, r));
    int ans = -1;

    if(x[0] - numl > 0) {
        ans = max(ans, solve(l, ll - 1, numl, x[1], mx));
    }
    if(y[1] - numr > 0) {
        ans = max(ans, solve(rr + 1, r, y[0], numr, mx));
    }
    return ans;
}


int find_best(int n) {
    srand(time(NULL));

    auto myrand = [&]() {
        return (1LL * (1LL << 15) * rand() + rand()) % n;
    };

    vector <bool> vis(n);
    int mx = 0;

    for(int i = 0; i < min(n, 200); i++) {
        int p = myrand();
        while(vis[p]) { p = myrand(); }
        vis[p] = 1;
        auto cur = myask(p);
        mx = max(mx, cur[0] + cur[1]);
    }

    return solve(0, n - 1, 0, 0, mx);
}

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