Submission #291892

#	Time	Username	Problem	Language	Result	Execution time	Memory
291892		amiratou	The Big Prize (IOI17_prize)	C++14	90 / 100	88 ms	5496 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> h[200005];
int f=-1,N;
vector<int> query(int idx){
	if(h[idx].empty())h[idx]=ask(idx);
	if(!(h[idx][0]+h[idx][1]))f=idx;
	return h[idx];
}
int close_left(int l,int r){
	while(l<=r){
		vector<int> M=query(l);
		if((M[0]+M[1])==N)return l;
		else if(!(M[0]+M[1])){f=l;return -1;}
		else if(!M[1])return -1;
		l++;
	}
	return -1;
}
int close_right(int l,int r){
	while(r>=l){
		vector<int> M=query(r);
		if((M[0]+M[1])==N)return r;
		else if(!(M[0]+M[1])){f=r;return -1;}
		else if(!M[0])return -1;
		r--;
	}
	return -1;
}
void gimme(int l,int r){
	if(l>=r)return ;
	if(f!=-1)return;
	vector<int> G=query(l),G2=query(r);
	if(f!=-1)return;
	if((G[0]+G[1])==(G2[0]+G2[1]) && (G2[0]==G[0]))return ;
	int med=(l+r)>>1,k;
	vector<int> M=query(med);
	if(!(M[0]+M[1])){f=med;return;}
	else if((M[0]+M[1])==N){
		gimme(l,med);
		if(f!=-1)return;
		k=med+1;
		if(f!=-1)return;
		if(k!=-1)gimme(k,r);
	}
	else{
		k=med;
		if(f!=-1)return;
		if(k!=-1)gimme(l,k);
		if(f!=-1)return;
		k=med+1;
		if(f!=-1)return;
		if(k!=-1)gimme(k,r);
	}
}

int find_best(int n) {
	N=0;
	for (int i = 0; i < min(500,n); ++i)
	{
		vector<int> Y=query(i);
		if(!(Y[0]+Y[1]))return i;
		else N=max(N,Y[0]+Y[1]);
	}
	int l=min(500,n-1);
	if(f!=-1)return f;
	assert(l!=-1);
	int r=n-1;
	if(f!=-1)return f;
	assert(r!=-1);
	gimme(l,r);
	assert(f!=-1);
	return f;
}

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