代码

// Preserves the v10 packed24 top partition and its exact fallback paths.
// Local measurements only; this candidate has not been submitted to Duck.ac.
// Duck.ac 1001 v10: v8 with independent byte-key / word-payload loads.
// Middle-load idea: https://duck.ac/submission/48085
// Network: https://bertdobbelaere.github.io/sorting_networks.html#N12L39D9
#include <algorithm>
#include <cstdint>
#include <cstring>
#include <immintrin.h>
#include <utility>
#pragma GCC optimize("O3,unroll-loops,no-strict-aliasing")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <cstdlib>
namespace fastsort {
template<class F,size_t... I>
[[gnu::always_inline]] inline void each(F&& f,std::index_sequence<I...>){
  (f(std::integral_constant<size_t,I>{}),...);
}
template<size_t N,class F> [[gnu::always_inline]] inline void repeat(F&&f){
  each(std::forward<F>(f),std::make_index_sequence<N>{});
}
}
namespace v2_tail {
using U=unsigned;using B=uint8_t;using H=uint16_t;using V=__m256i;using W=__m128i;
alignas(64) static B columns[256*8192];
inline U load16(const H* p){
  H v;std::memcpy(&v,p,2);return v;
}
[[gnu::noinline]] inline void dense(const H* src,U n,U* dst,U base){
  alignas(64) U counts[65536]={};
  for(U i=0;i<n;++i)++counts[load16(src+i)];
  for(U v=0;v<65536;++v)
    for(U c=counts[v];c;--c)*dst++=base|v;
}
inline void write8(W x,U* dst,U base){
  V y=_mm256_or_si256(_mm256_cvtepu8_epi32(x),_mm256_set1_epi32(base));
  __asm__ volatile("vmovdqu {%1, %0|%0, %1}" : "=m"(*reinterpret_cast<__m256i_u*>(dst)) : "x"(y));
}
[[gnu::always_inline]] inline void batch_sort(const B* src,B* out,B* tail){
V x[12],a[8],b[8];
fastsort::repeat<12>([&](auto j) __attribute__((always_inline)){
    x[j]=_mm256_load_si256((const V*)(src+256*j));
});
#define CMP(A,B) do {V lo=_mm256_min_epu8(x[A],x[B]);x[B]=_mm256_max_epu8(x[A],x[B]);x[A]=lo;} while(0)
CMP(0,8);CMP(1,7);CMP(2,6);CMP(3,11);CMP(4,10);CMP(5,9);CMP(0,1);CMP(2,5);CMP(3,4);CMP(6,9);CMP(7,8);CMP(10,11);CMP(0,2);CMP(1,6);CMP(5,10);CMP(9,11);CMP(0,3);CMP(1,2);CMP(4,6);CMP(5,7);CMP(8,11);CMP(9,10);CMP(1,4);CMP(3,5);CMP(6,8);CMP(7,10);CMP(1,3);CMP(2,5);CMP(6,9);CMP(8,10);CMP(2,3);CMP(4,5);CMP(6,7);CMP(8,9);CMP(4,6);CMP(5,7);CMP(3,4);CMP(5,6);CMP(7,8);
#undef CMP
  #pragma GCC unroll 4
  for(U i=0;i<4;++i){
    a[2*i]=_mm256_unpacklo_epi8(x[2*i],x[2*i+1]);
    a[2*i+1]=_mm256_unpackhi_epi8(x[2*i],x[2*i+1]);
  }
  #pragma GCC unroll 2
  for(U i=0;i<2;++i){
    #pragma GCC unroll 2
    for(U j=0;j<2;++j){
      b[4*i+2*j]=_mm256_unpacklo_epi16(a[4*i+j],a[4*i+j+2]);
      b[4*i+2*j+1]=_mm256_unpackhi_epi16(a[4*i+j],a[4*i+j+2]);
    }
  }
  #pragma GCC unroll 4
  for(U i=0;i<4;++i){
    V lo=_mm256_unpacklo_epi32(b[i],b[i+4]);
    V hi=_mm256_unpackhi_epi32(b[i],b[i+4]);
    _mm256_store_si256((V*)(out+64*i),lo);
    _mm256_store_si256((V*)(out+64*i+32),hi);
  }
    a[0]=_mm256_unpacklo_epi8(x[8],x[9]);a[1]=_mm256_unpackhi_epi8(x[8],x[9]);
    a[2]=_mm256_unpacklo_epi8(x[10],x[11]);a[3]=_mm256_unpackhi_epi8(x[10],x[11]);
    b[0]=_mm256_unpacklo_epi16(a[0],a[2]);b[1]=_mm256_unpackhi_epi16(a[0],a[2]);
    b[2]=_mm256_unpacklo_epi16(a[1],a[3]);b[3]=_mm256_unpackhi_epi16(a[1],a[3]);
    #pragma GCC unroll 2
    for(U i=0;i<2;++i){
      _mm256_store_si256((V*)(tail+64*i),b[2*i]);
      _mm256_store_si256((V*)(tail+64*i+32),b[2*i+1]);
    }
    }
// x is sorted and has at least one trailing 255 sentinel.
inline W insert_byte(W x,U byte){
  return _mm_min_epu8(x,_mm_max_epu8(_mm_slli_si128(x,1),_mm_set1_epi8(char(byte))));
}
[[gnu::noinline]] inline void slow_output(const B* first8,const B* last4,U h,U c,U* dst,U p){
  if(c<=16){
      W x=_mm_loadl_epi64((const W*)(first8));
      uint32_t four;std::memcpy(&four,last4,4);
        x=_mm_unpacklo_epi64(x,_mm_cvtsi64_si128(uint64_t(four)|0xffffffff00000000ull));
        U j=12;do{x=insert_byte(x,columns[256*j+h]);}while(++j<c);
        write8(x,dst,p);write8(_mm_srli_si128(x,8),dst+8,p);
      }else {
        B copy[32];for(U j=0;j<c;++j)copy[j]=columns[256*j+h];
        std::sort(copy,copy+c);for(U j=0;j<c;++j)dst[j]=p|copy[j];
      }
}
template<bool AllSmall>
[[gnu::always_inline]] inline U* emit_block(const B* first,const B* second,
    const U* count,U block,U* dst,U base){
  V prefix=_mm256_set1_epi32(base|(block<<8));
  auto emit=[&](U i,const B* first8,const B* last4) __attribute__((always_inline)){
    U h=block+i,c=count[h];
    if(AllSmall || __builtin_expect(c<=12,1)){
      V wide=_mm256_or_si256(_mm256_cvtepu8_epi32(_mm_loadl_epi64((const W*)first8)),prefix);
      __asm__ volatile("vmovdqu {%1, %0|%0, %1}" : "=m"(*reinterpret_cast<__m256i_u*>(dst)) : "x"(wide));
      U four;std::memcpy(&four,last4,4);
      W y=_mm_or_si128(_mm_cvtepu8_epi32(_mm_cvtsi32_si128(four)),_mm256_castsi256_si128(prefix));
      _mm_storeu_si128((W*)(dst+8),y);
    }else slow_output(first8,last4,h,c,dst,base|(h<<8));
    dst+=c;prefix=_mm256_add_epi32(prefix,_mm256_set1_epi32(256));
    __asm__("" : "+x"(prefix));
  };
  #pragma GCC unroll 1
  for(U half=0;half<2;++half){
    #pragma GCC unroll 1
    for(U group=0;group<4;++group){
      fastsort::repeat<4>([&](auto r) __attribute__((always_inline)){
        emit(16*half+4*group+r,
             first+16*half+64*group+8*r+16*(r/2),
             second+16*half+32*group+4*r);
      });
    }
  }
  return dst;
}
// Needs sixteen writable padding elements unless a precise fallback is taken.
[[gnu::noinline]] inline void columns_fast(const H* src,U n,U* dst,U base){
  if(n<64){
    U copy[64];for(U i=0;i<n;++i)copy[i]=base|load16(src+i);
    std::sort(copy,copy+n);std::memcpy(dst,copy,n*4);return;
  }
  if(n>8192){dense(src,n,dst,base);return;}
  alignas(64) U count[256];
  std::memset(columns,255,3072);
  for(U i=0;i<256;++i)count[i]=i;
  for(U i=0;i<n;++i){
    U v=load16(src+i),h=v>>8,at=count[h];
    count[h]=at+256;columns[at]=B(v);
  }
  U small[8];
  V over=_mm256_setzero_si256();
  #pragma GCC unroll 1
  for(U i=0;i<256;i+=32){
    V a=_mm256_srli_epi32(_mm256_load_si256((const V*)(count+i)),8);
    V b=_mm256_srli_epi32(_mm256_load_si256((const V*)(count+i+8)),8);
    V c=_mm256_srli_epi32(_mm256_load_si256((const V*)(count+i+16)),8);
    V d=_mm256_srli_epi32(_mm256_load_si256((const V*)(count+i+24)),8);
    _mm256_store_si256((V*)(count+i),a);_mm256_store_si256((V*)(count+i+8),b);
    _mm256_store_si256((V*)(count+i+16),c);_mm256_store_si256((V*)(count+i+24),d);
    V maximum=_mm256_max_epu32(_mm256_max_epu32(a,b),_mm256_max_epu32(c,d));
    over=_mm256_or_si256(over,_mm256_cmpgt_epi32(maximum,_mm256_set1_epi32(32)));
    V exceptional=_mm256_cmpgt_epi32(maximum,_mm256_set1_epi32(12));
    small[i>>5]=_mm256_testz_si256(exceptional,exceptional);
  }
  if(!_mm256_testz_si256(over,over)){dense(src,n,dst,base);return;}
  for(U block=0;block<256;block+=32){
    alignas(32) B first[256],second[128];
    batch_sort(columns+block,first,second);
    if(__builtin_expect(small[block>>5],1))dst=emit_block<true>(first,second,count,block,dst,base);
    else dst=emit_block<false>(first,second,count,block,dst,base);
  }
}
[[gnu::noinline]] inline void last_leaf(const H* src,U n,U* dst,U base){
  alignas(32) U copy[8192+16];
  columns_fast(src,n,copy,base);std::memcpy(dst,copy,n*4);
}
template<bool Full=false> inline void columns_merge(const H* src,U n,U* dst,U base,U* end){
  if(!Full && n>=64 && n<=8192 && end-dst<n+16)last_leaf(src,n,dst,base);
  else columns_fast(src,n,dst,base);
}
}
namespace fastsort {
using U=unsigned;using B=unsigned char;using H=uint16_t;using Z=uint64_t;
// Retained for the process lifetime and reused on subsequent calls.
static B* mem;
inline U get(const B* p){U x;std::memcpy(&x,p,4);return x&0xffffff;}
inline U at(const B* p,U i){return get(p+size_t(i/84)*256+i%84*3);}
inline bool fits(B**p,B**e){
  __m256i bad=_mm256_setzero_si256();
  for(U k=0;k<256;k+=4)bad=_mm256_or_si256(bad,_mm256_cmpgt_epi64(
    _mm256_load_si256((__m256i*)(p+k)),_mm256_load_si256((__m256i*)(e+k))));
  return _mm256_testz_si256(bad,bad);
}
bool split(U*a,U n,U*cap,B**start,U*cnt){
  constexpr U guard=25344;
  alignas(64) B cache[65536]={};alignas(64) B*p[256],*e[256];
  U pos[256];size_t off=0;
  for(U k=0;k<256;++k){
    start[k]=p[k]=mem+off;e[k]=p[k]+((size_t(cap[k])+83)/84)*256;
    off=size_t(e[k]-mem)+guard;pos[k]=k*256;
  }
  auto push=[&](U x) __attribute__((always_inline)){
    U k=x>>24,t=pos[k];std::memcpy(cache+t,&x,4);t+=3;
    if(__builtin_expect((t&255)==252,0)){
      t-=252;
      repeat<8>([&](auto j) __attribute__((always_inline)){
        _mm256_stream_si256((__m256i*)(p[k]+32*j),_mm256_load_si256((const __m256i*)(cache+t+32*j)));
      });
      p[k]+=256;
    }
    pos[k]=t;
  };
  for(U i=0;i<n;){
    U stop=std::min(n,i+8192);
    for(;i+8<=stop;i+=8)repeat<8>([&](auto j) __attribute__((always_inline)){push(a[i+j]);});
    for(;i<stop;++i)push(a[i]);
    if(!fits(p,e)){_mm_sfence();return false;}
  }
  for(U k=0;k<256;++k){
    U r=pos[k]&255;cnt[k]=U((p[k]-start[k])/256)*84+r/3;
    if(r){std::memcpy(p[k],cache+k*256,256);p[k]+=256;}
  }
  _mm_sfence();return fits(p,e);
}
void leaf(const B*s,U n,U base,U*d,U*end=nullptr){v2_tail::columns_merge((const H*)s,n,d,base,end?end:d+n);}
void middle(const B*s,U n,U base,U*d){
  if(n<4096){for(U i=0;i<n;++i)d[i]=base|at(s,i);std::sort(d,d+n);return;}
  U cnt[256]={},begin[257],pos[256];
  if(n>600000||n<16384){
    for(U i=0;i<n;++i)++cnt[at(s,i)>>16];
    begin[0]=0;
    for(U k=0;k<256;++k){pos[k]=begin[k];begin[k+1]=begin[k]+cnt[k];}
    for(U i=0;i<n;++i){U x=at(s,i);H lo=x;std::memcpy((B*)d+2*pos[x>>16]++,&lo,2);}
    for(int k=255;k>=0;--k)if(cnt[k])leaf((B*)d+2*begin[k],cnt[k],base|(U(k)<<16),d+begin[k]);
    return;
  }
  B*tmp=mem+380000000;B*p[256];
  U bytes=0;
  for(U k=0;k<256;++k){begin[k]=bytes;p[k]=tmp+bytes;bytes+=64*((((n+255)/256*5/4+32)*2+63)/64|1);}
  begin[256]=bytes;
  for(;;){
    U i=0;const B*b=s;
    for(;i+84<=n;i+=84,b+=256){
      _mm_prefetch((const char*)((uintptr_t)b+256),_MM_HINT_T0);
      #pragma GCC unroll 1
      for(U j=0;j<84;j+=12)repeat<12>([&](auto q) __attribute__((always_inline)){
        const B*r=b+3*(j+q);U k=r[2];H lo;std::memcpy(&lo,r,2);std::memcpy(p[k],&lo,2);p[k]+=2;
      });
    }
    for(;i<n;++i){U x=at(s,i);H lo=x;std::memcpy(p[x>>16],&lo,2);p[x>>16]+=2;}
    bool bad=false;
    for(U k=0;k<256;++k){cnt[k]=U(p[k]-(tmp+begin[k]))/2;bad|=p[k]>tmp+begin[k+1];}
    if(!bad)break;
    bytes=0;
    for(U k=0;k<256;++k){begin[k]=bytes;p[k]=tmp+bytes;bytes+=2*cnt[k];}
    begin[256]=bytes;
  }
  U*end=d+n;
  for(U k=0;k<256;++k){if(cnt[k])leaf(tmp+begin[k],cnt[k],base|(k<<16),d,end);d+=cnt[k];}
}
}
#define FUSED_BITS 8
#define FUSED_BLOCK 256
#define FUSED_RECORDS 84
// Experimental fused middle/tail stage. Requires the supplied v10 helpers.
namespace fused_cells {
using namespace v2_tail;
constexpr U C=1u<<(24-FUSED_BITS), R=FUSED_RECORDS;
static_assert(R*3+1<=FUSED_BLOCK,"packed record guard");
[[gnu::always_inline]] inline void transpose(const B* cells,V* row){
 V a[16],b[16];
 fastsort::repeat<16>([&](auto i) __attribute__((always_inline)){
   a[i]=_mm256_inserti128_si256(_mm256_castsi128_si256(_mm_load_si128((const W*)(cells+16*i))),_mm_load_si128((const W*)(cells+16*(i+16))),1);
 });
 fastsort::repeat<8>([&](auto i) __attribute__((always_inline)){
   b[2*i]=_mm256_unpacklo_epi8(a[2*i],a[2*i+1]);b[2*i+1]=_mm256_unpackhi_epi8(a[2*i],a[2*i+1]);
 });
 fastsort::repeat<4>([&](auto k) __attribute__((always_inline)){
   fastsort::repeat<2>([&](auto j) __attribute__((always_inline)){
     a[4*k+2*j]=_mm256_unpacklo_epi16(b[4*k+j],b[4*k+j+2]);a[4*k+2*j+1]=_mm256_unpackhi_epi16(b[4*k+j],b[4*k+j+2]);
   });
 });
 fastsort::repeat<2>([&](auto k) __attribute__((always_inline)){
   fastsort::repeat<4>([&](auto j) __attribute__((always_inline)){
     b[8*k+2*j]=_mm256_unpacklo_epi32(a[8*k+j],a[8*k+j+4]);b[8*k+2*j+1]=_mm256_unpackhi_epi32(a[8*k+j],a[8*k+j+4]);
   });
 });
 fastsort::repeat<8>([&](auto j) __attribute__((always_inline)){
   row[2*j]=_mm256_unpacklo_epi64(b[j],b[j+8]);row[2*j+1]=_mm256_unpackhi_epi64(b[j],b[j+8]);
 });
}
[[gnu::noinline]] inline void slow(const B* first,const B* last,const B* cell,const B* extra,U c,U* d,U p){
 if(c<=16){
   U four;std::memcpy(&four,last,4);
   W x=_mm_unpacklo_epi64(_mm_loadl_epi64((const W*)first),_mm_cvtsi64_si128(uint64_t(four)|0xffffffff00000000ull));
   for(U j=12;j<c;++j)x=insert_byte(x,j<15?cell[j+1]:extra[j-15]);
   write8(x,d,p);write8(_mm_srli_si128(x,8),d+8,p);
 }else{
   B copy[32];std::memcpy(copy,cell+1,15);std::memcpy(copy+15,extra,c-15);
   std::sort(copy,copy+c);for(U j=0;j<c;++j)d[j]=p|copy[j];
 }
}
template<bool Small>
[[gnu::always_inline]] inline U* emit(const B* first,const B* second,const B* cnt,const B* cells,const B* extra,U block,U* dst,U base){
 V prefix=_mm256_set1_epi32(base|(block<<8));
 auto one=[&](U i,const B* f,const B* s) __attribute__((always_inline)){
   U c=cnt[i];
   if(Small || __builtin_expect(c<=12,1)){
     V wide=_mm256_or_si256(_mm256_cvtepu8_epi32(_mm_loadl_epi64((const W*)f)),prefix);
     __asm__ volatile("vmovdqu {%1, %0|%0, %1}" : "=m"(*reinterpret_cast<__m256i_u*>(dst)) : "x"(wide));
     U four;std::memcpy(&four,s,4);W y=_mm_or_si128(_mm_cvtepu8_epi32(_mm_cvtsi32_si128(four)),_mm256_castsi256_si128(prefix));
     _mm_storeu_si128((W*)(dst+8),y);
   }else slow(f,s,cells+16*i,extra+17*i,c,dst,base|((block+i)<<8));
   dst+=c;prefix=_mm256_add_epi32(prefix,_mm256_set1_epi32(256));__asm__("" : "+x"(prefix));
 };
 #pragma GCC unroll 1
 for(U half=0;half<2;++half){
   #pragma GCC unroll 1
   for(U group=0;group<4;++group){
     fastsort::repeat<4>([&](auto r) __attribute__((always_inline)){
       one(16*half+4*group+r,first+16*half+64*group+8*r+16*(r/2),second+16*half+32*group+4*r);
     });
   }
 }
 return dst;
}
[[gnu::always_inline]] inline void loaded_sort(V* x,B* out,B* tail){
V a[8],b[8];
#define CMP(A,B) do {V lo=_mm256_min_epu8(x[A],x[B]);x[B]=_mm256_max_epu8(x[A],x[B]);x[A]=lo;} while(0)
CMP(0,8);CMP(1,7);CMP(2,6);CMP(3,11);CMP(4,10);CMP(5,9);CMP(0,1);CMP(2,5);CMP(3,4);CMP(6,9);CMP(7,8);CMP(10,11);CMP(0,2);CMP(1,6);CMP(5,10);CMP(9,11);CMP(0,3);CMP(1,2);CMP(4,6);CMP(5,7);CMP(8,11);CMP(9,10);CMP(1,4);CMP(3,5);CMP(6,8);CMP(7,10);CMP(1,3);CMP(2,5);CMP(6,9);CMP(8,10);CMP(2,3);CMP(4,5);CMP(6,7);CMP(8,9);CMP(4,6);CMP(5,7);CMP(3,4);CMP(5,6);CMP(7,8);
#undef CMP
  #pragma GCC unroll 4
  for(U i=0;i<4;++i){
    a[2*i]=_mm256_unpacklo_epi8(x[2*i],x[2*i+1]);
    a[2*i+1]=_mm256_unpackhi_epi8(x[2*i],x[2*i+1]);
  }
  #pragma GCC unroll 2
  for(U i=0;i<2;++i){
    #pragma GCC unroll 2
    for(U j=0;j<2;++j){
      b[4*i+2*j]=_mm256_unpacklo_epi16(a[4*i+j],a[4*i+j+2]);
      b[4*i+2*j+1]=_mm256_unpackhi_epi16(a[4*i+j],a[4*i+j+2]);
    }
  }
  #pragma GCC unroll 4
  for(U i=0;i<4;++i){
    V lo=_mm256_unpacklo_epi32(b[i],b[i+4]);
    V hi=_mm256_unpackhi_epi32(b[i],b[i+4]);
    _mm256_store_si256((V*)(out+64*i),lo);
    _mm256_store_si256((V*)(out+64*i+32),hi);
  }
    a[0]=_mm256_unpacklo_epi8(x[8],x[9]);a[1]=_mm256_unpackhi_epi8(x[8],x[9]);
    a[2]=_mm256_unpacklo_epi8(x[10],x[11]);a[3]=_mm256_unpackhi_epi8(x[10],x[11]);
    b[0]=_mm256_unpacklo_epi16(a[0],a[2]);b[1]=_mm256_unpackhi_epi16(a[0],a[2]);
    b[2]=_mm256_unpacklo_epi16(a[1],a[3]);b[3]=_mm256_unpackhi_epi16(a[1],a[3]);
    #pragma GCC unroll 2
    for(U i=0;i<2;++i){
      _mm256_store_si256((V*)(tail+64*i),b[2*i]);
      _mm256_store_si256((V*)(tail+64*i+32),b[2*i+1]);
    }
    }

void run(const B*s,U n,U base,U*d,U*end){
 if(n<16384 || n>600000){fastsort::middle(s,n,base,d);return;}
 B* cells=fastsort::mem+380000000;B* extra=cells+16*C;
 const V init=_mm256_broadcastsi128_si256(_mm_set_epi64x(-1,-256));
 for(U i=0;i<16*C;i+=32)_mm256_store_si256((V*)(cells+i),init);
 auto push=[&](const B*r) __attribute__((always_inline)){
   H word;std::memcpy(&word,r+1,2);U key=word&(C-1);B* cell=cells+16*key;U count=cell[0];cell[0]=B(count+1);
   if(__builtin_expect(count<15,1))cell[1+count]=r[0];
   else if(count<32)extra[17*key+count-15]=r[0];
   else return false;
   return true;
 };
 U i=0;const B*cur=s;
 for(;i+R<=n;i+=R,cur+=FUSED_BLOCK){
   _mm_prefetch((const char*)(cur+FUSED_BLOCK),_MM_HINT_T0);
   #pragma GCC unroll 7
   for(U j=0;j<R;++j)if(!push(cur+3*j)){fastsort::middle(s,n,base,d);return;}
 }
 for(;i<n;++i)if(!push(s+size_t(i/R)*FUSED_BLOCK+3*(i%R))){fastsort::middle(s,n,base,d);return;}
 for(U block=0;block<C;block+=32){
   alignas(32) V row[16];transpose(cells+16*block,row);
   alignas(32) B first[256],second[128],counts[32];
   _mm256_store_si256((V*)counts,row[0]);
   loaded_sort(row+1,first,second);
   bool small=_mm256_movemask_epi8(_mm256_cmpgt_epi8(row[0],_mm256_set1_epi8(12)))==0;
   U*dest=d;alignas(32) U final_buffer[32*32+16];
   bool bounded=end-d<32*32+16;if(bounded)dest=final_buffer;
   U* finish=small?emit<true>(first,second,counts,cells+16*block,extra+17*block,block,dest,base):emit<false>(first,second,counts,cells+16*block,extra+17*block,block,dest,base);
   U count=U(finish-dest);if(bounded)std::memcpy(d,final_buffer,count*4);d+=count;
 }
}
}

void sort(unsigned*a,int n){
  using namespace fastsort;
  if(!mem)mem=(B*)((uintptr_t(std::malloc(384000063))+63)&~uintptr_t(63));
  U cap[256],cnt[256];B*start[256];
  for(U k=0;k<256;++k)cap[k]=U((Z(n)+255)/256)*6/5+32;
  if(!split(a,n,cap,start,cnt)){
    std::memset(cap,0,sizeof cap);for(int i=0;i<n;++i)++cap[a[i]>>24];
    split(a,n,cap,start,cnt);
  }
  U off=0;for(U k=0;k<256;++k){if(cnt[k])fused_cells::run(start[k],cnt[k],k<<24,a+off,a+n);off+=cnt[k];}
}

评测结果