代码

#pragma GCC target("avx2,bmi,bmi2")


































































































































































































































#pragma GCC optimize("O3","unroll-loops","schedule-insns","sched-stalled-insns=2","live-range-shrinkage")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC target("avx2")
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <immintrin.h>














static inline void st256(void *p,__m256i v){   
  asm("vmovdqu %1, %0" : "=m"(*(__m256i*)p) : "x"(v));
}
typedef unsigned u32; typedef unsigned short u16; typedef unsigned char u8;

#define SLK1 4352u
#define DIT  256u
#define NMAX 134217728u
#define CAP1M (NMAX/256u + SLK1)



#define STR1M (((CAP1M + DIT + 64u) + 63u) & ~63u)
#define REC3 3u




#define GUARD8 (64u<<20)
static u8 g_S8[REC3*(256u*STR1M + CAP1M + 8192u) + 64u + GUARD8];




#define BLK 384u
#define BLKREC 128u
#define BLKST 512u   
static u8 g_stg[256u*BLKST] __attribute__((aligned(256)));

#define SLK2 256u
#define RS2MAX ((((CAP1M>>8) + SLK2 + 63u) >> 5) + 2u) * 32u
static u16 g_T[256u*RS2MAX + CAP1M + 8192u];

#define SLK3 18u
#define RS3MAX 32u




alignas(32) static u8 g_U[256u*RS3MAX + RS2MAX + 256u];

static u32 g_off[257];
static inline void sink64(unsigned long long v){ __asm__ volatile("" :: "r"(v) : "memory"); }
int g_noavx_dbg=-1; static int g_noavx=0;

static inline void pretouch_a(unsigned *p,int n){
  if(n<=0) return;
  for(int i=0;i<n;i+=1024)
    __asm__ volatile("orl $0, %0" : "+m"(p[i]) : : "memory");
  __asm__ volatile("orl $0, %0" : "+m"(p[n-1]) : : "memory");
}

static inline __m256i net8_simd(__m256i v){
#define BD(P,IMM) { __m256i t=P; __m256i lo=_mm256_min_epu32(v,t),hi=_mm256_max_epu32(v,t); v=_mm256_blend_epi32(hi,lo,IMM); }
  BD(_mm256_shuffle_epi32(v,_MM_SHUFFLE(2,3,0,1)),0x99)
  BD(_mm256_shuffle_epi32(v,_MM_SHUFFLE(1,0,3,2)),0xC3)
  BD(_mm256_shuffle_epi32(v,_MM_SHUFFLE(2,3,0,1)),0xA5)
  BD(_mm256_permute2x128_si256(v,v,1),0x0F)
  BD(_mm256_shuffle_epi32(v,_MM_SHUFFLE(1,0,3,2)),0x33)
  BD(_mm256_shuffle_epi32(v,_MM_SHUFFLE(2,3,0,1)),0x55)
  return v;
#undef BD
}

