Submission #1082716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082716		MMihalev	The Big Prize (IOI17_prize)	C++14	100 / 100	43 ms	11984 KiB

prize

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

    used[pos]=1;
    auto ve=ask(pos);
    asked[pos][0]=ve[0];
    asked[pos][1]=ve[1];
    kinds.insert(ve[0]+ve[1]);
    idx[ve[0]+ve[1]].insert(pos);
    return {ve[0],ve[1]};
}
bool useless(int l,int r)
{
    for(int x:kinds)
    {
        auto it1=idx[x].lower_bound(l);
        auto it2=idx[x].upper_bound(r);
        if(it1!=idx[x].begin() && it2!=idx[x].end())
        {
            it1--;
            int pos1=(*it1);
            int pos2=(*it2);
            if(query(pos2).first-query(pos1).first==0)return 1;
        }
    }
    return 0;
}
int ans=-1;
void rec(int l,int r)
{
    if(l>r)return;
    if(ans!=-1)return;
    int mid=(l+r)/2;
    auto cur=query(mid);
    if(cur.first+cur.second==0){ans=mid;return;}
    if(!useless(l,mid-1))rec(l,mid-1);
    if(!useless(mid+1,r))rec(mid+1,r);
}

int find_best(int n)
{
    rec(0,n-1);
    return ans;
}

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