#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
int n;
long long dp[40];
int calc(int n, int e){
return (e==1?n:e-n+1);
}
int g(int l, int r, int last){
if (l==r)
return l;
if (l>r)
swap(l,r);
int sz=1;
while (sz<r-l+1)
sz=sz*2+1;
int mid=0;
if (last<=r-sz)
mid=r-sz/2;
else if (last>=l+sz)
mid=l+sz/2;
else if (last<=l)
mid=last+sz/2;
else
mid=last-sz/2;
int nxt=mid*2-last;
int x=Guess(nxt);
if (!x)
return mid;
if ((x>0&&nxt>last)||(x<0&&nxt<last))
return g(min(mid+1,r),r,nxt);
return g(l,max(mid-1,l),nxt);
}
int f(int n, int e){
if (n==1)
return e;
if (n==2)
return calc((3-Guess(e))/2,e);
if (n==3)
return calc(2-Guess(e),e);
if (n<6){
int x=Guess(calc(n-2,e));
if (!x)
return calc(n-1,e);
if (x<0)
return calc(n,e);
return f(n-2,e);
}
if (n<8){
int x=Guess(calc(1,e));
if (!x)
return calc(4,e);
if (x>0)
return calc(Guess(calc(3,e))+2,e);
return calc(Guess(calc(n*2-3,e))+n-1,e);
}
int i=lower_bound(dp,dp+40,n)-dp-2;
int x=Guess(calc(dp[i]-2,e));
if (!x)
return calc((dp[i]+n-2)/2,e);
if (x<0)
return g(calc((dp[i]+n-2)/2+1,e),calc(n,e),calc(dp[i]-2,e));
x=Guess(calc(dp[i],e));
if (!x)
return calc(dp[i]-1,e);
if (x<0)
return f(dp[i],e);
return g(calc(dp[i],e),calc((dp[i]+n-3)/2,e),calc(dp[i],e));
}
int32_t HC(int32_t N){
n=N;
if (N==1)
return 1;
if (N==2){
Guess(1);
return (Guess(2)+3)/2;
}
dp[0]=1;
dp[1]=3;
dp[2]=7;
for (int i=3;i<40;i++)
dp[i]=dp[i-2]+(1LL<<i);
if (N<6){
Guess(N);
return f(N,1);
}
int mid=(1+N)>>1;
Guess(mid-1);
int x=Guess(mid+1);
if (!x)
return mid;
if (x<0)
return f(mid+1,1);
return f(N-mid,N);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
6748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
7028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
6748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
636 ms |
24532 KB |
Output is partially correct - alpha = 0.800000000000 |