static inline __m256i ld8s(const u8 *g,u32 prefix){
  return _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i*)g)),
                         _mm256_set1_epi32((int)prefix));
}
static inline __m256i ld8p(const u8 *g,u32 cc,u32 prefix){
  const __m256i idx=_mm256_setr_epi32(0,1,2,3,4,5,6,7);
  __m256i msk=_mm256_cmpgt_epi32(_mm256_set1_epi32((int)cc),idx);
  __m256i x=_mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i*)g));
  x=_mm256_or_si256(x,_mm256_set1_epi32((int)prefix));
  return _mm256_blendv_epi8(_mm256_set1_epi32(-1),x,msk);
}
static void emit_avx2(const u8 *g,u32 c,u32 prefix,u32 *o){
  if(c<=8){
    st256(o,net8_simd(ld8p(g,c,prefix)));
  } else {
    __m256i A=net8_simd(ld8p(g,8u,prefix));
    __m256i B=net8_simd(ld8p(g+8,c-8u,prefix));
    __m256i BR=_mm256_permutevar8x32_epi32(B,_mm256_setr_epi32(7,6,5,4,3,2,1,0));
    st256(o,net8_simd(_mm256_min_epu32(A,BR)));
    st256(o+8,net8_simd(_mm256_max_epu32(A,BR)));
  }
}
static inline __m256i bmerge8(__m256i v){
#define BS(P,IMM) { __m256i t=P; __m256i lo=_mm256_min_epu32(v,t),hi=_mm256_max_epu32(v,t); v=_mm256_blend_epi32(hi,lo,IMM); }
  BS(_mm256_permute2x128_si256(v,v,1),0x0F)
  BS(_mm256_shuffle_epi32(v,_MM_SHUFFLE(1,0,3,2)),0x33)
  BS(_mm256_shuffle_epi32(v,_MM_SHUFFLE(2,3,0,1)),0x55)
  return v;
#undef BS
}
static inline void emitv(const u8 *g,u32 c,u32 prefix,__m256i *A,__m256i *B){
  if(c<=8){ *A=net8_simd(ld8s(g,prefix)); }
  else {
    const __m256i REV=_mm256_setr_epi32(7,6,5,4,3,2,1,0);
    __m256i X=net8_simd(ld8s(g,prefix));
    __m256i Y=net8_simd(ld8s(g+8,prefix));
    __m256i YR=_mm256_permutevar8x32_epi32(Y,REV);
    __m256i MN=_mm256_min_epu32(X,YR), MX=_mm256_max_epu32(X,YR);
    *A=bmerge8(MN); *B=bmerge8(MX);
  }
}
static void emit_scalar(const u8 *g,u32 c,u32 prefix,u32 *o){
  for(u32 i=0;i<c;i++){
    u32 v=prefix|g[i]; u32 j=i;
    while(j&&o[j-1]>v){ o[j]=o[j-1]; j--; }
    o[j]=v;
  }
}
static inline void emit(const u8 *g,u32 c,u32 prefix,u32 *o){
  if(!g_noavx && c<=16) emit_avx2(g,c,prefix,o);
  else emit_scalar(g,c,prefix,o);
}



static u32 g_pb1[256*8] __attribute__((aligned(32)));   
static void init_pb1(void){
  for(u32 b=0;b<256;b++){ u32 v=b<<8; for(int k=0;k<8;k++) g_pb1[8*b+k]=v; }
}
alignas(32) static u8 g_sh1[32],g_sh2[32],g_sh4[32],g_selb[6][32],g_shrev[32];
static u8 g_mp0[32],g_mp2[32],g_mp2r[32],g_mp0s[32],g_mp2s[32];
static u8 g_k0s2[32],g_k2s4[32];
static void init_bmasks(void){
  for(int g=0;g<4;g++){ u8*p=g_shrev+8*g; int b=(g&1)*8; for(int k=0;k<8;k++) p[k]=b+7-k; }
  static const u8 P1[8]={1,0,3,2,5,4,7,6};
  static const u8 P2[8]={2,3,0,1,6,7,4,5};
  static const u8 P4[8]={4,5,6,7,0,1,2,3};
  for(int g=0;g<4;g++){
    int b=(g&1)*8;   
    u8*p=g_sh1+8*g; u8*q=g_sh2+8*g; u8*r=g_sh4+8*g;
    for(int k=0;k<8;k++){ p[k]=P1[k]+b; q[k]=P2[k]+b; r[k]=P4[k]+b; }
  }
  const u32 S[6]={0x99,0xC3,0xA5,0x0F,0x33,0x55};
  for(int s=0;s<6;s++) for(int g=0;g<4;g++) for(int e=0;e<8;e++)
    g_selb[s][8*g+e]=((S[s]>>e)&1)?0xFF:0x00;

  
  
  
  
  for(int g=0;g<4;g++){
    int gb=g&1, base=8*gb;
    for(int w=0;w<4;w++){
      int i0=base+2*w, i1=base+2*w+1;
      int b0=(0x55u>>(4*gb+w))&1, b2=(0x33u>>(4*gb+w))&1;
      g_mp0[8*g+2*w]=b0?i1:i0; g_mp0[8*g+2*w+1]=b0?i0:i1;
      g_mp2[8*g+2*w]=b2?i1:i0; g_mp2[8*g+2*w+1]=b2?i0:i1;
    }
  }
  for(int i=0;i<32;i++){ int off=(i>=16)?16:0;
    g_mp2r[i]=g_mp2[g_shrev[i]+off];
    g_mp0s[i]=g_mp0[g_sh1[i]+off]; g_mp2s[i]=g_mp2[g_sh1[i]+off];
    g_k0s2[i]=g_mp0[g_sh2[i]+off]; g_k2s4[i]=g_mp2[g_sh4[i]+off]; }
}
#define BM(a) _mm256_load_si256((const __m256i*)(a))






