제출 #268619

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
268619		Plurm	커다란 상품 (IOI17_prize)	C++11	0 / 100	1351 ms	8096 KiB

prize

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

vector<int> memoiz[200005];
vector<int> customAsk(int x){
	// Memoized version of ask
	if(memoiz[x].empty()) return memoiz[x] = ask(x);
	else return memoiz[x];
}

int solve(int l, int r, int offsL = 0, int offsR = 0){
	if(l == r) return -1;
	int m = (l+r)/2;
	vector<int> res = customAsk(m);
	do{
		if(res[0] + res[1] == 0) return m;
		if(m == r) break;
		m++;
	}while(res[0] + res[1] < 500);
	int left = -1;
	if(res[0] - offsL > 0) left = solve(l, m-1, offsL, res[1]);
	if(m == r) return left;
	if(left != -1) return left;
	if(res[1] - offsR > 0) return solve(m+1, r, res[0], offsR);
	return -1;
}

int find_best(int n) {
	if(n < 5000){
		for(int i = 0; i < n; i++) {
			vector<int> res = customAsk(i);
			if(res[0] + res[1] == 0)
				return i;
		}
	}
	return solve(0, n-1);
}

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