Submission #1134946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134946		pokmui9909	The Big Prize (IOI17_prize)	C++17	20 / 100	14 ms	11384 KiB

prize

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

set<ll> S[200005];
ll L[200005];

ll Qry;

ll dnc(ll l, ll r){
    if(l > r) return -1;
    ll m = (l + r) / 2;
    Qry++;
    assert(Qry <= 4000);
    auto t = ask(m);
    ll v = t[0] + t[1];
    if(v == 0) return m;
    S[v].insert(m);
    L[m] = t[0];


    auto it = S[v].lower_bound(m);
    if(it == S[v].begin() || L[*prev(it)] != L[m]){
        ll f = dnc(l, m - 1);
        if(f != -1) return f;
    }
    if(it == prev(S[v].end()) || L[*next(it)] != L[m]){
        ll f = dnc(m + 1, r);
        if(f != -1) return f;
    }
    return -1;
}

int find_best(int N){
    return dnc(0, N - 1);
}

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