Submission #425987

#	Time	Username	Problem	Language	Result	Execution time	Memory
425987		mosiashvililuka	The Big Prize (IOI17_prize)	C++14	0 / 100	109 ms	448 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,fx[200009],sq=450,lef,rig,mid,MX,LF,lf;
int F[200009];
pair <int, int> P[200009];
/*vector <int> ask(int q){
	int QA=0,WA=0,QQ=0;
	for(QQ=0; QQ<q; QQ++){
		if(F[QQ]<F[q]) QA++;
	}
	for(QQ=q+1; QQ<a; QQ++){
		if(F[QQ]<F[q]) WA++;
	}
	vector <int> QQA;
	QQA.push_back(QA);QQA.push_back(WA);
	return QQA;
}*/
pair <int, int> Ask(int q){
	if(fx[q]==1){
		return P[q];
	}
	fx[q]=1;
	vector <int> QA=ask(q);
	return make_pair(QA[0],QA[1]);
}
int find_best(int Nn) {
	a=Nn;
	MX=a+2;
	for(i=0; i<min(a,sq); i++){
		P[i]=Ask(i);
		MX=max(MX,P[i].first+P[i].second);
	}
	LF=0;
	while(1){
		lef=LF-1;rig=a;e=-1;
		if(LF==0){
			lf=0;
		}else{
			P[LF-1]=Ask(LF-1);
			lf=P[LF-1].first;
		}
		while(1){
			if(lef+1>=rig) break;
			mid=(lef+rig)/2;
			while(mid>lef){
				P[mid]=Ask(mid);
				if(P[mid].first+P[mid].second==MX) break;
				mid--;
			}
			if(mid==lef){
				e=lef+1;break;
			}
			P[mid]=Ask(mid);
			if(P[mid].first==lf){
				lef=mid;
				lf=P[mid].first;
			}else{
				rig=mid;
			}
		}
		P[e]=Ask(e);
		if(P[e].first+P[e].second==0){
			return e;
		}
		LF=e+1;
	}
	return 0;
}

/*int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(i=0; i<a; i++){
		cin>>F[i];
	}
	cout<<find_best(a);
	return 0;
}*/

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