代码

typedef unsigned long U;
typedef unsigned long long U64;
static char **v;static U c;
U getauxval(U k){char**p=v+c+1;while(*p)++p;U*q=(U*)(p+1);while(*q){if(*q==k)return q[1];q+=2;}return 0;}

#ifndef BRACKET
#define BRACKET 65536
#endif

int binary_search(const unsigned *a,int n,unsigned x){
 unsigned g=(unsigned)(((U64)x*(unsigned)n)>>32);
 unsigned l=g>BRACKET?g-BRACKET:0;
 unsigned r=g+BRACKET<(unsigned)n?g+BRACKET:(unsigned)n-1;
 __builtin_prefetch(a+l);__builtin_prefetch(a+r);
 unsigned y=a[l],z=a[r];
 if(x<y||x>z)l=0,r=n-1,y=a[0],z=a[n-1];
 for(;;){
  unsigned m=l+(unsigned)((double)(x-y)*(r-l)/(z-y));
  unsigned w=a[m];
  if(w==x)return m;
  if(w<x){if(m==l)y=a[++l];else l=m,y=w;}
  else {if(m==r)z=a[--r];else r=m,z=w;}
 }
}

__attribute__((noreturn))void __libc_start_main(int(*f)(int,char**,char**),int n,char**a){
 c=n;v=a;f(n,a,(char**)0);
 __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall":::"rax","rdi","rcx","r11","memory");__builtin_unreachable();
}

评测结果