Submission #137801

#	Time	Username	Problem	Language	Result	Execution time	Memory
137801		ckodser	The Big Prize (IOI17_prize)	C++14	96.07 / 100	69 ms	5288 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>

#define ll int
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll maxn=2e5+500;
const ll inf=1e9+900;

vector<ll>  ansS[maxn];
ll mx=0;
vector<ll>  ASK(ll x){
    if(ansS[x].size())return ansS[x];
    ansS[x]=ask(x);
    mx=max(mx,ansS[x][0]+ansS[x][1]);
    return ansS[x];
}
ll N;
ll bild(ll l,ll r,ll L,ll R){
    l=max(l,0);
    r=min(r,N);
    if(l>=r)return -1;
    if(L+R==mx)return -1;
    ll mid=(l+r)/2;
    for(ll i=mid;i<r;i++){
	vector<ll> vec=ASK(i);
	if(vec[0]+vec[1]==mx){
	    ll XX=bild(l,mid,L,vec[1]+(mid-i)); 
	    if(XX!=-1)return XX;
	    XX=bild(i+1,r,vec[0],R);
	    if(XX!=-1)return XX;
	    return -1;
	}else{
	    if(vec[0]+vec[1]==0)return i;
	}
    }
    return bild(l,mid,L,R+(r-mid));
}

int find_best(int n) {
    N=n;
    if(n<=5000){
	for(ll i=0;i<n;i++){
	    vector<ll> vec=ask(i);
	    if(vec[0]+vec[1]==0)return i;
	}
    }
    for(ll i=0;i<440;i++){
	vector<ll> ans=ASK(i);
	if(ans[0]+ans[1]==0)return i;
    }
    return bild(0,n,0,0);
}

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