#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
bool asked[N];
vector<int> answer[N];
int mx = 0 ;
vector<int> get(int i){
if(asked[i])
return answer[i];
asked[i] = true;
return answer[i] = ask(i);
}
int solve(int s,int e){
if(s == e){
vector<int> cur = get(s);
if(cur[0] + cur[1] != 0) return -1;
return s;
}
vector<int> v1 = get(s);
if(v1[0] + v1[1] == 0) return s;
if(v1[0] + v1[1] != mx) return solve(s+1,e);
vector<int> v2 = get(e);
if(v2[0] + v2[1] == 0) return e;
if(v2[0] + v2[1] != mx) return solve(s,e-1);
if(v1[0] == v2[0]) return -1;
if(s == e - 1) return -1;
int mid = (s + e) / 2;
if(rand() % 2){
int idx = solve(s,mid-1);
if(idx != -1) return idx;
return solve(mid+1,e);
}
int idx = solve(mid+1,e);
if(idx != -1) return idx;
return solve(s,mid-1);
}
int find_best(int n) {
srand(time(0));
int num = min(n,480);
for(int i=0;i<num;i++){
vector<int> res = get(i);
int cur = res[0] + res[1];
mx = max(mx,cur);
}
return solve(0,n-1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
6904 KB |
Integer -1 violates the range [0, 199999] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
6904 KB |
Integer -1 violates the range [0, 199999] |
| 2 |
Halted |
0 ms |
0 KB |
- |
