Submission #366051

#	Time	Username	Problem	Language	Result	Execution time	Memory
366051		denkendoemeer	The Big Prize (IOI17_prize)	C++14	100 / 100	55 ms	2304 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"
using namespace std;
vector<pair<int,int>>ans;
unordered_map<int,set<int>>mp;
int calc(int st,int dr)
{
    if (st>dr)
        return -1;
    int mij=(st+dr)/2;
    vector<int>aux=ask(mij);
    ans[mij]=make_pair(aux[0],aux[1]);
    int sum=ans[mij].first+ans[mij].second;
    if (sum==0)
        return mij;
    auto it=mp[sum].insert(mij).first;
    if (it==mp[sum].begin() || ans[*prev(it)].first!=ans[mij].first){
        int auxi=calc(st,mij-1);
        if (auxi!=-1)
            return auxi;
    }
    if (it==--mp[sum].end() || ans[*next(it)].second!=ans[mij].second){
        int auxi=calc(mij+1,dr);
        if (auxi!=-1)
            return auxi;
    }
    return -1;
}
int find_best(int n)
{
    ans.resize(n);
    return calc(0,n-1);
}

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