제출 #260129

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
260129		andreiomd	커다란 상품 (IOI17_prize)	C++11	90 / 100	92 ms	384 KiB

prize

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

using namespace std;

typedef pair < int, int > PII;

int N, V = 0;

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)
    {
        PII curr = Get_Ans(i);

        if(IsDiamond(curr))
            return i;

        if(!IsCandy(curr))
            --i;
        else
            break;
    }
    if(!found && i >= Left)
        found = 1, pos = i;
    ///

    ///
    while(!found && j <= Right)
    {
        PII curr = Get_Ans(j);

        if(IsDiamond(curr))
            return j;

        if(!IsCandy(curr))
            ++j;
        else
            break;
    }
    if(!found && j <= Right)
        found = 1, pos = j;
    ///

    if(!found)
        return 0;

    Mid = pos;
    if(Mid != ((Left + Right) >> 1))
        Now = Get_Ans(Mid);

    int ans = 0;

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

    if(!ans && Now.second != less_to_right)
        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: 70 / 80