#define BSTW(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,BM(M)); v=_mm256_blend_epi16(_mm256_max_epu8(v,t),_mm256_min_epu8(v,t),IMM); }
#define BSTD(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,BM(M)); v=_mm256_blend_epi32(_mm256_max_epu8(v,t),_mm256_min_epu8(v,t),IMM); }
static inline __m256i bsort8(__m256i v){
#define BST(M,S) { __m256i t=_mm256_shuffle_epi8(v,BM(M)); v=_mm256_blendv_epi8(_mm256_max_epu8(v,t),_mm256_min_epu8(v,t),BM(S)); }
  BST(g_sh1,g_selb[0]) BSTW(g_sh2,0x99) BST(g_sh1,g_selb[2])
  BSTD(g_sh4,0x55)     BSTW(g_sh2,0x55) BST(g_sh1,g_selb[5])
#undef BST
  return v;
}







#define BH_SEL(S) __m256i S
static inline __m256i bsort8h(__m256i v,__m256i S1,__m256i S2,__m256i S4,
                              __m256i K0,__m256i K2,__m256i K5,__m256i K0S2,__m256i K2S4){
#define BSW(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,M); v=_mm256_blend_epi16(_mm256_min_epu8(v,t),_mm256_max_epu8(v,t),IMM); }
#define BSD(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,M); v=_mm256_blend_epi32(_mm256_min_epu8(v,t),_mm256_max_epu8(v,t),IMM); }
  { __m256i t0=_mm256_shuffle_epi8(v,S1); __m256i m0=_mm256_min_epu16(v,t0);
    __m256i t2=_mm256_shuffle_epi8(m0,K0S2); v=_mm256_shuffle_epi8(m0,K0);
    v=_mm256_blend_epi16(_mm256_min_epu8(v,t2),_mm256_max_epu8(v,t2),0x66); }
  { __m256i t3=_mm256_shuffle_epi8(v,S1); __m256i m3=_mm256_min_epu16(v,t3);
    __m256i t4=_mm256_shuffle_epi8(m3,K2S4); v=_mm256_shuffle_epi8(m3,K2);
    v=_mm256_blend_epi32(_mm256_min_epu8(v,t4),_mm256_max_epu8(v,t4),0xAA); }
  BSW(S2,0xAA)
  { __m256i t=_mm256_shuffle_epi8(v,S1); v=_mm256_max_epu16(v,t); }

#undef BSH
#undef BSW
#undef BSD
  return v;
}
static inline __m256i bsort8x3hR(__m256i v,__m256i S1,__m256i S2,__m256i K0,__m256i K5r){
#define BSY(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,M); v=_mm256_blend_epi16(_mm256_min_epu8(v,t),_mm256_max_epu8(v,t),IMM); }
  { __m256i t=_mm256_shuffle_epi8(v,S1); v=_mm256_shuffle_epi8(_mm256_min_epu16(v,t),K0); }
  BSY(S2,0x66)
  { __m256i t=_mm256_shuffle_epi8(v,S1); v=_mm256_shuffle_epi8(_mm256_min_epu16(v,t),K5r); }
#undef BSY
  return v;
}
static inline __m256i bsort8x3h(__m256i v,__m256i S1,__m256i S2,__m256i K0,__m256i K2){
#define BSY(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,M); v=_mm256_blend_epi16(_mm256_min_epu8(v,t),_mm256_max_epu8(v,t),IMM); }
  { __m256i t=_mm256_shuffle_epi8(v,S1); v=_mm256_shuffle_epi8(_mm256_min_epu16(v,t),K0); }
  BSY(S2,0x66)
  { __m256i t=_mm256_shuffle_epi8(v,S1); v=_mm256_shuffle_epi8(_mm256_min_epu16(v,t),K2); }

#undef BSY
#undef BSZ
  return v;
}
static inline __m256i bmerge8bhMX(__m256i v,__m256i S1,__m256i S2,__m256i S4,__m256i K5){
  
#define BMX(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,M); v=_mm256_blend_epi32(_mm256_min_epu8(v,t),_mm256_max_epu8(v,t),IMM); }
#define BMY(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,M); v=_mm256_blend_epi16(_mm256_min_epu8(v,t),_mm256_max_epu8(v,t),IMM); }
  v=_mm256_shuffle_epi8(v,S4);
  BMY(S2,0xAA)
  { __m256i t=_mm256_shuffle_epi8(v,S1); v=_mm256_max_epu16(v,t); }
#undef BMX
#undef BMY
  return v;
}
static inline __m256i bmerge8bh(__m256i v,__m256i S1,__m256i S2,__m256i S4,__m256i K5){
#define BMD(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,M); v=_mm256_blend_epi32(_mm256_min_epu8(v,t),_mm256_max_epu8(v,t),IMM); }
#define BMW(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,M); v=_mm256_blend_epi16(_mm256_min_epu8(v,t),_mm256_max_epu8(v,t),IMM); }
  BMD(S4,0xAA)
  BMW(S2,0xAA)
  { __m256i t=_mm256_shuffle_epi8(v,S1); v=_mm256_max_epu16(v,t); }

#undef BMH
#undef BMD
#undef BMW
  return v;
}





