Submission #52152

#	Time	Username	Problem	Language	Result	Execution time	Memory
52152		ernestvw	The Big Prize (IOI17_prize)	C++11	20 / 100	22 ms	11524 KiB

prize

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

#include "prize.h"
//vector<int> ask(int i);

int N;

vector<int> memo[200001];
vector<int> query(int i) {
	if(memo[i][0] != -1) return memo[i];
	else return memo[i] = ask(i);
}

int find(int l, int r) {
	if(l == r) return l;
	int mid = (l+r)/2;
	vector<int> q = query(mid);
	if(q[0] == 0 and q[1] == 0) return mid;
	else if(q[0] == 0) return find(mid+1, r);
	return find(l, mid-1);
}

int find_best(int n) {
	N = n;
	for(int i = 0; i < N; i++) memo[i] = {-1, -1};
	return find(0, N-1);
}

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