#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
vector<pii> sto;
pii Ask(int x) {
if (sto[x].ff != -1) return sto[x];
// cerr << "ASK " << x << endl;
vector<int> res = ask(x);
return (sto[x] = make_pair(res[0], res[1]));
}
int brainless(int n) {
for (int i = 0; i < n; i++) {
pii ret = Ask(i);
if (ret.ff + ret.ss == 0) return i;
}
throw runtime_error("no answer?");
}
vector<int> bit;
void update(int pos) {
pos++;
int n = (int)(bit.size()) - 1;
while (pos <= n) {
bit[pos]++;
pos += (pos & -pos);
}
}
int pquery(int pos) {
int n = (int)(bit.size()) - 1;
int res = 0;
while (pos >= 1) {
res += bit[pos];
pos -= (pos & -pos);
}
return res;
}
int query(int l, int r) {
if (l > r) return 0;
l++; r++;
return pquery(r) - pquery(l - 1);
}
int find_best(int n) {
sto.clear(); sto.resize(n, make_pair(-1, -1));
bit.clear(); bit.resize(n + 1, 0);
if (n <= 5000) return brainless(n);
// only 472 max: 1 4 21 446 []
set<int> asked;
int times = 472;
vector<int> v(n);
for (int i = 0; i < n; i++) v[i] = i;
auto pickmid = [&](int lb, int rb) -> int {
set<int>::iterator it;
int mid = v[(lb + rb) >> 1];
it = asked.lower_bound(mid);
if (it != asked.end() && *it < v[rb]) return *it;
it = asked.upper_bound(mid);
if (it != asked.begin() && *(--it) >= v[lb]) return *it;
return mid;
};
auto findpos = [&](int tar) -> int {
int lb = 0, rb = (int)(v.size()) - 1;
while (lb < rb) {
int mid = (lb + rb) >> 1;
if (v[mid] == tar) return mid;
if (v[mid] < tar) lb = mid + 1;
else rb = mid;
}
return lb;
};
auto findone = [&]() -> int {
int lb = 0, rb = (int)(v.size()) - 1;
while (lb < rb) {
int mid = pickmid(lb, rb);
int pos = findpos(mid);
pii ret = Ask(mid); asked.insert(mid);
if (ret.ff + ret.ss < times) return mid;
if (query(0, mid - 1) < ret.ff) rb = pos - 1;
else lb = pos + 1;
}
return v[lb];
};
for (int t = 1; t <= times; t++) {
int res = findone();
pii ret = Ask(res);
if (ret.ff + ret.ss == 0) return res;
update(res);
for (int i = 0; i < (int)(v.size()); i++) {
if (v[i] == res) {
v.erase(v.begin() + i);
break;
}
}
}
// throw runtime_error("oh no");
return -1;
}
Compilation message
prize.cpp: In function 'int pquery(int)':
prize.cpp:32:6: warning: unused variable 'n' [-Wunused-variable]
32 | int n = (int)(bit.size()) - 1;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
3668 KB |
Integer -1 violates the range [0, 199999] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
3416 KB |
Integer -1 violates the range [0, 199999] |
| 2 |
Halted |
0 ms |
0 KB |
- |