static inline __m256i bsort8x3(__m256i v){
#define BSTY(M,IMM) { __m256i t=_mm256_shuffle_epi8(v,BM(M)); v=_mm256_blend_epi16(_mm256_max_epu8(v,t),_mm256_min_epu8(v,t),IMM); }
#define BSTZ(M,S) { __m256i t=_mm256_shuffle_epi8(v,BM(M)); v=_mm256_blendv_epi8(_mm256_max_epu8(v,t),_mm256_min_epu8(v,t),BM(S)); }
  BSTZ(g_sh1,g_selb[0]) BSTY(g_sh2,0x99) BSTZ(g_sh1,g_selb[2])
#undef BSTY
#undef BSTZ
  return v;
}

static inline void emit4b(const u8*g0,const u8*g1,const u8*g2,const u8*g3,__m256i O[4]){
  __m128i a=_mm_loadl_epi64((const __m128i*)g0);
  __m128i b=_mm_loadl_epi64((const __m128i*)g1);
  __m128i c=_mm_loadl_epi64((const __m128i*)g2);
  __m128i d=_mm_loadl_epi64((const __m128i*)g3);
  __m256i v=_mm256_set_m128i(_mm_unpacklo_epi64(c,d),_mm_unpacklo_epi64(a,b));
  v=bsort8(v);
  __m128i lo=_mm256_castsi256_si128(v), hi=_mm256_extracti128_si256(v,1);
  O[0]=_mm256_cvtepu8_epi32(lo);
  O[1]=_mm256_cvtepu8_epi32(_mm_srli_si128(lo,8));
  O[2]=_mm256_cvtepu8_epi32(hi);
  O[3]=_mm256_cvtepu8_epi32(_mm_srli_si128(hi,8));
}


static inline __m256i bmerge8b(__m256i v){
#define BMG(M,S) { __m256i t=_mm256_shuffle_epi8(v,BM(M)); v=_mm256_blendv_epi8(_mm256_max_epu8(v,t),_mm256_min_epu8(v,t),BM(S)); }
  BSTD(g_sh4,0x55) BSTW(g_sh2,0x55) BMG(g_sh1,g_selb[5])
#undef BMG
  return v;
}

