代码

// V24: four-at-a-time bitmap output with bounded overlapping stores.
// V24 experiment: leaf bitmap with exact duplicate recovery.
// Duck.ac 1001, C++17 / AVX2. V23: sparse destination prefetch.
// Based on V20 (https://duck.ac/submission/48100).
// Prefetch one destination per three records, twelve records ahead.
// All overflow recovery and output bounds remain exact.
// The 300 ms target has not been reached; see v23/README.md for judge results.
// 12-input 39-comparator network: Bert Dobbelaere,
// 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>
static_assert(sizeof(unsigned)==4 && sizeof(uint16_t)==2,"32-bit unsigned required");
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;
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 c,U base,U* end){
  V y=_mm256_or_si256(_mm256_cvtepu8_epi32(x),_mm256_set1_epi32(base));
  if(end-dst>=8)_mm256_storeu_si256((V*)dst,y);
  else _mm256_maskstore_epi32((int*)dst,_mm256_cmpgt_epi32(_mm256_set1_epi32(c),_mm256_setr_epi32(0,1,2,3,4,5,6,7)),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+32*i),_mm256_permute2x128_si256(lo,hi,0x20));
    _mm256_store_si256((V*)(out+128+32*i),_mm256_permute2x128_si256(lo,hi,0x31));
  }
    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+32*i),_mm256_permute2x128_si256(b[2*i],b[2*i+1],0x20));
      _mm256_store_si256((V*)(tail+64+32*i),_mm256_permute2x128_si256(b[2*i],b[2*i+1],0x31));
    }
    }
