이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 nxt=l+r-last;
nxt=max(nxt,1);
nxt=min(nxt,n);
int x=Guess(nxt);
if (!x)
return (last+nxt)/2;
if ((x>0&&nxt>last)||(x<0&&nxt<last))
return g(min((last+nxt)/2+1,r),r,nxt);
return g(l,max((last+nxt-1)/2,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);
}
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;
}
if (N<6){
Guess(N);
return f(N,1);
}
dp[0]=1;
dp[1]=3;
for (int i=2;i<40;i++)
dp[i]=dp[i-2]+(1LL<<i);
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |