제출 #646193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
646193		piOOE	커다란 상품 (IOI17_prize)	C++17	20 / 100	52 ms	5224 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"

using namespace std;
using Query = vector<int>;

int find_best(int n) {
    vector<Query> value(n);

    auto query = [&](int i) -> Query {
        if (value[i].empty()) value[i] = ask(i);
        return value[i];
    };

    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 = query(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 = query(0);
    if (valid(L)) {
        return 0;
    }

    Query R = query(n - 1);
    if (valid(R)) {
        return n - 1;
    }

    dfs(0, n - 1, L, R);

    return ans;
}

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