#include "prize.h"
#include <bits/stdc++.h>
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 500;
int find_best(int n) {
map<int, vector<int>> mp;
auto _ask = [&](int x) {
if (mp.count(x)) return mp[x];
auto res = ask(x);
if (res[0] + res[1] == 0) return res;
return mp[x] = res;
};
int mx = 0;
for (int i = 0; i < min(n, N); i++) {
auto res = _ask(i);
mx = max(mx, res[0] + res[1]);
if (res[0] + res[1] == 0) return i;
}
auto solve = [&](auto&& s, vector<int> ask, int ml, int mr) -> void {
if (ml > mr || ask.empty()) return;
int want = (ml + mr) / 2;
int tl = 0, tr = sz(ask) - 1, ans = -1;
while (tl <= tr) {
int mid = (tl + tr) / 2;
auto res = _ask(mid);
if (res[0] + res[1] < mx) {
ask.erase(ask.begin() + mid);
tr--; continue;
}
else {
if (res[0] >= want) ans = mid, tr = mid - 1;
else tl = mid + 1;
}
}
if (!~ans) return;
if (ans - 2 >= 0) {
s(s, vector<int>(ask.begin(), ask.begin() + ans - 1), ml, want - 1);
}
if (ans + 1 < sz(ask)) {
s(s, vector<int>(ask.begin() + ans + 1, ask.end()), want + 1, mr);
}
};
vector<int> idx(n);
iota(all(idx), 0);
solve(solve, idx, 1, mx);
assert(0);
return -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
2904 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
2648 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
