Submission #1208704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208704		m5588ohammed	The Big Prize (IOI17_prize)	C++20	95.06 / 100	22 ms	11372 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int ans=-1,n,lst,sum=0,cnt=0;
vector <int> info[200005];
void ASK(int idx){
	//cout<<idx<<endl;
	if(info[idx][0]==-1){
		info[idx]=ask(idx);
		cnt++;
	}
	if(cnt>=9000) assert(0);
	return; 
}
void walk(int i){
	lst=i;
	ASK(i);
	if(info[i][0]+info[i][1]==0){
		ans=i;
		return;
	}
	if(info[i][0]+info[i][1]==sum){
		lst=i;
		return;
	}
	walk(i+1);
	return;
}
void search(int i){
	ASK(i);
	int l=0,r=n-1;
	while(l<=r){
		int mid=(l+r)/2;
		if(mid<i) {l=mid+1;continue;}
		ASK(mid);
		if(info[i][0]+info[i][1]==0){
			ans=i;
			return;
		}
		if(info[mid][0]==info[i][0]&&info[mid][1]==info[i][1]){
			lst=mid+1;
			l=mid+1;
		}
		else r=mid-1;
	}
	return;
}
int find_best(int N) {

	srand(time(NULL));
	n=N;
	for(int i=0;i<n;i++) info[i]={-1,-1};

	int k=500;
	while(k--){
		int idx=rand()%n;
		ASK(idx);
		if(info[idx][0]+info[idx][1]>sum) sum=info[idx][0]+info[idx][1];
	}
	while(true){
		walk(lst);
		if(ans!=-1) return ans;
		search(lst);
		if(ans!=-1) return ans;
	}
	return lst;
}

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