// 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))));
}
// i3-8100 / AVX2: restore 32 encoded counters per iteration.
// Compare exact counts, so skewed inputs still reach the dense fallback.
[[gnu::always_inline]] inline U restore_counts(U* count,U* exceptional){
  U* end=count+256;U over;
  const V limit12=_mm256_set1_epi32(12),limit32=_mm256_set1_epi32(32);
  __asm__ volatile(
    "vpxor %%ymm4, %%ymm4, %%ymm4\n\t"
    ".p2align 4\n\t"
    "1:\n\t"
    "vmovdqa 0(%[count]), %%ymm0\n\t"
    "vmovdqa 32(%[count]), %%ymm1\n\t"
    "vmovdqa 64(%[count]), %%ymm2\n\t"
    "vmovdqa 96(%[count]), %%ymm3\n\t"
    "vpsrld $8, %%ymm0, %%ymm0\n\t"
    "vpsrld $8, %%ymm1, %%ymm1\n\t"
    "vpsrld $8, %%ymm2, %%ymm2\n\t"
    "vpsrld $8, %%ymm3, %%ymm3\n\t"
    "vmovdqa %%ymm0, 0(%[count])\n\t"
    "vmovdqa %%ymm1, 32(%[count])\n\t"
    "vmovdqa %%ymm2, 64(%[count])\n\t"
    "vmovdqa %%ymm3, 96(%[count])\n\t"
    "vpmaxud %%ymm1, %%ymm0, %%ymm0\n\t"
    "vpmaxud %%ymm3, %%ymm2, %%ymm2\n\t"
    "vpmaxud %%ymm2, %%ymm0, %%ymm0\n\t"
    "vpcmpgtd %[limit12], %%ymm0, %%ymm1\n\t"
    "vmovmskps %%ymm1, %%eax\n\t"
    "movl %%eax, (%[flags])\n\t"
    "vpmaxud %%ymm0, %%ymm4, %%ymm4\n\t"
    "addq $128, %[count]\n\t"
    "addq $4, %[flags]\n\t"
    "cmpq %[end], %[count]\n\t"
    "jb 1b\n\t"
    "vpcmpgtd %[limit32], %%ymm4, %%ymm0\n\t"
    "vmovmskps %%ymm0, %k[over]\n\t"
    : [count] "+&r"(count), [flags] "+&r"(exceptional), [over] "=&r"(over)
    : [end] "r"(end), [limit12] "x"(limit12), [limit32] "x"(limit32)
    : "rax","ymm0","ymm1","ymm2","ymm3","ymm4","cc","memory");
  return over;
}
[[gnu::always_inline]] inline U* emit32(const B* first,const B* second,const U* count,U* dst,V prefix){
  const V step=_mm256_set1_epi32(256);const U* end=count+32;
  __asm__ volatile(
    ".p2align 4\n\t"
    "1:\n\t"
    "movl 0(%[count]), %%eax\n\t"
    "vpmovzxbd 0(%[first]), %%ymm1\n\t"
    "vpmovzxbd 0(%[second]), %%xmm2\n\t"
    "vpor %[prefix], %%ymm1, %%ymm1\n\t"
    "vpor %x[prefix], %%xmm2, %%xmm2\n\t"
    "vmovdqu %%ymm1, (%[dst])\n\t"
    "vmovdqu %%xmm2, 32(%[dst])\n\t"
    "leaq (%[dst],%%rax,4), %[dst]\n\t"
    "vpaddd %[step], %[prefix], %[prefix]\n\t"
    "movl 4(%[count]), %%eax\n\t"
    "vpmovzxbd 8(%[first]), %%ymm1\n\t"
    "vpmovzxbd 4(%[second]), %%xmm2\n\t"
    "vpor %[prefix], %%ymm1, %%ymm1\n\t"
    "vpor %x[prefix], %%xmm2, %%xmm2\n\t"
    "vmovdqu %%ymm1, (%[dst])\n\t"
    "vmovdqu %%xmm2, 32(%[dst])\n\t"
    "leaq (%[dst],%%rax,4), %[dst]\n\t"
    "vpaddd %[step], %[prefix], %[prefix]\n\t"
    "movl 8(%[count]), %%eax\n\t"
    "vpmovzxbd 16(%[first]), %%ymm1\n\t"
    "vpmovzxbd 8(%[second]), %%xmm2\n\t"
    "vpor %[prefix], %%ymm1, %%ymm1\n\t"
    "vpor %x[prefix], %%xmm2, %%xmm2\n\t"
    "vmovdqu %%ymm1, (%[dst])\n\t"
    "vmovdqu %%xmm2, 32(%[dst])\n\t"
    "leaq (%[dst],%%rax,4), %[dst]\n\t"
    "vpaddd %[step], %[prefix], %[prefix]\n\t"
    "movl 12(%[count]), %%eax\n\t"
    "vpmovzxbd 24(%[first]), %%ymm1\n\t"
    "vpmovzxbd 12(%[second]), %%xmm2\n\t"
    "vpor %[prefix], %%ymm1, %%ymm1\n\t"
    "vpor %x[prefix], %%xmm2, %%xmm2\n\t"
    "vmovdqu %%ymm1, (%[dst])\n\t"
    "vmovdqu %%xmm2, 32(%[dst])\n\t"
    "leaq (%[dst],%%rax,4), %[dst]\n\t"
    "vpaddd %[step], %[prefix], %[prefix]\n\t"
    "movl 16(%[count]), %%eax\n\t"
    "vpmovzxbd 32(%[first]), %%ymm1\n\t"
    "vpmovzxbd 16(%[second]), %%xmm2\n\t"
    "vpor %[prefix], %%ymm1, %%ymm1\n\t"
    "vpor %x[prefix], %%xmm2, %%xmm2\n\t"
    "vmovdqu %%ymm1, (%[dst])\n\t"
    "vmovdqu %%xmm2, 32(%[dst])\n\t"
    "leaq (%[dst],%%rax,4), %[dst]\n\t"
    "vpaddd %[step], %[prefix], %[prefix]\n\t"
    "movl 20(%[count]), %%eax\n\t"
    "vpmovzxbd 40(%[first]), %%ymm1\n\t"
    "vpmovzxbd 20(%[second]), %%xmm2\n\t"
    "vpor %[prefix], %%ymm1, %%ymm1\n\t"
    "vpor %x[prefix], %%xmm2, %%xmm2\n\t"
    "vmovdqu %%ymm1, (%[dst])\n\t"
    "vmovdqu %%xmm2, 32(%[dst])\n\t"
    "leaq (%[dst],%%rax,4), %[dst]\n\t"
    "vpaddd %[step], %[prefix], %[prefix]\n\t"
    "movl 24(%[count]), %%eax\n\t"
    "vpmovzxbd 48(%[first]), %%ymm1\n\t"
    "vpmovzxbd 24(%[second]), %%xmm2\n\t"
    "vpor %[prefix], %%ymm1, %%ymm1\n\t"
    "vpor %x[prefix], %%xmm2, %%xmm2\n\t"
    "vmovdqu %%ymm1, (%[dst])\n\t"
    "vmovdqu %%xmm2, 32(%[dst])\n\t"
    "leaq (%[dst],%%rax,4), %[dst]\n\t"
    "vpaddd %[step], %[prefix], %[prefix]\n\t"
    "movl 28(%[count]), %%eax\n\t"
    "vpmovzxbd 56(%[first]), %%ymm1\n\t"
    "vpmovzxbd 28(%[second]), %%xmm2\n\t"
    "vpor %[prefix], %%ymm1, %%ymm1\n\t"
    "vpor %x[prefix], %%xmm2, %%xmm2\n\t"
    "vmovdqu %%ymm1, (%[dst])\n\t"
    "vmovdqu %%xmm2, 32(%[dst])\n\t"
    "leaq (%[dst],%%rax,4), %[dst]\n\t"
    "vpaddd %[step], %[prefix], %[prefix]\n\t"
    "addq $64, %[first]\n\t"
    "addq $32, %[second]\n\t"
    "addq $32, %[count]\n\t"
    "cmpq %[end], %[count]\n\t"
    "jb 1b\n\t"
    : [dst] "+&r"(dst), [prefix] "+&x"(prefix), [count] "+&r"(count), [first] "+&r"(first), [second] "+&r"(second)
    : [end] "r"(end), [step] "x"(step)
    : "rax","ymm1","ymm2","cc","memory");
  return dst;
}
// Extended end is allowed only for independent-source forward output.
inline void columns_merge(const H* src,U n,U* dst,U base,U* end){
  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) static B columns[256*8192];
  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 exceptional[8];
  if(restore_counts(count,exceptional)){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);
    V prefix=_mm256_set1_epi32(base|(block<<8));
    if(exceptional[block>>5]==0 && end-dst>=384){
      dst=emit32(first,second,count+block,dst,prefix);
      continue;
    }
    for(U i=0;i<32;++i){
      U h=block+i,c=count[h],p=base|(h<<8);
      if(__builtin_expect(c<=12,1)){
      W x=_mm_loadl_epi64((const W*)(first+8*i));
      uint32_t four;std::memcpy(&four,second+4*i,4);
        V wide=_mm256_or_si256(_mm256_cvtepu8_epi32(x),prefix);
        if(__builtin_expect(end-dst>=12,1)){
          __asm__ volatile("vmovdqu {%1, %0|%0, %1}"
                        : "=m"(*reinterpret_cast<__m256i_u*>(dst)) : "x"(wide));
          W y=_mm_or_si128(_mm_cvtepu8_epi32(_mm_cvtsi32_si128(four)),_mm256_castsi256_si128(prefix));
    _mm_storeu_si128((W*)(dst+8),y);
        }else{
          alignas(32) U copy[16];
          _mm256_store_si256((V*)copy,wide);
          W y=_mm_or_si128(_mm_cvtepu8_epi32(_mm_cvtsi32_si128(four)),_mm256_castsi256_si128(prefix));
          _mm_store_si128((W*)(copy+8),y);
          std::memcpy(dst,copy,c*4);
        }
      } else if(c<=16){
      W x=_mm_loadl_epi64((const W*)(first+8*i));
      uint32_t four;std::memcpy(&four,second+4*i,4);
        x=_mm_unpacklo_epi64(x,_mm_cvtsi64_si128(uint64_t(four)|0xffffffff00000000ull));
        for(U j=12;j<c;++j)x=insert_byte(x,columns[256*j+h]);
        write8(x,dst,8,p,end);write8(_mm_srli_si128(x,8),dst+8,c-8,p,end);
      }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];
      }
      dst+=c;
      prefix=_mm256_add_epi32(prefix,_mm256_set1_epi32(256));
    }
  }
}
}
namespace fastsort {
using U=unsigned;using B=unsigned char;using H=uint16_t;using Z=uint64_t;
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);
}

