Submission #103157

#	Time	Username	Problem	Language	Result	Execution time	Memory
103157		minson123	The Big Prize (IOI17_prize)	C++11	98.72 / 100	74 ms	704 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int pos,minr,limt;
map<int,pii> dic;
pii query(int p){
	if(dic.find(p)!=dic.end()) return dic[p];
	vector<int> q=ask(p);
	return dic[p]=pii(q[0],q[1]);
}
void solve(int l,int r){
	/*pii q=query(l);
	if(q.first+q.second==limt && q.second==minr) return;*/
	if(pos!=-1 || l>r) return;
	if(l==r){
		pii q=query(l);
		if(q.first==0 && q.second==0) pos=l;
		else if(q.first+q.second==limt) minr=q.second;
	}else{
		int mid=(l+r)>>1;
		pii q=query(mid+1);
		if(q.first+q.second<limt){
			if(q.first==0 && q.second==0) pos=mid+1;
			solve(mid+2,r);
		}else if(q.second>minr) solve(mid+1,r);
		q=query(l);
		if(query(l)!=query(mid+1)){
			if(q.first+q.second<limt){
				if(q.first==0 && q.second==0) pos=l;
				solve(l+1,mid);
			}else if(q.second>minr){
				solve(l,mid);
			}
		}
	}
}
int find_best(int n){
	for(int i=max(0,n/2-250),j=0;j<500 && i<n;i++,j++){
		pii q=query(i);
		int s=q.first+q.second;
		limt=max(limt,s);
		// s;
		if(s>=0 && (ll)s*s*s*s>n) break;
	}
	minr=pos=-1;
	solve(0,n-1);
	return pos;
}

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