代码

// Duck.ac 1001 - C++17, x86-64 AVX2. Submit this file without a main().
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC optimize("O3,unroll-loops,no-strict-aliasing")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#endif
#include <algorithm>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <immintrin.h>

#include <algorithm>
#include <array>
#include <cstdint>
#include <cstring>
#include <immintrin.h>

namespace tail16 {

inline unsigned load16(const uint16_t* p) {
    uint16_t value;
    std::memcpy(&value,p,sizeof(value));
    return value;
}

[[gnu::noinline]] inline void dense(const uint16_t* src,unsigned n,unsigned* dst,unsigned base) {
    alignas(64) unsigned counts[65536]={};
    for(unsigned i=0;i<n;++i)++counts[load16(src+i)];
    for(unsigned v=0;v<65536;++v)
        for(unsigned c=counts[v];c;--c)*dst++=base|v;
}

template<int J,int K>
inline __m256i byte_step8x4(__m256i x) {
    alignas(32) static constexpr auto perm=[] {
        std::array<uint8_t,32> a{};
        for(unsigned i=0;i<32;++i)a[i]=uint8_t((i&15)^J);
        return a;
    }();
    __m256i y=_mm256_shuffle_epi8(x,_mm256_load_si256((const __m256i*)perm.data()));
    __m256i low=_mm256_min_epu8(x,y),high=_mm256_max_epu8(x,y);
    if constexpr(J>=2) {
        constexpr int wordmask=[] {
            int result=0;
            for(unsigned i=0;i<8;++i)
                if(bool((2*i)&J)!=bool((2*i)&K))result|=1<<i;
            return result;
        }();
        return _mm256_blend_epi16(low,high,wordmask);
    } else {
        alignas(32) static constexpr auto mask=[] {
            std::array<uint8_t,32> a{};
            for(unsigned i=0;i<32;++i)
                a[i]=bool((i&15)&J)!=bool((i&15)&K)?255:0;
            return a;
        }();
        return _mm256_blendv_epi8(low,high,_mm256_load_si256((const __m256i*)mask.data()));
    }
}

// Sort the four eight-byte groups independently.
inline __m256i sort8x4(__m256i x) {
    x=byte_step8x4<1,2>(x);
    x=byte_step8x4<2,4>(x);x=byte_step8x4<1,4>(x);
    x=byte_step8x4<4,32>(x);x=byte_step8x4<2,32>(x);x=byte_step8x4<1,32>(x);
    return x;
}

inline __m256i sort16x2(__m256i x) {
    x=byte_step8x4<1,2>(x);
    x=byte_step8x4<2,4>(x);x=byte_step8x4<1,4>(x);
    x=byte_step8x4<4,8>(x);x=byte_step8x4<2,8>(x);x=byte_step8x4<1,8>(x);
    x=byte_step8x4<8,32>(x);x=byte_step8x4<4,32>(x);
    x=byte_step8x4<2,32>(x);x=byte_step8x4<1,32>(x);
    return x;
}

inline void write8(__m128i bytes,unsigned* dst,unsigned size,unsigned base,unsigned* array_end) {
    __m256i v=_mm256_or_si256(_mm256_cvtepu8_epi32(bytes),_mm256_set1_epi32(base));
    if(array_end-dst>=8)_mm256_storeu_si256((__m256i*)dst,v);
    else {
        __m256i mask=_mm256_cmpgt_epi32(_mm256_set1_epi32(size),
                                       _mm256_setr_epi32(0,1,2,3,4,5,6,7));
        _mm256_maskstore_epi32((int*)dst,mask,v);
    }
}

inline void write_large(uint8_t* slot,unsigned size,unsigned* dst,unsigned base,unsigned* array_end) {
    if(size<=16) {
        __m256i x=_mm256_castsi128_si256(_mm_load_si128((const __m128i*)slot));
        __m128i y=_mm256_castsi256_si128(sort16x2(x));
        write8(y,dst,8,base,array_end);
        write8(_mm_srli_si128(y,8),dst+8,size-8,base,array_end);
    } else {
        std::sort(slot,slot+size);
        for(unsigned j=0;j<size;++j)dst[j]=base|slot[j];
    }
}

// The complete source is consumed before output starts, allowing overlap.
// array_end limits temporary vector overstores, which later outputs overwrite.
inline void groups4(const uint16_t* src,unsigned n,unsigned* dst,unsigned base,unsigned* array_end) {
    if(n<64) {
        unsigned copy[64];
        for(unsigned i=0;i<n;++i)copy[i]=base|load16(src+i);
        std::sort(copy,copy+n);
        std::memcpy(dst,copy,n*sizeof(unsigned));
        return;
    }
    if(n>8192) {dense(src,n,dst,base);return;}
    alignas(64) uint8_t slots[16384];
    alignas(64) unsigned cnt[256];
    std::memset(slots,255,8192);
    for(unsigned i=0;i<256;++i)cnt[i]=32*i;
    for(unsigned i=0;i<n;++i) {
        unsigned v=load16(src+i);
        slots[cnt[v>>8]++]=uint8_t(v);
    }
    unsigned overflow=0;
    for(unsigned i=0;i<256;++i) {cnt[i]-=32*i;overflow|=(cnt[i]>32);}
    if(overflow) {dense(src,n,dst,base);return;}

    for(unsigned hi=0;hi<256;hi+=4) {
        const uint8_t* s=slots+32*hi;
        __m128i low=_mm_unpacklo_epi64(_mm_loadl_epi64((const __m128i*)s),
                                     _mm_loadl_epi64((const __m128i*)(s+32)));
        __m128i high=_mm_unpacklo_epi64(_mm_loadl_epi64((const __m128i*)(s+64)),
                                      _mm_loadl_epi64((const __m128i*)(s+96)));
        __m256i packed=_mm256_inserti128_si256(_mm256_castsi128_si256(low),high,1);
        __m256i sorted=sort8x4(packed);
        __m128i a=_mm256_castsi256_si128(sorted),b=_mm256_extracti128_si256(sorted,1);
        __m128i v[4]={a,_mm_srli_si128(a,8),b,_mm_srli_si128(b,8)};
        for(unsigned j=0;j<4;++j) {
            unsigned c=cnt[hi+j],p=base|((hi+j)<<8);
            if(c<=8) {if(c)write8(v[j],dst,c,p,array_end);}
            else write_large(slots+32*(hi+j),c,dst,p,array_end);
            dst+=c;
        }
    }
}

} // namespace tail16




