Submission #90017

#	Time	Username	Problem	Language	Result	Execution time	Memory
90017		nikolapesic2802	The Big Prize (IOI17_prize)	C++14	100 / 100	68 ms	10456 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;

const int N=2e5+5;
map<int,vector<int> > m[N];
int sol=-1;
void solve(int l,int r)
{
    if(sol!=-1||l>r)
        return;
    int mid=(l+r)>>1;
    vector<int> cur=ask(mid);
    int sum=cur[0]+cur[1];
    if(sum==0)
    {
        sol=mid;
        return;
    }
    auto it=m[sum].upper_bound(mid);
    int left=1,right=1;
    if(it!=m[sum].begin()&&m[sum].size())
    {
        it--;
        if((*it).second[1]==cur[1])
            left=0;
        it++;
    }
    if(it!=m[sum].end())
    {
        if((*it).second[0]==cur[0])
            right=0;
    }
    m[sum][mid]=cur;
    if(left)
        solve(l,mid-1);
    if(right)
        solve(mid+1,r);
}
int find_best(int n) {
    solve(0,n-1);
    return sol;
}

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