#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
const int L=30;
int n,magic[L];
int Search(int l,int r,int last){
if(l==r)return l;
if(l>r)swap(l,r);
int sz=3;
while(sz<r-l+1)sz=sz*2+1;
int mid;
if(r-sz+1>last)mid=r-sz/2;
else if(l+sz-1<last)mid=l+sz/2;
else if(last<=l)mid=last+sz/2;
else mid=last-sz/2;
int nxt=mid*2-last;
int g=Guess(nxt);
if(g==0)return mid;
if((g>0)^(last<nxt))return Search(l,max(l,mid-1),nxt);
else return Search(min(r,mid+1),r,nxt);
}
int get(int x,bool inv){return inv?n-x+1:x;}
int Solve(int sz,bool inv){
if(sz==1)return get(1,inv);
if(sz==2)return Guess(get(1,inv))>0?get(1,inv):get(2,inv);
if(sz==3){
int g=Guess(get(1,inv));
return g==0?get(2,inv):g>0?get(1,inv):get(3,inv);
}
if(sz==4){
int g=Guess(get(3,inv));
if(g<0)return get(4,inv);
g=Guess(get(1,inv));
return g>0?get(1,inv):g==0?get(2,inv):get(3,inv);
}
if(sz==5){
int g=Guess(get(3,inv));
if(g<0)return get(5,inv);
if(g==0)return get(4,inv);
g=Guess(get(1,inv));
return g>0?get(1,inv):g==0?get(2,inv):get(3,inv);
}
if(sz==6){
int g=Guess(get(1,inv));
if(g>0){
g=Guess(get(3,inv));
return g>0?get(3,inv):g==0?get(2,inv):get(1,inv);
}else{
g=Guess(get(9,inv));
return g>0?get(6,inv):g==0?get(5,inv):get(4,inv);
}
}
if(sz==7){
int g=Guess(get(1,inv));
if(g>0){
g=Guess(get(3,inv));
return g>0?get(3,inv):g==0?get(2,inv):get(1,inv);
}else if(g<0){
g=Guess(get(11,inv));
return g>0?get(7,inv):g==0?get(6,inv):get(5,inv);
}else return get(4,inv);
}
int ptr=0;
while(magic[ptr]<sz)ptr++;
int tmp=magic[ptr-2];
int g=Guess(get(tmp-2,inv));
if(g==0)return get((tmp-2+sz)/2,inv);
if(g<0)return Search(get((tmp-2+sz)/2+1,inv),get(sz,inv),get(tmp-2,inv));
g=Guess(get(tmp,inv));
return g==0?get(tmp-1,inv):g<0?Solve(tmp,inv):Search(get(tmp,inv),get((tmp-2+sz-1)/2,inv),get(tmp,inv));
}
int HC(int N){
n=N;
if(n==1)return 1;
if(n==2){
Guess(1);
return Guess(2)>0?2:1;
}
if(n==3){
Guess(1);
int g=Guess(3);
return g<0?1:g==0?2:3;
}
magic[0]=1;
magic[1]=3;
magic[2]=7;
for(int i=3;i<L;i++)magic[i]=magic[i-2]+(1<<i);
int mid=n/2+1;
Guess(mid-2);
int g=Guess(mid);
return g==0?mid-1:g<0?Solve(mid,0):Solve(n-mid+1,1);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
1280 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
1075 ms |
22880 KB |
Output is partially correct - alpha = 1.000000000000 |
