Submission #260144

#TimeUsernameProblemLanguageResultExecution timeMemory
260144andreiomdThe Big Prize (IOI17_prize)C++11
92.51 / 100
63 ms384 KiB
#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;

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

    if(!ans && Now.first != less_to_left)
        ans = F(Left, Mid - 1, less_to_left, Now.second);

    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);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...