static inline void emit4b2(const u8*g0,const u8*g1,const u8*g2,const u8*g3,__m256i*A,__m256i*B,__m256i O[4]){
  __m128i x0=_mm_loadu_si128((const __m128i*)g0);
  __m128i x1=_mm_loadu_si128((const __m128i*)g1);
  __m128i x2=_mm_loadu_si128((const __m128i*)g2);
  __m128i x3=_mm_loadu_si128((const __m128i*)g3);
  __m256i a=_mm256_set_m128i(_mm_unpacklo_epi64(x2,x3),_mm_unpacklo_epi64(x0,x1));
  *B=_mm256_set_m128i(_mm_unpackhi_epi64(x2,x3),_mm_unpackhi_epi64(x0,x1));
  a=bsort8(a); *A=a;
  __m128i lo=_mm256_castsi256_si128(a), hi=_mm256_extracti128_si256(a,1);
  O[0]=_mm256_cvtepu8_epi32(lo);
  O[1]=_mm256_cvtepu8_epi32(_mm_srli_si128(lo,8));
  O[2]=_mm256_cvtepu8_epi32(hi);
  O[3]=_mm256_cvtepu8_epi32(_mm_srli_si128(hi,8));
}

static __attribute__((noinline)) u32 *emit_b1range(u32 b1,const u16 *p,const u32 *cnt3,u32 hi24,u32 *o){
  for(u32 b=b1;b<b1+4;b++){ u32 c=cnt3[b]; if(!c) continue;
    emit(g_U+(b*RS3MAX),c,hi24|(b<<8),o); o+=c; }
  return o;
}


