Submission #478694

#	Time	Username	Problem	Language	Result	Execution time	Memory
478694		mosiashvililuka	The Big Prize (IOI17_prize)	C++14	90 / 100	128 ms	2780 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,lef,rig,mid,T=550,BO[200009],mx,E;
pair <int, int> P[200009];vector <int> vv;
void ASK(int q){
	if(q==0) return;
	if(BO[q]==0){
		BO[q]=1;vv=ask(q-1);
		P[q]=make_pair(vv[0],vv[1]);
	}
}
int find_best(int Nn) {
	a=Nn;
	for(i=1; i<=min(T,a); i++){
		ASK(i);
		mx=max(mx,P[i].first+P[i].second);
	}
	ASK(a);i=0;
	j=a;
	while(P[j].first+P[j].second!=mx){
		j--;ASK(j);
	}
	E=P[j].first;jj=j;
	while(1){
		if(i>=jj||P[i].first==E) break;
		lef=i;rig=jj+1;
		while(1){
			if(lef+1>=rig) break;
			mid=(lef+rig)/2;
			ASK(mid);j=mid;
			while(P[j].first+P[j].second!=mx&&j!=0){
				j--;ASK(j);
			}
			if(P[j].first==P[i].first){
				lef=mid;
			}else{
				rig=mid;
			}
		}
		//rig-1 > lollipop
		ASK(rig-1);
		i=rig;ASK(i);
		while(i<jj&&P[i].first+P[i].second!=mx){
			i++;ASK(i);
		}
	}
	for(i=1; i<=a; i++){
		if(BO[i]!=0&&P[i].first==0&&P[i].second==0){
			return i-1;
		}
	}
	return 0;
}

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