Submission #590255

#	Time	Username	Problem	Language	Result	Execution time	Memory
590255		AlesL0	The Big Prize (IOI17_prize)	C++17	97.39 / 100	57 ms	1160 KiB

prize

#include <bits/stdc++.h>

using namespace std;

vector <bool> is_small;
int sum;
vector <int> val;
int sol = -1;

vector <int> ask(int i);

void binary_search(int m, int s, int e, int left, int right){
    if (sol != -1)return;
    if (is_small[m])return;
    vector <int> a = ask(m);
    if (a[0]+a[1] == 0)sol = m;
    //if (a[0]+a[1] < sum){is_small[m] = 1; return;}
    if (e-s <= 1)return;
    if (a[0]-left > 0)binary_search((s+m)/2, s, m, left, a[1]);
    if (a[1]-right > 0)binary_search((m+1+e)/2, m+1, e, a[0], right);
}

int find_best(int n){
    if (n == 1)return 0;
    is_small.resize(n, 0);
    val.resize(n);
    sum = 0;
    for (int i = 0; i <= min(500, n-1); i++){
        vector <int> a = ask(i);
        val[i] = a[0]+a[1];
        sum = max(sum, val[i]);
    }
    int start = -1;
    for (int i = 0; i < min(501, n); i++){
        if (val[i] < sum)is_small[i] = 1;
        if (val[i] >= sum)start = i;
        if (val[i] == 0)return i;
    }
    binary_search(start, 0, n, 0, 0);
    return sol;
}

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