제출 #775067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
775067		t6twotwo	커다란 상품 (IOI17_prize)	C++17	90 / 100	88 ms	300 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
int find_best(int N) {
    int mx = 0;
    for (int i = 0; i < 500; i++) {
        vector<int> t = ask(i);
        if (t[0] + t[1] == 0) {
            return i;
        }
        mx = max(mx, t[0] + t[1]);
    }
    int x = 500;
    while (1) {
        vector<int> t = ask(x);
        if (t[0] + t[1] == 0) {
            return x;
        }
        if (t[0] + t[1] != mx) {
            x++;
            continue;
        }
        int lo = x, hi = N - 1;
        while (lo < hi) {
            int mi = (lo + hi + 1) / 2;
            vector<int> v = ask(mi);
            if (v == t) {
                lo = mi;
            } else {
                hi = mi - 1;
            }
        }
        x = lo + 1;
    }
}

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