제출 #1080994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1080994		qwusha	커다란 상품 (IOI17_prize)	C++17	0 / 100	3 ms	416 KiB

prize

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
const ll inf = 1e18;
const ll mod = 1e9 + 7;

#include <prize.h>

int find_best(int n) {
    vector<pair<int, int>> s;
    for (int i = 0; i < min(n, 500); i++) {
        vector<int> res = ask(i);
        s.push_back({res[0] + res[1], -i});
    }
    sort(s.rbegin(), s.rend());
    int ind = -(s[0].se);
    int cur = s[0].fi;
    int val = s[0].fi;
    while(true) {
        int l = ind, r = n;
        int last = -1;
        while (r - l > 1) {
            int m = (r + l) / 2;
            auto an = ask(m);
            if (cur == an[1]) {
                l = m;
            } else {
                r = m;
                last = an[1];
            }
        }
        if (last == 0) {
            return r;
        }
        ind = r;
        vector<int> an = ask(ind);
        while (an[0] + an[1] < val) {
            if (an[1] == 0) {
                return ind;
            }
            ind++;
            an = ask(ind);
        }
        last = an[1];
    }
}

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