static void sort_region(const u8 *src,u32 m,u32 *out,u32 d3){
  if(m<=64){
    const u32 hi=(u32)d3<<24;
    for(u32 i=0;i<m;i++){
      u32 v=hi|((*(const u32*)(src+REC3*i))&0xFFFFFFu); u32 j=i;
      while(j&&out[j-1]>v){ out[j]=out[j-1]; j--; }
      out[j]=v;
    }
    return;
  }
  u32 RS2=(m>>8)+SLK2;
  { u32 k=(RS2+31u)>>5; if(!(k&1u)) k++; RS2=k<<5; }   
  u16 * __restrict T=g_T;
  u32 st2[256];
  for(u32 b=0;b<256;b++) st2[b]=b*RS2;
  {
    const u8 * __restrict sp=src;
#pragma GCC unroll 8
    for(u32 i=0;i<m;i++){
      __builtin_prefetch(sp+768,0,0);
      u32 lo=*(const u16*)sp; u32 b2=sp[2]; sp+=REC3;
      T[st2[b2]++]=lo;
    }
  }
  for(u32 b=0;b<256;b++) if(st2[b]-b*RS2>RS2){ const u32 hi=(u32)d3<<24;
    for(u32 i=0;i<m;i++) out[i]=hi|((*(const u32*)(src+REC3*i))&0xFFFFFFu); std::sort(out,out+m); return; }
  u32 pos=0;
  alignas(32) u32 st3[256];
  { for(u32 b=0;b<256;b++) st3[b]=b<<5; }
  for(u32 b2=0;b2<256;b2++){
    u32 m2=st2[b2]-b2*RS2;
    if(!m2) continue;
    const u16 *p=T+b2*RS2;
    u32 hi24=(b2<<16)|(d3<<24);
    if(m2<=8){
      u32 buf[8];
      for(u32 i=0;i<m2;i++){ u32 v=(u32)p[i]|hi24; u32 j=i;
        while(j&&buf[j-1]>v){ buf[j]=buf[j-1]; j--; } buf[j]=v; }
      for(u32 i=0;i<m2;i++) out[pos+i]=buf[i];
      pos+=m2; continue;
    }
    
    const u32 RS3=RS3MAX;
    const u32 RSH=5u;          
    u8 * __restrict U=g_U;
    { __m256i mx=_mm256_set1_epi8(-1);
      for(u32 bb=0;bb<256u;bb++) _mm_store_si128((__m128i*)(U+(bb<<RSH)),_mm256_castsi256_si128(mx)); }
#pragma GCC unroll 8
    for(u32 i=0;i<m2;i++){ u32 r=p[i]; u32 b1=r>>8; U[st3[b1]++]=(u8)r; }
    alignas(32) u32 cnt3[256];
    u32 bad=0;
    { __m256i r=_mm256_setr_epi32(0,1,2,3,4,5,6,7),stp=_mm256_set1_epi32(8),sh=_mm256_set1_epi32((int)RSH);
      __m256i mx=_mm256_setzero_si256();
      for(u32 b=0;b<256;b+=8){ __m256i bv=_mm256_sllv_epi32(r,sh); __m256i v=_mm256_load_si256((const __m256i*)(st3+b));
        v=_mm256_sub_epi32(v,bv);
        _mm256_store_si256((__m256i*)(cnt3+b),v);
        _mm256_store_si256((__m256i*)(st3+b),bv);   
        mx=_mm256_max_epu32(mx,v); r=_mm256_add_epi32(r,stp); }
      __m256i mr=_mm256_max_epu32(_mm256_permute2x128_si256(mx,mx,1),mx);
      mr=_mm256_max_epu32(_mm256_shuffle_epi32(mr,_MM_SHUFFLE(1,0,3,2)),mr);
      mr=_mm256_max_epu32(_mm256_shuffle_epi32(mr,_MM_SHUFFLE(2,3,0,1)),mr);
      if((u32)_mm256_extract_epi32(mr,0)>RS3) bad=1; }
    if(bad){
      u32 *o=out+pos;
      for(u32 i=0;i<m2;i++){ u32 v=((u32)p[i])|hi24; u32 j=i;
        while(j&&o[j-1]>v){ o[j]=o[j-1]; j--; } o[j]=v; }
      pos+=m2; continue;
    }
    if(d3!=255u){
      u32 *o=out+pos;
      const __m256i HIV=_mm256_set1_epi32((int)hi24);
      
      
      
      
      
      
      const __m256i SH1=BM(g_sh1),SH2=BM(g_sh2),SH4=BM(g_sh4);
      const __m256i K0S2=BM(g_k0s2),K2S4=BM(g_k2s4);
      const __m256i K0=BM(g_mp0),K2=BM(g_mp2),K5=BM(g_mp2r);
      __m256i Pn=_mm256_set_m128i(_mm_loadu_si128((const __m128i*)(U+(2*RS3))),_mm_loadu_si128((const __m128i*)(U)));
      __m256i Qn=_mm256_set_m128i(_mm_loadu_si128((const __m128i*)(U+(3*RS3))),_mm_loadu_si128((const __m128i*)(U+RS3)));
      for(u32 b1=0;b1<256;b1+=4){
        u32 c0=cnt3[b1],c1=cnt3[b1+1],c2=cnt3[b1+2],c3=cnt3[b1+3];
        u32 mx=c0; if(c1>mx)mx=c1; if(c2>mx)mx=c2; if(c3>mx)mx=c3;
        
        
        
        
        
        
        
        
        __m256i P=Pn,Q=Qn;
        { const u8 *nb=U+((b1+4)*RS3);
          Pn=_mm256_set_m128i(_mm_loadu_si128((const __m128i*)(nb+(2*RS3))),_mm_loadu_si128((const __m128i*)(nb)));
          Qn=_mm256_set_m128i(_mm_loadu_si128((const __m128i*)(nb+(3*RS3))),_mm_loadu_si128((const __m128i*)(nb+RS3))); }
        __m256i AP=_mm256_unpacklo_epi64(P,Q);
        __m256i A=bsort8h(AP,SH1,SH2,SH4,K0,K2,K5,K0S2,K2S4);
        if(__builtin_expect(mx<=8u,1)){
          __m128i lo=_mm256_castsi256_si128(A), hi=_mm256_extracti128_si256(A,1);
          __m256i O0=_mm256_cvtepu8_epi32(lo),        O1=_mm256_cvtepu8_epi32(_mm_srli_si128(lo,8));
          __m256i O2=_mm256_cvtepu8_epi32(hi),        O3=_mm256_cvtepu8_epi32(_mm_srli_si128(hi,8));
          st256(o,_mm256_or_si256(_mm256_or_si256(O0,BM(g_pb1+8*b1)),       HIV)); o+=c0;
          st256(o,_mm256_or_si256(_mm256_or_si256(O1,BM(g_pb1+8*(b1+1))),   HIV)); o+=c1;
          st256(o,_mm256_or_si256(_mm256_or_si256(O2,BM(g_pb1+8*(b1+2))),   HIV)); o+=c2;
          st256(o,_mm256_or_si256(_mm256_or_si256(O3,BM(g_pb1+8*(b1+3))),   HIV)); o+=c3;
          continue;
        }
        
        
        
        
        
        
        
        
        
        
        if(__builtin_expect(mx>16u,0)){
          o=emit_b1range(b1,p,cnt3,hi24,o);
          continue;
        }
        __m256i B=_mm256_unpackhi_epi64(P,Q);
        
        
        
        
        
        
        __m256i MN,MX;
        if(__builtin_expect(mx<=12u,1)){
          __m256i BR=bsort8x3hR(B,SH1,SH2,K0,K5);
          MN=bmerge8bh(_mm256_min_epu8(A,BR),SH1,SH2,SH4,K5);
          MX=bmerge8bhMX(_mm256_max_epu8(A,BR),SH1,SH2,SH4,K5);
        } else {
          __m256i BR=_mm256_shuffle_epi8(bsort8h(B,SH1,SH2,SH4,K0,K2,K5,K0S2,K2S4),BM(g_shrev));
          MN=bmerge8bh(_mm256_min_epu8(A,BR),SH1,SH2,SH4,K5);
          MX=bmerge8bh(_mm256_max_epu8(A,BR),SH1,SH2,SH4,K5);
        }
        __m128i lo,hi;
        lo=_mm256_castsi256_si128(MN); hi=_mm256_extracti128_si256(MN,1);
        __m256i M0=_mm256_cvtepu8_epi32(lo), M1=_mm256_cvtepu8_epi32(_mm_srli_si128(lo,8));
        __m256i M2=_mm256_cvtepu8_epi32(hi), M3=_mm256_cvtepu8_epi32(_mm_srli_si128(hi,8));
        lo=_mm256_castsi256_si128(MX); hi=_mm256_extracti128_si256(MX,1);
        __m256i X0=_mm256_cvtepu8_epi32(lo), X1=_mm256_cvtepu8_epi32(_mm_srli_si128(lo,8));
        __m256i X2=_mm256_cvtepu8_epi32(hi), X3=_mm256_cvtepu8_epi32(_mm_srli_si128(hi,8));
        u32 *p=o;











#define STK(CC,MV,XV,OO,PB) { __m256i PV=_mm256_or_si256(BM(PB),HIV); \
                              st256(p,_mm256_or_si256(MV,PV)); \
                              st256(p+8,_mm256_or_si256(XV,PV)); p+=CC; }
        STK(c0,M0,X0,O[0],g_pb1+8*b1)
        STK(c1,M1,X1,O[1],g_pb1+8*(b1+1))
        STK(c2,M2,X2,O[2],g_pb1+8*(b1+2))
        STK(c3,M3,X3,O[3],g_pb1+8*(b1+3))
#undef STK
        o=p;
      }
      pos=(u32)(o-out);
    } else {
      for(u32 b1=0;b1<256;b1++){
        u32 c=cnt3[b1];
        if(!c) continue;
        const u8 *g=U+(b1*RS3);
        u32 prefix=hi24|(b1<<8);
        u32 *o=out+pos;
        u32 w=(c<=8)?8u:16u;
        if(pos+w<=m) emit(g,c,prefix,o);
        else emit_scalar(g,c,prefix,o);
        pos+=c;
      }
    }
  }
}


