Submission #654454

#	Time	Username	Problem	Language	Result	Execution time	Memory
654454		Hanksburger	The Big Prize (IOI17_prize)	C++17	100 / 100	73 ms	10688 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
set<int> s[200005];
int a[200005];
int f(int l, int r)
{
    if (l>r)
        return -1;
    int m=(l+r)/2, k;
    vector<int> v=ask(m);
    if (!(k=(a[m]=v[0])+v[1]))
        return m;
    auto it=s[k].insert(m).first;
    if (it==s[k].begin() || a[*prev(it)]!=a[m])
    {
        int x=f(l, m-1);
        if (x>=0)
            return x;
    }
    if (it==--s[k].end() || a[*next(it)]!=a[m])
    {
        int x=f(m+1, r);
        if (x>=0)
            return x;
    }
    return -1;
}
int find_best(int N)
{
    return f(0, N-1);
}

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