#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;
void solve(int l, int r, int cc, 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] > cc){
failed = true; cc = a[0] + a[1];
return;
}
if(a[0] + a[1] == cc || R - L - 1 == rc - lc){
break;
}
}
if(c == L + 1){
solve(l, L, cc, lc, a[0]); if(failed) return;
solve(R, r, cc, a[0] + (R - L - 2), rc); if(failed) return;
}else{
solve(l, L, cc, lc, a[0] - (R - L - 2)); if(failed) return;
solve(R, r, cc, a[0], rc); if(failed) return;
}
}
int find_best(int n) {
int cc = 1;
do{
failed = false;
solve(0, n - 1, cc, 0, cc);
}while(failed);
for(auto [i, p] : M){
if(p[0] + p[1] == 0){
return i;
}
}
return -1;
}
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:46:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
46 | for(auto [i, p] : M){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
288 KB |
Output is correct |
2 |
Correct |
1 ms |
272 KB |
Output is correct |
3 |
Correct |
1 ms |
292 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 |
0 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
208 KB |
Output is correct |
9 |
Correct |
1 ms |
292 KB |
Output is correct |
10 |
Correct |
0 ms |
208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
308 KB |
Output is correct |
2 |
Correct |
0 ms |
208 KB |
Output is correct |
3 |
Correct |
1 ms |
288 KB |
Output is correct |
4 |
Correct |
0 ms |
344 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 |
292 KB |
Output is correct |
8 |
Correct |
0 ms |
288 KB |
Output is correct |
9 |
Correct |
1 ms |
296 KB |
Output is correct |
10 |
Correct |
0 ms |
208 KB |
Output is correct |
11 |
Execution timed out |
3035 ms |
525732 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |