제출 #677707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
677707		bashkort	커다란 상품 (IOI17_prize)	C++17	100 / 100	46 ms	344 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: 80 / 80