Submission #260152

#	Time	Username	Problem	Language	Result	Execution time	Memory
260152		andreiomd	The Big Prize (IOI17_prize)	C++11	92.63 / 100	66 ms	416 KiB

prize

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

using namespace std;

typedef pair < int, int > PII;

int N;
int Candy_Sum = 0;

///
inline PII Get_Ans (int pos)
{
    vector < int > res = ask(pos);

    return {res[0], res[1]};
}

inline bool IsDiamond (PII X)
{
    return ((X.first + X.second) == 0);
}

inline bool IsCandy (PII X)
{
    return ((X.first + X.second) == Candy_Sum);
}
///

inline int Go (int Left, int Right)
{
    if(Left > Right)
        return 0;

    if(Left == Right)
        return Left;

    int Mid = ((Left + Right) >> 1);
    PII Now = Get_Ans(Mid);

    if(IsDiamond(Now))
        return Mid;

    if(Now.first)
        return Go(Left, Mid - 1);

    return Go(Mid + 1, Right);
}

inline int F (int Left, int Right, int less_to_left, int less_to_right)
{
    if(Left > Right)
        return 0;

    if(Left == Right)
    {
        if(IsDiamond(Get_Ans(Left)))
            return Left;

        return 0;
    }

    int Mid = ((Left + Right) >> 1);
    PII Now = Get_Ans(Mid);

    if(IsDiamond(Now))
        return Mid;

    int i = Mid - 1, j = Mid + 1, pos = 0;
    bool found = 0;

    if(IsCandy(Now))
        found = 1, pos = Mid;

    ///
    while(!found && (i >= Left || j <= Right))
    {
        if(i >= Left)
        {
            PII curr = Get_Ans(i);

            if(IsDiamond(curr))
                return i;

            if(!IsCandy(curr))
                --i;
            else
            {
                found = 1, pos = i, Now = curr;

                break;
            }
        }

        if(j <= Right)
        {
            PII curr = Get_Ans(j);

            if(IsDiamond(curr))
                return j;

            if(!IsCandy(curr))
                ++j;
            else
            {
                found = 1, pos = j, Now = curr;

                break;
            }
        }
    }
    ///

    if(!found)
        return 0;

    Mid = pos;

    int ans = 0;

    int ext_left = Now.first - less_to_left;
    int ext_right = Now.second - less_to_right;

    if(!ext_left && !ext_right)
        return 0;

    if(ext_left && ext_right)
    {
        if(ext_left > ext_right)
        {
            ans = F(Left, Mid - 1, less_to_left, Now.second);

            if(!ans)
                ans = F(Mid + 1, Right, Now.first, less_to_right);
        }
        else
        {
            ans = F(Mid + 1, Right, Now.first, less_to_right);

            if(!ans)
                ans = F(Left, Mid - 1, less_to_left, Now.second);
        }
    }
    else
    {
        if(ext_left)
            ans = F(Left, Mid - 1, less_to_left, Now.second);
        else
            ans = F(Mid + 1, Right, Now.first, less_to_right);
    }

    return ans;
}

int find_best(int n)
{
    N = n;

    for(int i = 0; i < min(N, 476); ++i)
    {
        PII Now = Get_Ans(i);

        if(IsDiamond(Now))
            return i;

        Candy_Sum = max(Candy_Sum, Now.first + Now.second);
    }

    if(Candy_Sum == 1)
        return Go(0, N - 1);

    return F(0, N - 1, 0, 0);
}

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