Submission #827395

#	Time	Username	Problem	Language	Result	Execution time	Memory
827395		vjudge1	The Big Prize (IOI17_prize)	C++14	100 / 100	47 ms	11576 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = 2e5 ;
set<int> s[N + 1] ;
pair<int, int> ax[N + 1] ;
int rec(int l, int r)
{
    if(l > r)
        return -1 ;
    int mid = (l + r) >> 1, sum, mx = -1 ;
    vector<int> v = ask(mid) ;
    ax[mid] = {v[0], v[1]} ;
    sum = v[0] + v[1] ;
    s[sum].insert(mid) ;
    if(!sum)
        return mid ;
    auto lf = (s[sum].lower_bound(mid)), rg = (s[sum].upper_bound(mid)) ;
    lf-- ;
    if(lf == s[sum].begin() || ax[*lf].fi != ax[mid].fi)
        mx = max(mx, rec(l, mid - 1)) ;
    if(rg == s[sum].end() || ax[mid].fi != ax[*rg].fi)
        mx = max(mx, rec(mid + 1, r)) ;
    return mx ;
}
int find_best(int n)
{
    return rec(0, n - 1) ;
}
//signed main()
//{
//    return 0 ;
//}

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