Submission #1065454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065454		TheQuantiX	The Big Prize (IOI17_prize)	C++17	90 / 100	58 ms	2132 KiB

prize

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

using namespace std;
using ll = long long;

pair<int, int> memo[200001];
ll p = 0;

pair<ll, ll> doask(int i) {
    if (memo[i].first != -1) {
        return memo[i];
    }
    auto v = ask(i);
    memo[i] = {v[0], v[1]};
    return memo[i];
}

int find_best(int n) {
    mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
    for (int i = 0; i < n; i++) {
        memo[i] = {-1, -1};
    }
    for (int i = 0; i < 500; i++) {
        ll x = gen() % n;
        p = max(p, doask(x).first + doask(x).second);
        if (doask(x).first + doask(x).second == 0) {
            return x;
        }
    }
    ll x = 0;
    while (x != n) {
        if (doask(x).first + doask(x).second != p) {
            if (doask(x).first + doask(x).second == 0) {
                return x;
            }
            x++;
            continue;
        }
        ll l = x, r = n - 1;
        while (r > l) {
            ll mid = (l + r) / 2;
            if (doask(mid) != doask(x)) {
                r = mid;
            }
            else {
                l = mid + 1;
            }
        }
        if (doask(l).first + doask(l).second == 0) {
            return l;
        }
        x = r + 1;
    }
    assert(false);
}

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