Submission #648218

#	Time	Username	Problem	Language	Result	Execution time	Memory
648218		rafatoa	The Big Prize (IOI17_prize)	C++17	97.63 / 100	64 ms	400 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
 
using namespace std;
using Query = vector<int>;
 
int find_best(int n) {
    auto valid = [&](Query x) {
        return x[0] + x[1] == 0;
    };
 
    int ans = -1;
 
    function<void(int, int, Query, Query)> dfs = [&](int l, int r, Query L, Query R) {
        if (l + 1 >= r || ans != -1 || L == R) {
            return;
        }
 
        int mid = (l + r) >> 1;
        Query M = ask(mid);
 
        if (valid(M)) {
            ans = mid;
            return;
        }
 
        // if (L[0] + L[1] == R[0] + R[1] && L[0] + L[1] > M[0] + M[1] && L[1] - R[1] == 1) {
        //     return;
        // }
 
        dfs(l, mid, L, M), dfs(mid, r, M, R);
    };
 
    Query L = ask(0);
    if (valid(L)) {
        return 0;
    }
 
    Query R = ask(n - 1);
    if (valid(R)) {
        return n - 1;
    }
 
    dfs(0, n - 1, L, R);
 
    return ans;
}

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