#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> ask(int i);
vector<int> res[200005];
void query(int i){
if(res[i].empty())
res[i] = ask(i);
}
bool pos[200005];
set<int> ls[200005];
int ans = -1;
void solve(int l, int r){
if(ans != -1) return;
while(l <= r && pos[l++]);
while(l <= r && pos[r--]);
if(r < l) return;
int m = (l + r) >> 1;
query(m);
int s = res[m][0] + res[m][1];
if(s == 0){
ans = m;
return;
}
pos[m] = 1;
set<int>::iterator lll = ls[s].find(m);
set<int>::iterator rrr = lll--;
set<int>::iterator it = rrr++;
if(rrr != ls[s].end()){
int rr = *rrr;
if(res[m][0] == res[rr][0]){
for(int i = m + 1; i < rr; i++)
pos[i] = 1;
}
}
if(it != ls[s].begin()){
int ll = *lll;
if(res[ll][0] == res[ll][0])
for(int i = ll + 1; i < m; i++)
pos[i] = 1;
}
solve(l, m);
solve(m, r);
}
int find_best(int n) {
solve(0, n - 1);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
27 ms |
28800 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
27 ms |
28704 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |