Submission #315886

#	Time	Username	Problem	Language	Result	Execution time	Memory
315886		wildturtle	The Big Prize (IOI17_prize)	C++14	0 / 100	91 ms	368 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
vector <int> v;
int maxx,idx,l,le,ri,mid,ans;
int find_best(int n) {
	for(int i=0;i<500;i++) {
		v=ask(i);
		if(v[0]+v[1]==0) return i;
		if(v[0]+v[1]>maxx) {
			maxx=v[0]+v[1];
			idx=i;
			l=v[0];
		}
	}
	while(true) {
		le=idx+1; ri=n-1;
		while(le<=ri) {
			mid=(le+ri)/2;
			v=ask(mid);
			if(v[0]+v[1]==maxx && v[0]==l) le=mid+1;
			else { ri=mid-1; }
			if(v[0]+v[1]!=maxx) ans=mid;
		}
		for(int i=ans+1;i<min(n,ans+500);i++) {
			v=ask(i);
			if(v[0]+v[1]==0) return i;
			if(v[0]+v[1]==maxx) {
				idx=i;
				l=v[0];
				break;
			}
		}
	}
}

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