Submission #1260012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260012		Faggi	The Big Prize (IOI17_prize)	C++20	20 / 100	30 ms	1428 KiB

prize

#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i,n) for(i=0; i<n; i++)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;

vector<int> ask(int i);

const int MAXM=447;

map<ll,vector<int>>memo;
ll ans=0;
int N;
bool enc=0;
int maxi=0; 

vector<int>cons(ll x)
{
    if(enc)
        return {N,N};
    auto it=memo.find(x);
    if(it==memo.end())
        memo[x]=ask(x);
    if(memo[x][0]+memo[x][1]==0)
    {
        enc=1;
        ans=x;
    }
    return memo[x];
}

bool lolip(ll x)
{
    int sumx = cons(x)[0] + cons(x)[1];
    if(sumx==0) enc=1, ans=x; 
    return sumx < maxi; 
}

void solve(ll l, ll r, ll il, ll ir)
{
    if(il==ir||enc)
        return;
    if(l==r)
    {
        cons(l);
        return;
    }

    ll mid=(l+r)/2;
    while(!enc && mid>=l && lolip(mid)) mid--; 
    if(enc) return;
    if(mid>=l){
        solve(l,mid,il,cons(mid)[0]);
        if(enc) return;
        solve((l+r)/2+1,r,cons(mid)[0]+abs(((l+r)/2)-mid),ir);
    }
}

int find_best(int n) {
    ll i;
    N=n;
    maxi=0;

    for(i=0; i<min(MAXM,n); i++){
        int s = cons(i)[0]+cons(i)[1];
        maxi = max(maxi,s);
        if(enc) break;
    }

    int a=0, b=n-1;
    while(!enc && a<n && cons(a)[0]+cons(a)[1]!=maxi) a++;
    while(!enc && b>=0 && cons(b)[0]+cons(b)[1]!=maxi) b--;

    if(!enc) solve(a,b,cons(a)[0],cons(b)[0]);

    return ans;
}

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