Submission #260105

#	Time	Username	Problem	Language	Result	Execution time	Memory
260105		andreiomd	The Big Prize (IOI17_prize)	C++11	20 / 100	7 ms	384 KiB

prize

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

using namespace std;

typedef pair < int, int > PII;

map < int, bool > mp;

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 >= 0 && !IsCandy(Get_Ans(i)))
        --i;
    if(!found && i >= 0)
        found = 1, pos = i;

    while(!found && j < N && !IsCandy(Get_Ans(j)))
        ++j;
    if(!found && j < N)
        found = 1, pos = j;

    Mid = pos;
    Now = Get_Ans(Mid);

    int ans = 0;

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

    if(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, 501); ++i)
    {
        PII Now = Get_Ans(i);

        if(IsDiamond(Now))
            return i;

        mp[Now.first + Now.second] = 1;

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

    for(auto it : mp)
        ++V;

    if(V <= 2)
        return Go(0, N - 1);

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

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:116:14: warning: variable 'it' set but not used [-Wunused-but-set-variable]
     for(auto it : mp)
              ^~

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