Submission #105426

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

prize

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

using namespace std;

int rangMax;

pair<int,int> ans[200005];

int found = -1;


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)
{
    if(found != -1) return;

    int mid = (st + dr) / 2, pos = mid;

    while(found == -1 && pos <= dr && rang(pos) != rangMax)
    {
        if(rang(pos) == 0) found = pos;
        ++pos;
    }

    if(found != -1) return;

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

        if(found != -1) return;

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

        return;
    }


    if(found != -1) return;

    pos = mid;
    while(found == -1 && pos >= st && rang(pos) != rangMax)
    {
        if(rang(pos) == 0) found = pos;
        pos--;
    }

    if(found != -1) return;

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

        if(found != -1) return;

        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);
    assert(found != -1);
    return found;
}

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