Submission #426179

#	Time	Username	Problem	Language	Result	Execution time	Memory
426179		mosiashvililuka	The Big Prize (IOI17_prize)	C++14	20 / 100	158 ms	2656 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=2,lef,rig,mid,MX,LF,lf;
int F[200009];
pair <int, int> P[200009];
/*pair <int, 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++;
	}
	return make_pair(QA,WA);
}*/
pair <int, int> Ask(int q){
	if(fx[q]==1){
		return P[q];
	}
	fx[q]=1;
	vector <int> QA=ask(q);
	P[q]=make_pair(QA[0],QA[1]);
	return make_pair(QA[0],QA[1]);
}
int find_best(int Nn) {
	a=Nn;
	MX=0;
	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;
			//cout<<lef<<" O "<<rig<<endl;
			mid=(lef+rig)/2;
			while(mid>lef){
				P[mid]=Ask(mid);
				if(P[mid].first+P[mid].second==MX) break;
				mid--;
			}
			//cout<<mid<<endl;
			if(mid==lef){
				e=lef+1;break;
			}
			P[mid]=Ask(mid);
			/*if(mid==2){
				cout<<"ORISTVIS: "<<P[mid].first<<" "<<P[mid].second<<"    "<<lf<<endl;
			}*/
			if(P[mid].first==lf){
				lef=mid;
				lf=P[mid].first;
			}else{
				rig=mid;
			}
		}
		lf++;
		//cout<<LF<<" "<<e<<" GUN "<<lf<<endl;
		P[e]=Ask(e);
		if(P[e].first+P[e].second==0){
			return e;
		}
		//lf=P[e].first;
		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: 20 / 20
• Subtask 2: 0 / 80