#include <cstddef>
#include <cstdint>
#include <cstring>
#include <immintrin.h>

namespace duck_partition_swwc {
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using u8 = unsigned char;
constexpr u32 block_size = 8192;
constexpr std::size_t guard_bytes = std::size_t((block_size + 20) / 21 + 1) * 64;

static inline std::size_t bucket_bytes(u32 capacity) {
    return ((std::size_t(capacity) + 20) / 21) * 64;
}

static inline std::size_t plan(const u32* src, u32 n,
                              u32 (&capacity)[256]) {
    constexpr u32 sample_size = 262144;
    u32 sampled[256] = {};
    const u32 take = n < sample_size ? n : sample_size;
    if (n <= sample_size) {
        for (u32 i = 0; i < n; ++i) ++sampled[src[i] >> 24];
    } else {
        // Sample sixteen adjacent values from each stratum.
        u32 random = 0x9e3779b9u;
        for (u32 i = 0; i < 16384; ++i) {
            const u32 lo = u32((u64(i) * n) >> 14);
            const u32 hi = u32((u64(i + 1) * n) >> 14);
            random = random * 1664525u + 1013904223u;
            const u32 offset = u32((u64(random) * (hi - lo - 15)) >> 32);
            const u32 at = (lo + offset) & ~u32(15);
            for (u32 j = 0; j < 16; ++j) ++sampled[src[at + j] >> 24];
        }
    }
    std::size_t bytes = 63; // Caller-provided malloc need not be 64B aligned.
    for (u32 k = 0; k < 256; ++k) {
        capacity[k] = take ? u32((u64(n) * (6 * sampled[k] + 80)
                                 + u64(take) * 5 - 1) / (u64(take) * 5)) : 0;
        bytes += bucket_bytes(capacity[k]) + guard_bytes;
    }
    return bytes;
}

#if defined(__GNUC__)
__attribute__((target("avx2")))
#endif
static inline bool within_capacity(u8* const (&next)[256],
                                   u8* const (&limit)[256]) {
    __m256i bad = _mm256_setzero_si256();
    for (unsigned k = 0; k < 256; k += 4) {
        const __m256i p = _mm256_load_si256(reinterpret_cast<const __m256i*>(next + k));
        const __m256i e = _mm256_load_si256(reinterpret_cast<const __m256i*>(limit + k));
        bad = _mm256_or_si256(bad, _mm256_cmpgt_epi64(p, e));
    }
    return _mm256_testz_si256(bad, bad) != 0;
}

// Each output cache line holds 21 packed 24-bit records; byte 63 is padding.
// start[k] is 64B aligned. Input remains unchanged even on capacity failure.
#if defined(__GNUC__)
__attribute__((target("avx2")))
#endif
static inline bool scatter(const u32* src, u32 n, u8* arena,
                           std::size_t arena_bytes,
                           const u32 (&capacity)[256],
                           u8* (&start)[256], u32 (&count)[256]) {
    alignas(64) u8 cache[256][64] = {};
    alignas(64) u32 pos[256] = {};
    alignas(64) u8* next[256];
    alignas(64) u8* limit[256];
    const std::size_t padding = (0 - reinterpret_cast<std::uintptr_t>(arena)) & 63;
    if (padding > arena_bytes) return false;
    std::size_t used = padding;
    for (unsigned k = 0; k < 256; ++k) {
        const std::size_t span = bucket_bytes(capacity[k]) + guard_bytes;
        if (span > arena_bytes - used) return false;
        used += span;
    }
    used = padding;
    for (unsigned k = 0; k < 256; ++k) {
        start[k] = next[k] = arena + used;
        limit[k] = next[k] + bucket_bytes(capacity[k]);
        used += bucket_bytes(capacity[k]) + guard_bytes;
    }
    u32 done = 0;
    while (done != n) {
        const u32 remaining = n - done;
        const u32 take = remaining < block_size ? remaining : block_size;
        const u32 end = done + take;
        #pragma GCC unroll 4
        for (; done != end; ++done) {
            const u32 x = src[done];
            const unsigned k = x >> 24;
            u32 at = pos[k];
            std::memcpy(cache[k] + at, &x, 4);
            at += 3;
            if (__builtin_expect(at == 63, 0)) {
                _mm256_stream_si256(reinterpret_cast<__m256i*>(next[k]),
                    _mm256_load_si256(reinterpret_cast<const __m256i*>(cache[k])));
                _mm256_stream_si256(reinterpret_cast<__m256i*>(next[k] + 32),
                    _mm256_load_si256(reinterpret_cast<const __m256i*>(cache[k] + 32)));
                next[k] += 64;
                at = 0;
            }
            pos[k] = at;
        }
        if (!within_capacity(next, limit)) {
            _mm_sfence();
            return false;
        }
    }
    for (unsigned k = 0; k < 256; ++k) {
        count[k] = u32((next[k] - start[k]) / 64) * 21 + pos[k] / 3;
        if (pos[k]) {
            _mm256_stream_si256(reinterpret_cast<__m256i*>(next[k]),
                _mm256_load_si256(reinterpret_cast<const __m256i*>(cache[k])));
            _mm256_stream_si256(reinterpret_cast<__m256i*>(next[k] + 32),
                _mm256_load_si256(reinterpret_cast<const __m256i*>(cache[k] + 32)));
            next[k] += 64;
        }
    }
    const bool ok = within_capacity(next, limit);
    _mm_sfence();
    return ok;
}
} // namespace duck_partition_swwc



