제출 #296944

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
296944		kshitij_sodani	커다란 상품 (IOI17_prize)	C++14	100 / 100	94 ms	47632 KiB

prize

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back


#include "prize.h"
vector<int> pre[2000001];
pair<int,int> ma={-1,-1};
int ans;
vector<int> ask2(int i){
	if(pre[i].size()>0){
		return pre[i];
	}
	pre[i]=ask(i);
	return pre[i];
}
void run(int l,int r,int aa,int bb){
	if(aa+bb==ma.a){
		return ;
	}
	if(l>r){
		return;
	}
	//cout<<l<<":"<<r<<":"<<aa<<":"<<bb<<endl;
	int mid=(l+r)/2;
	int xx=0;
	for(int i=mid;i>=l;i--){
		vector<int> res=ask2(i);
		if(res[0]+res[1]==ma.a){
			if(i>l){
				run(l,i-1,aa,res[1]);
			}
			if(mid<r){
				run(mid+1,r,res[0]+xx,bb);
			}
			return;
		}
		xx++;
	}
	if(mid<r){
		run(mid+1,r,aa+xx,bb);
	}
}
int find_best(int n) {
	
	for(int i=0;i<min(500,n);i++){
		vector<int> res=ask2(i);
		if(res[0]+res[1]>ma.a){
			ma={res[0]+res[1],i};
		}
		if(ma.a>100){
			break;
		}
	}
	run(0,n-1,0,0);

	for(int i=0;i<n;i++){
		if(pre[i].size()>0){
			if(pre[i][0]+pre[i][1]==0){
				return i;
			}
		}
	}




	return 0;
}

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