__attribute__((noinline)) void pospad(void) {
  __asm__ __volatile__(".fill 139,1,0x90 ; ret");
}


__attribute__((noinline)) void pospadB(void) {
  __asm__ __volatile__(".fill 75,1,0x90 ; ret");
}

void sort(unsigned *a,int n){
  static int initt=0;
  if(!initt){ initt=1; init_pb1(); init_bmasks(); }
  static int init=0;
  if(g_noavx_dbg>=0) g_noavx=g_noavx_dbg; else if(!init){ init=1; g_noavx = __builtin_cpu_supports("avx2")?0:1; }
  {
    
    
    
    
    
    
    
    
    
    u32 off[256]; u32 base[256], ob[256];
    for(u32 b=0;b<256;b++){ u32 bs=REC3*(b*STR1M+64u*((b*1237u)&7u)); base[b]=bs; ob[b]=bs; off[b]=b*BLKST; }
    const u32 * __restrict aa=a; u8 * __restrict S=g_S8; u8 * __restrict SG=g_stg;









#define L2BODY(K) { \
      u32 v=aa[i+(K)], d=((const u8*)aa)[4*(i+(K))+3]; \
      u32 o=off[d]; \
      off[d]=o+REC3; \
      *(u32*)(SG+o)=v; \
      if(__builtin_expect(((o+REC3)&127u)==0u,0)){ \
        u32 f=ob[d]; ob[d]=f+BLK; \
        u8*_fq=SG+(o+REC3-BLK); u8*_fr=S+f; \
        for(u32 _fk=0;_fk<BLK;_fk+=32) \
          _mm256_stream_si256((__m256i*)(_fr+_fk),_mm256_load_si256((const __m256i*)(_fq+_fk))); \
        off[d]=o+REC3-BLK; \
      } }
    { int i=0;
      for(;i+16<=n;i+=16){
                         if(__builtin_expect((i&1023u)==0u && i+8192<(int)n,0))
                           __asm__ volatile("orl $0, %0" : "+m"(((u32*)aa)[i+8192]));
                         L2BODY(0)                          L2BODY(1)                          L2BODY(2)                          L2BODY(3)
                         L2BODY(4)                          L2BODY(5)                          L2BODY(6)                          L2BODY(7)
                         L2BODY(8)                          L2BODY(9)                          L2BODY(10)                          L2BODY(11)
                         L2BODY(12)                          L2BODY(13)                          L2BODY(14)                          L2BODY(15)
 }
      for(;i+8<=n;i+=8){
                         if(__builtin_expect((i&1023u)==0u && i+8192<(int)n,0))
                           __asm__ volatile("orl $0, %0" : "+m"(((u32*)aa)[i+8192]));
                         L2BODY(0)                          L2BODY(1)                          L2BODY(2)                          L2BODY(3)
                         L2BODY(4)                          L2BODY(5)                          L2BODY(6)                          L2BODY(7)
 }
      for(;i<n;i++){ L2BODY(0) }    }
#undef L2BODY
    _mm_sfence();
    int bad=0; u32 tot=0;
    for(u32 b=0;b<256;b++){
      u32 rem=off[b]%BLKST;            
      u32 cnt=(ob[b]-base[b])/BLK*BLKREC+rem/REC3;
      if(cnt>CAP1M) bad=1;
      g_off[b]=tot; tot+=cnt;
    }
    g_off[256]=tot;
    if(bad || tot!=(u32)n){ std::sort(a,a+n); return; }
    for(u32 b=0;b<256;b++){
      u32 m=g_off[b+1]-g_off[b];
      if(!m) continue;
      u32 rem=off[b]%BLKST;
      if(rem){                       
        u8*q=SG+(off[b]-rem); u8*r=g_S8+ob[b];
        for(u32 k=0;k<rem;k++) r[k]=q[k];
      }
      
      
      
      sort_region(g_S8+base[b], m, a+g_off[b], b);
    }
    volatile u8 l_pad[1920u]; l_pad[0]=1;
    sink64(l_pad[0]);
  }
}

评测结果