// Complete collection before output makes this safe for overlapping leaf input.
bool bitmap_leaf(const B* s,U n,U base,U* d){
  if(n<64||n>8192)return false;
  alignas(64) uint64_t bits[1024]={};
  U duplicates[129],ndup=0;
  for(U i=0;i<n;++i){
    H half;std::memcpy(&half,s+2*i,2);U x=half;
    U word=x>>6;uint64_t mask=uint64_t(1)<<(x&63),old=bits[word];
    if(old&mask){
      if(ndup==128)return false;
      duplicates[ndup++]=x;
    }
    bits[word]=old|mask;
  }
  std::sort(duplicates,duplicates+ndup);duplicates[ndup]=65536;
  U next=0;U* const end=d+n;
  for(U word=0;word<1024;++word){
    uint64_t pending=bits[word];
    if(!pending)continue;
    const U count=_mm_popcnt_u64(pending);
    if(count<=4 && duplicates[next]>>6!=word && end-d>=4){
      const U prefix=base|(word<<6);
      // Unused lanes are overwritten by later output; stay within this leaf.
      fastsort::repeat<4>([&](auto lane) __attribute__((always_inline)){
        d[lane]=prefix|U(_tzcnt_u64(pending));pending=_blsr_u64(pending);
      });
      d+=count;continue;
    }
    while(pending){
      U x=(word<<6)+_tzcnt_u64(pending);pending=_blsr_u64(pending);
      *d++=base|x;
      while(duplicates[next]==x){*d++=base|x;++next;}
    }
  }
  return true;
}

void leaf(const B*s,U n,U base,U*d,U*end=nullptr){if(!bitmap_leaf(s,n,base,d))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<72;j+=12)repeat<12>([&](auto q) __attribute__((always_inline)){
        if constexpr(size_t(q)%3==0){
          U future=b[3*(j+12+q)+2];_mm_prefetch((const char*)p[future],_MM_HINT_T0);
        }
        const B* r=b+3*(j+q);U key=r[2];H lo;std::memcpy(&lo,r,2);std::memcpy(p[key],&lo,2);p[key]+=2;
      });
      repeat<12>([&](auto q) __attribute__((always_inline)){
        const B* r=b+3*(72+q);U key=r[2];H lo;std::memcpy(&lo,r,2);std::memcpy(p[key],&lo,2);p[key]+=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];}
}
}
void sort(unsigned*a,int n){
  using namespace fastsort;
  if(n<2)return;
  if(n<4096||n>100000000){std::sort(a,a+n);return;}
  void*raw=std::malloc(384000063);if(!raw){std::sort(a,a+n);return;}
  mem=(B*)((uintptr_t(raw)+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])middle(start[k],cnt[k],k<<24,a+off);off+=cnt[k];}
  std::free(raw);
}

评测结果