namespace duck1001 {
using u32 = std::uint32_t;
using u16 = std::uint16_t;
using u8 = unsigned char;

static inline u32 load24(const u8* p) {
    u32 v;
    std::memcpy(&v, p, 4);
    return v & 0xffffffu;
}
static inline u32 read_record(const u8* p, std::size_t i) {
    return load24(p + (i / 21) * 64 + (i % 21) * 3);
}
static inline void store24(u8* p, u32 v) {
    std::memcpy(p, &v, 4);
}

// Input may overlap output: consume the complete input before emitting.
static void finish16(const u16* src, u32 count, u32 high, u32* dst) {
    tail16::groups4(src, count, dst, high, dst + count);
}

static void middle(const u8* src, u32 count, u32 top, u32* dst) {
    if (count < 4096) {
        for (u32 i = 0; i < count; ++i)
            dst[i] = (top << 24) | read_record(src, i);
        std::sort(dst, dst + count);
        return;
    }
    alignas(64) u32 hist[256] = {};
    u32 begin[257], next[256];
    for (u32 i = 0; i < count; ++i) ++hist[read_record(src, i) >> 16];
    begin[0] = 0;
    for (unsigned k = 0; k != 256; ++k) {
        next[k] = begin[k];
        begin[k + 1] = begin[k] + hist[k];
    }
    // Access with memcpy avoids type-based aliasing between uint16 and uint32.
    u8* scratch = reinterpret_cast<u8*>(dst);
    for (u32 i = 0; i < count; ++i) {
        u32 v = read_record(src, i);
        u16 low = static_cast<u16>(v);
        std::memcpy(scratch + std::size_t(next[v >> 16]++) * 2, &low, 2);
    }
    // Expansion moves right. Descending order preserves all unread buckets.
    for (int k = 255; k >= 0; --k) {
        if (hist[k]) finish16(reinterpret_cast<const u16*>(scratch) + begin[k],
                              hist[k], (top << 24) | (u32(k) << 16), dst + begin[k]);
    }
}

static void middle_sampled(const u8* src, u32 count, u32 top, u32* dst) {
    if (count < 16384 || count > 600000) {
        middle(src, count, top, dst);
        return;
    }
    // Maximum nominal span is 4*count+512 bytes; reserve another
    // 2*count bytes so even a completely incorrect sample cannot overrun.
    alignas(64) static u8 scratch[3601024];
    alignas(64) u32 sampled[256] = {};
    u32 begin[256], hist[256];
    u8* ptr[256];
    constexpr u32 samples = 4096;
    for (u32 i = 0; i < samples; ++i) {
        u32 index = (std::uint64_t(i) * count) >> 12;
        ++sampled[read_record(src, index) >> 16];
    }
    u32 bytes = 0;
    for (u32 k = 0; k < 256; ++k) {
        begin[k] = bytes;
        ptr[k] = scratch + bytes;
        bytes += 2 * (((std::uint64_t(sampled[k] + 16) * count) >> 12) + 1);
    }
    u32 i = 0;
    const u8* block = src;
    for (; i + 21 <= count; i += 21, block += 64) {
        _mm_prefetch(reinterpret_cast<const char*>(
            reinterpret_cast<std::uintptr_t>(block) + 256), _MM_HINT_T0);
        #pragma GCC unroll 21
        for (u32 j = 0; j < 21; ++j) {
            u32 v = load24(block + std::size_t(j) * 3);
            u16 low = static_cast<u16>(v);
            u8*& p = ptr[v >> 16];
            std::memcpy(p, &low, 2);
            p += 2;
        }
    }
    for (; i < count; ++i) {
        u32 v = read_record(src, i);
        u16 low = static_cast<u16>(v);
        u8*& p = ptr[v >> 16];
        std::memcpy(p, &low, 2);
        p += 2;
    }
    bool overflow = false;
    for (u32 k = 0; k < 256; ++k) {
        hist[k] = u32(ptr[k] - (scratch + begin[k])) / 2;
        u32 limit = k == 255 ? bytes : begin[k + 1];
        overflow |= ptr[k] > scratch + limit;
    }
    if (overflow) {
        u32 offset = 0;
        for (u32 k = 0; k < 256; ++k) {
            begin[k] = offset;
            ptr[k] = scratch + offset;
            offset += 2 * hist[k];
        }
        for (u32 i = 0; i < count; ++i) {
            u32 v = read_record(src, i);
            u16 low = static_cast<u16>(v);
            u8*& p = ptr[v >> 16];
            std::memcpy(p, &low, 2);
            p += 2;
        }
    }
    for (u32 k = 0; k < 256; ++k) {
        if (hist[k]) finish16(reinterpret_cast<const u16*>(scratch + begin[k]),
                              hist[k], (top << 24) | (k << 16), dst);
        dst += hist[k];
    }
}
}

