Submission #1185687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185687		ByeWorld	The Big Prize (IOI17_prize)	C++20	90 / 100	22 ms	408 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 2e5+10;
typedef pair<int,int> pii;

int n;

pii ASK(int i){
	vector<int> res = ask(i);
	return {res[0], res[1]};
}
int find_best(int N) {
	n = N;
	// if(n <= 500){
	// 	for(int i = 0; i < n; i++) {
	// 		vector<int> res = ask(i);
	// 		if(res[0] + res[1] == 0)
	// 			return i;
	// 	}
	// 	return 0;
	// }
	set <int> s;
	for(int i=0; i<min(n, 500); i++){
		vector<int> ret = ask(i);
		if(ret[0] + ret[1] == 0)
			return i;
		s.insert(ret[0] + ret[1]);
	}
	if(s.size() > 5) assert(false);

	int MX = *(--s.end());
	int nw = 0;
	while(true){
		// cout << nw << " nw\n";
		pii ret = ASK(nw);
		if(ret.fi + ret.se == 0)
			return nw;
		int more = ret.se;
		if(ret.fi+ret.se != MX){
			nw++; continue;
		}
		int l=nw+1, r=n-1, mid=0, cnt=nw;
		while(l<=r){
			mid = (l+r)>>1;
			pii ret = ASK(mid);
			if(ret.fi + ret.se == 0)
				return mid;
			if(ret.se == more) cnt = mid, l = mid+1;
			else r = mid-1;
		}
		nw = cnt+1;
	}
}

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