제출 #291887

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
291887		amiratou	커다란 상품 (IOI17_prize)	C++14	90 / 100	108 ms	5408 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> h[200005];
int f=-1,N;
vector<int> query(int idx){
	if(!h[idx].empty())return h[idx];
	return h[idx]=ask(idx);
}
int close_left(int l,int r){
	while(l<=r){
		vector<int> M=query(l);
		if((M[0]+M[1])==N)return l;
		else if(!(M[0]+M[1])){f=l;return -1;}
		else if(!M[1])return -1;
		l++;
	}
	return -1;
}
int close_right(int l,int r){
	while(r>=l){
		vector<int> M=query(r);
		if((M[0]+M[1])==N)return r;
		else if(!(M[0]+M[1])){f=r;return -1;}
		else if(!M[0])return -1;
		r--;
	}
	return -1;
}
void gimme(int l,int r){
	if(f!=-1)return;
	if(l==r)return ;
	vector<int> G=query(l),G2=query(r);
	if(G2[0]==G[0])return;
	int med=(l+r)>>1,k;
	vector<int> M=query(med);
	if(!(M[0]+M[1])){f=med;return;}
	else if((M[0]+M[1])==N){
		gimme(l,med);
		if(f!=-1)return;
		k=close_left(med+1,r);
		if(f!=-1)return;
		if(k!=-1)gimme(k,r);
	}
	else{
		k=close_right(l,med-1);
		if(f!=-1)return;
		if(k!=-1)gimme(l,k);
		if(f!=-1)return;
		k=close_left(med+1,r);
		if(f!=-1)return;
		if(k!=-1)gimme(k,r);
	}
}

int find_best(int n) {
	N=0;
	for (int i = 0; i < min(500,n); ++i)
	{
		vector<int> Y=query(i);
		if(!(Y[0]+Y[1]))return i;
		else N=max(N,Y[0]+Y[1]);
	}
	int l=close_left(0,n-1);
	if(f!=-1)return f;
	assert(l!=-1);
	int r=close_right(l,n-1);
	if(f!=-1)return f;
	assert(r!=-1);
	gimme(l,r);
	assert(f!=-1);
	return f;
}

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