Submission #1082338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082338		MMihalev	The Big Prize (IOI17_prize)	C++14	90 / 100	51 ms	2408 KiB

prize

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include "prize.h"
using namespace std;
const int MAX_N=2e5+4;
int asked[MAX_N][2];
bool used[MAX_N];
int qq;
pair<int,int>query(int pos)
{
    if(used[pos])return {asked[pos][0],asked[pos][1]};

    if(qq>10000)while(1);
    used[pos]=1;
    qq++;
    auto ve=ask(pos);
    asked[pos][0]=ve[0];
    asked[pos][1]=ve[1];
    return {ve[0],ve[1]};
}
int find_best(int n)
{
    int prevpos=-1;
    int qq=500;
    int big=-1e9;
    while(qq--)
    {
        prevpos++;
        auto cur=query(prevpos);
        int all=cur.first+cur.second;
        if(all==0)return prevpos;
        big=max(big,all);
    }
    while(1)
    {
        prevpos++;
        auto cur=query(prevpos);
        int all=cur.first+cur.second;
        if(all==big)
        {
            int l=prevpos,r=n-1;
            while(l<=r)
            {
                int mid=(l+r)/2;
                auto cur2=query(mid);
                if(cur2==cur)
                {
                    prevpos=mid;
                    l=mid+1;
                }
                else r=mid-1;
            }
        }
        else
        {
            if(all==0)return prevpos;
        }
    }
}

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