Submission #317371

#	Time	Username	Problem	Language	Result	Execution time	Memory
317371		tigicha	The Big Prize (IOI17_prize)	C++14	90 / 100	108 ms	512 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
vector <int> v;
int mx, k, p, l, r, m, ans;
int find_best(int n){
	for(int i=0; i<474;i++){
		v=ask(i);
		if(v[0]+v[1]==0) return i;
		if(v[0]+v[1]>mx){
			mx=v[0]+v[1];
			k=i;
			p=v[0];
		}
	}
	while(true){
		l=k+1;
		r=n-1;
		while(l<=r){
			m=(l+r)/2;
			v=ask(m);
			if(v[0]+v[1]==0) return m;
			if(v[0]+v[1]==mx && v[0]==p) l=m+1;
			else r=m-1;
			if(v[0]+v[1]!=mx) ans=m;
		}
		for(int i=ans; i<n; i++){
			v=ask(i);
			if(v[0]+v[1]==0) return i;
			if(v[0]+v[1]==mx){
				k=i;
				p=v[0];
				break;
			}
		}
	}
}

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