#include "grader.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,rev;
ll kuy(ll x) {
if(!rev) return x;
return n-x+1;
}
ll small(ll l, ll r, ll a) {
Guess(kuy(l));
ll res=Guess(kuy(r));
// printf("res = %d\n",res);
if (res==0) return (l+r)/2;
if (res==1) return r;
return l;
}
ll solve(ll l, ll r, ll a) {
// printf("solve [%d, %d] : %d [%d, %d]\n",kuy(l),kuy(r),a,l,r);
if(l==r) return l;
if(r-l+1<=3) return small(l,r,a);
if(a==l) {
ll b = (l*2+r)/3;
ll c = (l+2*r)/3;
ll tmp1 = Guess(kuy(b)), tmp2 = Guess(kuy(c));
// printf("b = %d c = %d tmp = %d and %d (%d, %d)\n",kuy(b),kuy(c),tmp1,tmp2,b,c);
if(a!=b && tmp1==0) return (a+b)/2;
if(b!=c && tmp2==0) return (b+c)/2;
if(tmp2==-1) {
if(tmp1==-1) return solve(l,(a+b)/2,c);
else return solve((a+b)/2+1,(b+c)/2,c);
}
else return solve((b+c)/2+1,r,c);
}
else if(l<=a && a<=r) {
ll b = (l+2*r)/3;
ll tmp = Guess(kuy(b));
// printf("b = %d (%d)\n",kuy(b),b);
assert(a!=b);
if(a!=b && tmp==0) return (a+b)/2;
if(tmp==-1) return solve(l,(a+b)/2,b);
else return solve((a+b)/2+1,r,b);
}
else {
ll b = l+r-a;
// printf("b = %d (%d)\n",kuy(b));
ll tmp = Guess(kuy(b));
if(a!=b && tmp==0) return (a+b)/2;
if(b < a) {
if(tmp==1) return solve(l,(l+r)/2,b);
return solve((l+r)/2+1,r,b);
}
else {
if(tmp==1) return solve((l+r)/2+1,r,b);
return solve(l,(l+r)/2,b);
}
}
}
int HC(int N) {
n = N;
Guess(N);
ll tmp = Guess(1);
if(tmp==0) return (1+N)/2;
rev = 0;
if(tmp==1) rev = 1;
// printf("rev = %d\n",rev);
if(rev) Guess(N);
return kuy(solve(1,N,1));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
1268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
773 ms |
8312 KB |
Output isn't correct - alpha = 0.000000000000 |
