| # | Time | Username | Problem | Language | Result | Execution time | Memory | 
|---|---|---|---|---|---|---|---|
| 1080993 | qwusha | The Big Prize (IOI17_prize) | C++17 | 0 ms | 0 KiB | 
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
            }
        }
        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];
    }
}
