Submission #1162936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1162936		MrDogMeat	The Big Prize (IOI17_prize)	C++20	0 / 100	772 ms	1114112 KiB

prize

#include<bits/stdc++.h>
using namespace std;

std::vector<int> ask(int i);

const int MAXN = 2e5;

int Ans;

vector<int> A[MAXN];

bool answered[MAXN];
bool Found;

vector<int> ASK(int x) {
    if(!answered[x]) {
        A[x] = ask(x);
        if(A[x][0] + A[x][1] == 0) {
            Ans = x;
            Found = true;
        }
        answered[x] = true;
    }
    return A[x];
}

void solve(int l, int r) {
    if(l == r || Found) {
        return;
    }
    int mid = (l + r) / 2;
    vector<int> a = ASK(mid), b = ASK(l), c = ASK(r);
    if(a[0] + a[1] == b[0] + b[1] && a[0] - b[1] > 0) {
        solve(l, mid - 1);
    }
    if(a[0] + a[1] == c[0] + c[1] && c[0] - a[1] > 0) {
        solve(mid + 1, r);
    }
}

int find_best(int n) {
    for(int i = 0; i < MAXN; i++) {
        A[i].resize(2);
    }
    solve(0, n - 1);
    return Ans;
}

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