Submission #90019

#	Time	Username	Problem	Language	Result	Execution time	Memory
90019		nikolapesic2802	The Big Prize (IOI17_prize)	C++14	0 / 100	12 ms	9720 KiB

prize

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

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

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