Submission #1203870

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

prize

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

#include"prize.h"
const ll L=500;

int find_best(int n){
	map<ll,ll>C;
	for(int i=0;i<L;++i){
		vector<int>a=ask(i);
		++C[a[0]+a[1]];
		if(!a[0]&&!a[1])return i;
	}
	ll x=0,lik=L-1,br,l,r;
	for(auto[u,v]:C)x=max(x,u);
	br=L-C[x];
	while(1){
		l=lik+1,r=n-1;
		while(l<=r){
			ll m=(l+r)/2;
			vector<int>a=ask(m);
			if(!a[0]&&!a[1])return m;
			else if(a[0]+a[1]==x){
				if(a[0]!=br)r=m-1;
				else l=m+1;
			}else{
				lik=m;
				r=m-1;
			}
		}
		++br;
	}
	return -1;
}

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