제출 #817709

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
817709		FEDIKUS	커다란 상품 (IOI17_prize)	C++17	90 / 100	66 ms	388 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;
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) {
	int q=0;
	n=_n;
	map<int,int> kurac;
	for(int i=0;i<koren;i++){
		auto rez=ask(i);
		q++;
		maxi=max(maxi,rez[0]+rez[1]);
		kurac[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;
		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{
				if(rez[0]==klk){
					l=mid+1;
				}else{
					r=mid-1;
				}
			}
		}
		tren=sled;
		klk++;
	}
	return res;
}

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