void sort(unsigned* a, int n) {
    using namespace duck1001;
    if (n < 2) return;
    if (n < 4096) { std::sort(a, a + n); return; }
    alignas(64) u32 hist[256] = {}, capacity[256];
    u8* start[256];
    std::size_t bytes = duck_partition_swwc::plan(a, n, capacity);
    u8* buffer = static_cast<u8*>(std::malloc(bytes));
    if (!buffer) { std::sort(a, a + n); return; }
    if (!duck_partition_swwc::scatter(a, n, buffer, bytes, capacity, start, hist)) {
        std::memset(hist, 0, sizeof(hist));
        for (int i = 0; i < n; ++i) ++hist[a[i] >> 24];
        u32 next[256] = {};
        std::size_t offset = 0;
        for (unsigned k = 0; k < 256; ++k) {
            start[k] = buffer + offset;
            offset += ((std::size_t(hist[k]) + 20) / 21) * 64 + 64;
        }
        for (int i = 0; i < n; ++i) {
            u32 v = a[i];
            unsigned k = v >> 24;
            u32 pos = next[k]++;
            store24(start[k] + std::size_t(pos / 21) * 64 + (pos % 21) * 3, v);
        }
    }
    u32 offset = 0;
    for (unsigned k = 0; k < 256; ++k) {
        if (hist[k]) middle_sampled(start[k], hist[k], k, a + offset);
        offset += hist[k];
    }
    std::free(buffer);
}

评测结果