Submission #343808

#	Time	Username	Problem	Language	Result	Execution time	Memory
343808		Kerim	The Big Prize (IOI17_prize)	C++17	20 / 100	69 ms	492 KiB

prize

#include "prize.h"
#include "bits/stdc++.h"
using namespace std;
const int C=500;
const int CC=25;
int find_best(int n){
	int mx=0;
	for(int i=0;i<min(C,n);i++){
		vector<int>res=ask(i);
		if(res[0]+res[1]==0)
			return i;
		mx=max(mx,res[0]+res[1]);
	}
	for(int i=C;i<n;i++){
		vector<int>res=ask(i);
		if(res[0]+res[1]==0)
			return i;
		if(res[0]+res[1]<mx)
			continue;
		if(i+C<n and ask(i+C)==res)
			i+=C;
		else if(i+CC<n and ask(i+CC)==res)
			i+=CC;
		else{
			int st=i+1,en=min(n-1,i+CC);
			while(st+1<en){
				int mid=(st+en)>>1;
				if(ask(mid)==res)
					st=mid;
				else
					en=mid;
			}	
			if(ask(en)==res)
				i=en;
			else
				i=st;
		}
	}
	return -1;
}

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