#include "grader.h"
#include<bits/stdc++.h>
using namespace std;
int n,rev;
int kuy(int x) {
if(!rev) return x;
return n-x+1;
}
int small(int l, int r, int a) {
Guess(kuy(l));
int res=Guess(kuy(r));
// printf("res = %d\n",res);
if (res==0) return (l+r)/2;
if (res==1) return r;
return l;
}
int solve(int l, int r, int 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) {
int b = (l*2+r)/3;
int c = (l+2*r)/3;
int 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) {
int b = (l+2*r)/3;
int tmp = Guess(kuy(b));
// printf("b = %d (%d)\n",kuy(b),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 {
int b = l+r-a;
if(b<1) b = 1;
if(b>n) b = n;
// printf("b = %d (%d)\n",kuy(b),b);
int 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,r,b);
}
else {
if(tmp==1) return solve((l+r)/2,r,b);
return solve(l,(l+r)/2,b);
}
}
}
int solve2(int n) {
int l = 1;
int r = n;
Guess(1);
int p = 1;
while (l < r) {
int z = r-l+1;
int res, side;
if (p == l) {
res = Guess(p = r), side = 0;
} else if (p == r) {
res = Guess(p = l), side = 1;
} else if (p < l) {
int q = r+(l-p);
if (q <= n) {
res = Guess(p = q);
side = 0;
} else {
Guess(p = (r <= n/2 ? r : l));
continue;
}
} else if (p > r) {
int q = l-(p-r);
if (q >= 1) {
res = Guess(p = q);
side = 1;
} else {
Guess(p = (r <= n/2 ? r : l));
continue;
}
} else {
assert(false);
}
int m = (l+r)/2;
if (side == 0) {
if (z % 2 == 0) {
if (res == 1) l = m+1;
else if (res == -1) r = m;
else assert(false);
} else {
if (res == 1) l = m+1;
else if (res == -1) r = m-1;
else l = r = m;
}
} else {
if (z % 2 == 0) {
if (res == 1) r = m;
else if (res == -1) l = m+1;
else assert(false);
} else {
if (res == 1) r = m-1;
else if (res == -1) l = m+1;
else l = r = m;
}
}
}
return l;
}
int HC(int N) {
if(N<=1000000) return solve2(N);
n = N;
Guess(N);
int 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 |
31 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
1272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
726 ms |
8216 KB |
Output is partially correct - alpha = 0.555555555556 |
