Submission #283964

#	Time	Username	Problem	Language	Result	Execution time	Memory
283964		hank55663	The Big Prize (IOI17_prize)	C++14	0 / 100	10 ms	4992 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> cache[200005];
int Maxnum=0;
int cnt=0;
vector<int> myask(int x){
	
	if(cache[x].empty()){
		cache[x]=ask(x);
		if(cache[x][0]+cache[x][1]==Maxnum)cnt++;
		//printf("%d\n",x);
	}
	return cache[x];
}
int Maxm[200005];
bool cal(int l,int r,int Maxnum,int num,int &res){
	if(l>r)return false;
	int mid=(l+r)/2;
	int a=mid,b=mid;
	while(true){
		if(a<l)break;
		vector<int> v=myask(a);
		if(v[0]+v[1]==0){res=a;return true;}
		if(v[0]+v[1]==Maxnum){
			break;
		}
		a--;
	}
	while(true){
		if(b>r)break;
		vector<int> v=myask(b);
		if(v[0]+v[1]==0){res=b;return true;}
		if(v[0]+v[1]==Maxnum){
			break;
		}
		b++;
	}
	vector<int> v=myask(a);
	if(v[0]!=num){
		assert(v[0]>num);
		if(cal(l,a-1,Maxnum,num,res))return true;
		num=v[0];
	}
	v=myask(b);
	if(cal(b+1,r,Maxnum,v[0],res))return true;
	return false;
}
int find_best(int n) {
//	int Maxnum=0;
	for(int i = 0;i<n&&i<500;i++){
		vector<int> v=myask(i);
		if(v[0]+v[1]==0)return i;
		Maxnum=max(Maxnum,v[0]+v[1]);
	}
	int res;
	cal(0,n-1,Maxnum,0,res);
	printf("%d\n",cnt);
	return res;
	int l=0,r=n-1;
	int num=0;
	while(true){
		int Max=r,Min=l;
	//	printf("%d %d\n",Max,Min);
		while(Max>Min){
			int mid=(Max+Min)/2;
			vector<int> v=myask(mid);
		
			if(v[0]+v[1]==0)return mid;
			if(v[1]==0)r=mid-1;
			if(v[0]+v[1]!=Maxnum){
				Max=mid;
			}
			else{
				Maxm[v[0]]=max(Maxm[v[0]],mid);
				if(v[0]-num)Max=mid-1;
				else Min=mid+1;
			}
		}
		num++;
		Maxm[num]=max(Maxm[num],Max);
		vector<int> v=myask(Max);
		if(v[0]+v[1]==0)return Max;
	//	printf("? %d %d %d\n",v[0],v[1],num);
		l=Maxm[num]+1;
	}
	/*
	int Max=n-1,Min=0;
	while(Max>Min){
		int mid=(Max+Min)/2;
		vector<int> v=ask(mid);
		if(v[0]+v[1]==0){
			return mid;
		}
		if(v[0]<v[1]){
			Min=mid+1;
		}
		else{
			Max=mid-1;
		}
	}
	return Min;*/
}
/*
1 2 5 447 90001
*/

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