Submission #817768

#	Time	Username	Problem	Language	Result	Execution time	Memory
817768		FEDIKUS	The Big Prize (IOI17_prize)	C++17	97.61 / 100	48 ms	432 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>

using namespace std;

const int maxn=2e5+10;
const int koren=480;

int res=-1;
int maxi=0;
int n;
int q=0;
map<int,int> najr;
map<int,int> najl;

int find_best(int _n) {
	n=_n;
	map<int,int> kurac;
	vector<int> sta(koren);
	for(int i=0;i<koren;i++){
		auto rez=ask(i);
		q++;
		maxi=max(maxi,rez[0]+rez[1]);
		kurac[rez[0]+rez[1]]++;
		sta[i]=rez[0]+rez[1];
		if(rez[0]+rez[1]==0) return i;
	}
	int klk=koren-kurac[maxi];
	int tren=koren-1;
	while(true){
		int l=tren+1;
		int r=n-1;
		int sled=-1;
		if(najr.find(klk)!=najr.end()) l=najr[klk]+1;
		auto it=najl.upper_bound(klk);
		if(it!=najl.end()) r=it->second-1;
		while(l<=r){
			int mid=l+(r-l)/2;
			auto rez=ask(mid);
			q++;
			if(q==10000) exit(-1);
			if(rez[0]+rez[1]==0) return mid;
			if(rez[0]+rez[1]<maxi){
				sled=mid;
				r=mid-1;
			}else{
				najr[rez[0]]=max(najr[rez[0]],mid);
				if(najl.find(rez[0])==najl.end()) najl[rez[0]]=n;
				najl[rez[0]]=min(najl[rez[0]],mid);
				if(rez[0]==klk){
					l=mid+1;
				}else{
					r=mid-1;
				}
			}
		}
		tren=sled;
		klk++;
	}
	return res;
}

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