Submission #105423

#	Time	Username	Problem	Language	Result	Execution time	Memory
105423		Alexa2001	The Big Prize (IOI17_prize)	C++17	97.42 / 100	60 ms	2080 KiB

prize

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

using namespace std;

vector<int> possible;
int rangMax;

pair<int,int> ans[200005];

pair<int,int> query(int x)
{
    if(ans[x] != make_pair(-1, -1)) return ans[x];
    auto res = ask(x);
    ans[x] = {res[0], res[1]};
    return ans[x];
}

int rang(int x)
{
    return query(x).first + query(x).second;
}


void divide(int st, int dr, int outleft, int outright)
{
    int mid = (st + dr) / 2, pos = mid;

    while(pos <= dr && rang(pos) != rangMax)
    {
        possible.push_back(pos);
        ++pos;
    }

    if(pos <= dr)
    {
        if(query(pos).second > outright)
            divide(pos+1, dr, query(pos).first, outright);

        if(query(pos).first > outleft + (pos - mid))
            divide(st, mid-1, outleft, query(pos).second + (pos - mid));

        return;
    }

    pos = mid;
    while(pos >= st && rang(pos) != rangMax)
    {
        possible.push_back(pos);
        pos--;
    }

    if(pos >= st)
    {

        if(query(pos).first > outleft)
            divide(st, pos-1, outleft, query(pos).second);

        if(query(pos).second > outright + (mid - pos))
            divide(mid+1, dr, query(pos).first + (mid - pos), outright);

        return;
    }
}

int find_best(int n)
{
    int i;
    for(i=0; i<n; ++i) ans[i] = {-1, -1};

    for(i=0; i<500 && i<n; ++i)
        rangMax = max(rangMax, rang(i));

    divide(0, n-1, 0, 0);

    for(auto it : possible)
        if(rang(it) == 0) return it;
    assert(0);
}

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