#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(69420);
int n;
int solve(int l, int r, int prv){
// cout << l << " " << r << " " << prv << endl;
if(l == r)return l;
if(l == 1){
if(r <= 3){
int tmp = Guess(1);
if(tmp == 1)return 1;
if(tmp == 0)return 2;
return r;
}
int dist = (r - l + 1)/3, g = dist;
int tmp = Guess(g);
if(tmp == -1)return solve((g+r)/2 + 1, r, g);
if(tmp == 0)return (g+r)/2;
tmp = Guess(g+2);
if(tmp == 0)return g+1;
if(tmp == -1)return solve(1, g+2, g+2);
return solve(g+2, (g+r-1)/2, g+2);
}
else if(r == n){
if(r - l + 1 <= 3){
int tmp = Guess(n);
if(tmp == 1)return n;
if(tmp == 0)return n-1;
return l;
}
int dist = (r - l + 1)/4, g = r - dist + 1;
int tmp = Guess(g);
if(tmp == -1)return solve(l, (l+g-1)/2, g);
if(tmp == 0)return (l+g)/2;
tmp = Guess(g-2);
if(tmp == 0)return g-1;
if(tmp == -1)return solve(g-2, r, g-2);
return solve((g+l)/2 + 1, g-2, g-2);
}
else {
int mid = (l+r)>>1;
if(prv == mid){
int tmp = Guess(prv + 2);
if(tmp == -1)return solve(l, prv, prv+2);
if(tmp == 0)return prv+1;
if(tmp == 1)return solve(prv+2, r, prv+2);
}
int qq = max(1, 2*mid - prv);
qq = min(qq, n);
int tmp = Guess(qq);
if(prv < mid)tmp*=-1;
if(tmp == -1)return solve((qq + prv)/2 + 1, r, qq);
if(tmp == 0)return (qq+prv)/2;
return solve(l, (qq+prv-1)/2, qq);
}
}
int HC(int N){
n = N;
if(n <= 3){
Guess(n);
return solve(1, n, 1);
}
else {
int mid = n/2;
Guess(mid-1);
int tmp = Guess(mid+1);
if(tmp == 0)return mid;
if(tmp == 1)return solve(mid+1, n, mid+1);
return solve(1, mid+1, mid+1);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
6748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
6748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
6748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
409 ms |
8048 KB |
Output is partially correct - alpha = 0.250000000000 |
