#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
map<int, vector<int>> M, Li;
vector<int> self_ask(int i){
if(!M.count(i)) M[i] = ask(i); vector<int> r = M[i];
Li[r[0] + r[1]].push_back(i);
return r;
}
vector<int> b;
bool failed = false, done = false, un = true;
mt19937 rng(0);
int cc, ans;
void solve(int l, int r, int lc, int rc){
if(l > r || lc == rc) return;
int L = (l + r) / 2, R = (l + r) / 2 + 1, F = 0;
int c; vector<int> a;
while(true){
c = F ? R++ : L--; F ^= 1;
a = self_ask(c);
if(a[0] + a[1] == 0){
done = true; failed = true; ans = c;
}
if(un || a[0] + a[1] > cc){
failed = true; un = false; cc = a[0] + a[1];
return;
}
if(a[0] + a[1] == cc || R - L - 1 == rc - lc){
break;
}
}
if(R - L + 1 == rc - lc) return;
if(c == L + 1){
solve(l, L, lc, a[0]); if(failed) return;
solve(R, r, a[0] + (R - L - 2), rc); if(failed) return;
}else{
solve(l, L, lc, a[0] - (R - L - 2)); if(failed) return;
solve(R, r, a[0], rc); if(failed) return;
}
}
int find_best(int n) {
cc = n;
do{
failed = false;
solve(0, n - 1, 0, cc);
if(done) break;
}while(failed);
if(done){
return ans;
}
}
Compilation message
prize.cpp: In function 'std::vector<int> self_ask(int)':
prize.cpp:8:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
8 | if(!M.count(i)) M[i] = ask(i); vector<int> r = M[i];
| ^~
prize.cpp:8:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
8 | if(!M.count(i)) M[i] = ask(i); vector<int> r = M[i];
| ^~~~~~
prize.cpp: In function 'int find_best(int)':
prize.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
56 | }
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 KB |
Output is correct |
2 |
Correct |
1 ms |
208 KB |
Output is correct |
3 |
Correct |
1 ms |
296 KB |
Output is correct |
4 |
Correct |
1 ms |
208 KB |
Output is correct |
5 |
Correct |
1 ms |
208 KB |
Output is correct |
6 |
Correct |
1 ms |
208 KB |
Output is correct |
7 |
Correct |
1 ms |
308 KB |
Output is correct |
8 |
Correct |
0 ms |
300 KB |
Output is correct |
9 |
Correct |
0 ms |
208 KB |
Output is correct |
10 |
Correct |
0 ms |
208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
308 KB |
Output is correct |
3 |
Correct |
1 ms |
208 KB |
Output is correct |
4 |
Correct |
0 ms |
292 KB |
Output is correct |
5 |
Correct |
1 ms |
292 KB |
Output is correct |
6 |
Correct |
0 ms |
300 KB |
Output is correct |
7 |
Correct |
1 ms |
304 KB |
Output is correct |
8 |
Correct |
1 ms |
304 KB |
Output is correct |
9 |
Correct |
0 ms |
300 KB |
Output is correct |
10 |
Correct |
1 ms |
312 KB |
Output is correct |
11 |
Correct |
1 ms |
312 KB |
Output is correct |
12 |
Correct |
0 ms |
304 KB |
Output is correct |
13 |
Correct |
3 ms |
336 KB |
Output is correct |
14 |
Incorrect |
4 ms |
336 KB |
answer is not correct |
15 |
Halted |
0 ms |
0 KB |
- |