Submission #209432

#	Time	Username	Problem	Language	Result	Execution time	Memory
209432		TAISA_	The Big Prize (IOI17_prize)	C++14	20 / 100	81 ms	2040 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
using P=pair<int,int>;
/*vector<int> s;
vector<int> ask(int id){
	cout<<id<<endl;
	int a,b;cin>>a>>b;
	vector<int> res{a,b};
	return res;
}*/
int find_best(int n) {
	vector<int> a;
	vector<P> v(n,P(-1,-1));
	int en=n;
	int cnt=0;
	int ma=0;
	for(int i=0;i<min(n,450);i++){
		a=ask(i);
		ma=max(ma,a[0]+a[1]);
		v[i]=P(a[0],a[1]);
		if(a[0]+a[1]==0){
			return i;
		}
	}
	while(1){
		int ok=0,ng=en;
		while(ng-ok>1){
			int mid=(ok+ng)/2;
			if(v[mid].first==-1){
				a=ask(mid);
				v[mid]=P(a[0],a[1]);
				if(a[0]+a[1]==0){
					return mid;
				}
			}
			if(v[mid].second==cnt){
				if(v[mid].second+v[mid].first==ma){
					ng=mid;
				}else{
					ok=mid;
				}
			}else{
				ok=mid;
			}
		}
		en=ok;
		cnt++;
	}
	return 0;
}
/*int main(){
	int n;cin>>n;
	s.resize(n);
	for(int i=0;i<n;i++){
		cin>>s[i];
	}
	cout<<find_best(n)<<endl;
}*/

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