Submission #528485

#	Time	Username	Problem	Language	Result	Execution time	Memory
528485		new_acc	커다란 상품 (IOI17_prize)	C++14	0 / 100	110 ms	740 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"
#define fi first
#define se second
using namespace std;
typedef unsigned long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=2e5+10;
int t[N];
set<int>s;
int n;
/*vi ask(int ind){
	vi a;
	a.push_back(0),a.push_back(0);
	for(int i=0;i<ind;i++) if(t[i]<t[ind]) a[0]++;
	for(int i=ind+1;i<n;i++) if(t[i]<t[ind]) a[1]++;
	return a;
}*/
int bs(int pocz,int kon,int x,int l,int r){
	int sr;
	while(pocz<=kon){
		sr=(pocz+kon)/2;
		vi a=ask(sr);
		if(a[0]+a[1]==0) return -(sr+1);
		if(a[0]+a[1]!=x) return sr;
		if(a[0]>l) kon=sr-1;
		else{
			if(a[1]>r) pocz=sr+1;
			else return INT_MAX;
		}
	}	
	return INT_MAX;
}
int find_best(int m){
	n=m;	
	int l=0,r=0;
	int ind=0,p=sqrt(n);
	if(p*p!=n) p++;
	while(ind<n-1){
		vi a=ask(ind);
		if(a[0]+a[1]==0){
			return ind;
			break;
		}
		s.insert(ind);
		if(a[0]+a[1]>=p) {p=a[0]+a[1];break;}
		ind++,l++;
	}	
	auto it=s.end();
	it--;
	s.insert(n);
	vi a=ask(2);
	while(*it!=n){
		auto it2=it;
		it2++;
		int pom=bs(*it+1,*it2-1,p,l,r);
		if(pom!=INT_MAX){
			if(pom<0) return abs(pom)-1;
			s.insert(pom);
			r++;
		}else{
			l++,r--;
			it++;
		}
	}
	return 0;
}
/*int main(){
	int k;
	cin>>k;
	for(int i=0;i<k;i++) cin>>t[i];
	cout<<find_best(k)<<"\n";
}*/

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