Submission #547580

#	Time	Username	Problem	Language	Result	Execution time	Memory
547580		Monarchuwu	The Big Prize (IOI17_prize)	C++17	100 / 100	53 ms	10716 KiB

prize

#include "prize.h"
#include<set>
using namespace std;

const int MAXN = 2e5 + 8;
int ans;
int prf[MAXN];
set<int> s[MAXN];

bool dnc(int l, int r) {
    if (l > r) return false;
    int m = (l + r) >> 1;
    vector<int> a = ask(m);
    int sum = a[0] + a[1];
    prf[m] = a[0];
    if (sum == 0) { ans = m; return true; }

    auto it = s[sum].insert(m).first;
    if (it == s[sum].begin() ? a[0] : prf[*prev(it)] != prf[m])
        if (dnc(l, m - 1)) return true;

    if (next(it) == s[sum].end() ? a[1] : prf[m] != prf[*next(it)])
        if (dnc(m + 1, r)) return true;

    return false;
}

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

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