Submission #1259998

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259998		Faggi	The Big Prize (IOI17_prize)	C++20	97.24 / 100	16 ms	960 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=450;

map<ll,vector<int>>memo;
ll N, ans=0;
bool enc=0;
vector<int>cons(ll x)
{
    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)
{
    vector<int>q=cons(x);
    ll cant=q[0]+q[1];
    cant=N-cant;
    if(cant*cant+1>N)
        return 1;
    return 0;
}

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)
        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 a=0, i, b=n-1;
    N=n;
    for(i=0; i<MAXM; i++)
    {
        if(lolip(i))
        {
            a=i;
            break;
        }
    }
    for(i=n-1; i>=n-MAXM; i--)
    {
        if(lolip(i))
        {
            b=i;
            break;
        }
    }

    solve(a,b,ask(a)[0],ask(b)[0]);

	return ans;
}

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