Submission #293165

#	Time	Username	Problem	Language	Result	Execution time	Memory
293165		kshitij_sodani	The Big Prize (IOI17_prize)	C++14	90 / 100	137 ms	47876 KiB

prize

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back

#include "prize.h"
vector<int> pre[2000001];
vector<int> ask2(int i){
	if(pre[i].size()>0){
		return pre[i];
	}
	pre[i]=ask(i);
	return pre[i];
}
int find_best(int n) {
	if(n<500){
		for(int i = 0; i < n; i++) {
			vector<int> res = ask2(i);
			if(res[0] + res[1] == 0)
				return i;
		}
	}
	pair<int,int> ma={-1,-1};
	for(int i=0;i<500;i++){
		vector<int> res=ask2(i);
		if(res[0]+res[1]==0){
			return i;
		}
		if(res[0]+res[1]>=ma.a){
			ma={res[0]+res[1],i};
		}
	}
	int ind=ma.b;
	ask2(n-1);
	if(pre[n-1][0]+pre[n-1][1]==0){
		return n-1;
	}
	while(ind<n){
		vector<int> res=ask2(ind);
		if(res[0]+res[1]==0){
			return ind;
		}
		if(res[0]+res[1]<ma.a){
			ind+=1;
			continue;
		}
		if(res[0]==pre[n-1][0]){
			break;
		}

		int low=ind+1;
		int high=n-1;
		while(low<high-1){
			int mid=(low+high)/2;
			vector<int> res2=ask2(mid);
			if(res2[0]+res2[1]<ma.a){
				high=mid;
			}
			else{
				if(res2[0]==res[0]){
					low=mid;
				}
				else{
					high=mid;
				}
			}
		}
		for(int i=low;i<=high;i++){
			vector<int> res2=ask2(i);
			if(res2[0]+res2[1]<ma.a){
				ind=i;
				break;
			}
			else{
				if(res2[0]==res[0]){
					continue;
				}
				else{
					ind=i;
					break;
				}
			}
		}
		if(pre[ind][0]+pre[ind][1]==0){
			return ind;
		}
	}





	
	return 0;
}

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