Submission #817669

#	Time	Username	Problem	Language	Result	Execution time	Memory
817669		FEDIKUS	The Big Prize (IOI17_prize)	C++17	20 / 100	63 ms	536 KiB

prize

#include "prize.h"
#include<vector>
#include<set>

using namespace std;

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

int res=-1;
int maxi=0;
set<pair<int,int> > veliki;
int fwt[maxn];
int n;

void dodaj(int x){
	x++;
	for(;x<maxn;x+=x&-x) fwt[x]++;
}
int qry(int x){
	int ret=0;
	x++;
	if(x==0) return 0;
	for(;x>0;x-=x&-x) ret+=fwt[x];
	return ret;
}

bool uradi(int l,int r,bool levi,bool desni){
	if(l>r) return false;
	int mid=l+(r-l)/2;
	vector<int> rez=ask(mid);
	int klkl=rez[0],klkr=rez[1];
	if(klkl+klkr<maxi){
		dodaj(mid);
		veliki.emplace(pair<int,int>(mid,klkl+klkr));
	}
	if(klkl+klkr==0){
		res=mid;
		return true;
	}
	if(levi){
		if(klkl+klkr==maxi){
			klkl-=qry(l-1);
		}else{
			for(auto i:veliki){
				int sta=0;
				if(i.first<l && i.second<klkl+klkr) sta++;
				klkl-=sta;
			}
		}
		if(klkl>0) if(uradi(l,mid-1,true,false)) return true;
	}
	if(desni){
		if(klkl+klkr==maxi){
			klkr-=qry(n-1)-qry(r);
		}else{
			for(auto i:veliki){
				int sta=0;
				if(i.first>r && i.second<klkl+klkr) sta++;
				klkr-=sta;
			}
		}
		if(klkr>0) uradi(mid+1,r,false,true);
	}
	if(!levi && klkl>0) if(uradi(l,mid-1,false,desni)) return true;
	if(!desni && klkr>0) if(uradi(mid+1,r,levi,false)) return true;
	return false;
}

int find_best(int _n) {
	n=_n;
	for(int i=0;i<koren;i++){
		auto rez=ask(i);
		maxi=max(maxi,rez[0]+rez[1]);
		if(rez[0]+rez[1]==0) return i;
	}
	uradi(koren,n-1,true,true);
	return res;
}

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