代码

// Single-threaded 32-bit unsigned sort for the stated JudgeDuck task.
// Compile as C++17. No main(), I/O, threads, or OS-specific allocation calls.
// The fixed-capacity layouts are speculative, but correctness is not:
// every speculative pass has worst-case address space and an exact retry.
#include <algorithm>
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <immintrin.h>

#pragma GCC push_options
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=skylake")

namespace duck_sort_v2_detail {
static_assert(sizeof(unsigned) == 4, "32-bit unsigned is required");
// GCC aliasing extension: temporary 16-bit records may reuse the unsigned array.
typedef std::uint16_t U16 __attribute__((__may_alias__));
using U8 = std::uint8_t;

inline unsigned load3(const U8* p) {
    unsigned v;
    std::memcpy(&v, p, 4); // Fourth byte is ignored; every global bucket has padding.
    return v;
}
inline void store3(U8* p, unsigned v) {
    std::memcpy(p, &v, 4); // Consecutive records overlap by one byte, intentionally.
}

bool all_equal(const unsigned* a, unsigned n, unsigned value) {
    const __m256i wanted = _mm256_set1_epi32(static_cast<int>(value));
    unsigned i = 0;
    for (; i + 8 <= n; i += 8) {
        const __m256i v = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(a + i));
        if (_mm256_movemask_epi8(_mm256_cmpeq_epi32(v, wanted)) != -1) return false;
    }
    for (; i < n; ++i) if (a[i] != value) return false;
    return true;
}

// Input is never modified, so an overflowing speculative layout can be retried.
inline void scatter_top(const unsigned* __restrict__ src, unsigned n,
                        U8* __restrict__ dst, unsigned* __restrict__ p) {
    unsigned i = 0;
    for (; i + 16 <= n; i += 16) {
        _mm_prefetch(reinterpret_cast<const char*>(
            reinterpret_cast<std::uintptr_t>(src) + std::size_t(i + 64) * 4), _MM_HINT_NTA);
        #pragma GCC unroll 16
        for (unsigned j = 0; j < 16; ++j) {
            unsigned v = src[i + j], k = v >> 24;
            store3(dst + p[k], v);
            p[k] += 3;
        }
    }
    for (; i < n; ++i) {
        unsigned v = src[i], k = v >> 24;
        store3(dst + p[k], v);
        p[k] += 3;
    }
}

// [B0,B1,B2] -> B0 buckets containing [B1,B2]. No histogram updates here.
inline void scatter_low(const U8* __restrict__ src, unsigned n,
                        U16* __restrict__ dst, unsigned* __restrict__ p) {
    unsigned i = 0;
    for (; i + 16 <= n; i += 16) {
        _mm_prefetch(reinterpret_cast<const char*>(
            reinterpret_cast<std::uintptr_t>(src) + std::size_t(i + 64) * 3), _MM_HINT_T0);
        #pragma GCC unroll 16
        for (unsigned j = 0; j < 16; ++j) {
            unsigned v = load3(src + std::size_t(i + j) * 3);
            dst[p[v & 255]++] = static_cast<U16>(v >> 8);
        }
    }
    for (; i < n; ++i) {
        unsigned v = load3(src + std::size_t(i) * 3);
        dst[p[v & 255]++] = static_cast<U16>(v >> 8);
    }
}

// Visit B0 buckets in increasing order, preserving B0 order within each B1.
// Only B2 needs an explicit histogram; B1 counts come from pointer progress.
template<bool CountB2>
inline void scatter_mid(const U16* __restrict__ src,
                        const unsigned* __restrict__ start,
                        const unsigned* __restrict__ count,
                        U16* __restrict__ dst, unsigned* __restrict__ p,
                        unsigned* __restrict__ count_b2) {
    for (unsigned b0 = 0; b0 < 256; ++b0) {
        const U16* s = src + start[b0];
        unsigned n = count[b0], i = 0;
        for (; i + 16 <= n; i += 16) {
            _mm_prefetch(reinterpret_cast<const char*>(
                reinterpret_cast<std::uintptr_t>(s) + std::size_t(i + 64) * 2), _MM_HINT_T0);
            #pragma GCC unroll 16
            for (unsigned j = 0; j < 16; ++j) {
                unsigned v = s[i + j];
                dst[p[v & 255]++] = static_cast<U16>(b0 | (v & 0xff00));
                if (CountB2) ++count_b2[v >> 8];
            }
        }
        for (; i < n; ++i) {
            unsigned v = s[i];
            dst[p[v & 255]++] = static_cast<U16>(b0 | (v & 0xff00));
            if (CountB2) ++count_b2[v >> 8];
        }
    }
}
} // namespace duck_sort_v2_detail

void sort(unsigned* a, int nn) {
    using namespace duck_sort_v2_detail;
    if (nn <= 1) return;
    const unsigned n = static_cast<unsigned>(nn);
    // The problem fixes n=100,000,000. Also handle small correctness tests.
    if (n < 4096 || n > 100000000u) {
        std::sort(a, a + n);
        return;
    }
    // Sampling here only selects a full equality check; it never proves equality.
    if (a[0] == a[n / 2] && a[0] == a[n - 1] && all_equal(a, n, a[0])) return;

    alignas(64) unsigned start[257], p[256], count[256];
    const unsigned cap = static_cast<unsigned>((std::uint64_t(n) * 9 + 2047) / 2048);
    const unsigned stride = cap * 3 + 4;
    // Tail guard holds an ENTIRE input, not just a statistical safety margin.
    // Even if every key chooses the last bucket, all writes remain allocated.
    U8* b = static_cast<U8*>(std::malloc(std::size_t(stride) * 256 + std::size_t(n) * 3 + 64));
    if (!b) { std::sort(a, a + n); return; }
    for (unsigned k = 0; k < 256; ++k) start[k] = p[k] = k * stride;
    start[256] = stride * 256;
    scatter_top(a, n, b, p);

    bool retry = false;
    unsigned max_count = 0;
    for (unsigned k = 0; k < 256; ++k) {
        count[k] = (p[k] - start[k]) / 3;
        retry |= count[k] > cap;
        max_count = std::max(max_count, count[k]);
    }
    if (retry) {
        unsigned x = 0;
        for (unsigned k = 0; k < 256; ++k) {
            start[k] = p[k] = x;
            x += count[k] * 3 + 4;
        }
        start[256] = x;
        scatter_top(a, n, b, p);
    }

    const unsigned max_cap = static_cast<unsigned>((std::uint64_t(max_count) * 9 + 2047) / 2048);
    const std::size_t work_bytes = (std::size_t(max_cap) * 256 + max_count + 32) * 2;
    U16* spare0 = static_cast<U16*>(std::malloc(work_bytes));
    U16* spare1 = static_cast<U16*>(std::malloc(work_bytes));
    if (!spare0 || !spare1) {
        std::free(spare0); std::free(spare1); std::free(b);
        std::sort(a, a + n); // a is still untouched at this point.
        return;
    }

    alignas(64) unsigned count0[256], count1[256], count2[256];
    alignas(64) unsigned start0[256], start1[256], p0[256], p1[256], p2[256];
    unsigned offset = 0;
    for (unsigned b3 = 0; b3 < 256; ++b3) {
        const unsigned c = count[b3];
        if (!c) continue;
        const U8* src = b + start[b3];
        unsigned* dst = a + offset;
        const unsigned local_cap = static_cast<unsigned>((std::uint64_t(c) * 9 + 2047) / 2048);
        const std::size_t need = (std::size_t(local_cap) * 256 + c) * 2;

        // a's unsorted suffix is disposable: every input is now in b.
        U16* tmp0 = need <= std::size_t(n - offset) * 4
                      ? reinterpret_cast<U16*>(dst) : spare0;
        // b's prefix through this bucket becomes disposable after scatter_low.
        // Do not touch the next bucket's input. Otherwise use separate storage.
        U16* tmp1 = need <= start[b3 + 1] ? reinterpret_cast<U16*>(b) : spare1;
        offset += c;
        for (unsigned k = 0; k < 256; ++k) {
            start0[k] = p0[k] = local_cap * k;
            start1[k] = p1[k] = local_cap * k;
            count2[k] = 0;
        }
        scatter_low(src, c, tmp0, p0);
        retry = false;
        for (unsigned k = 0; k < 256; ++k) {
            count0[k] = p0[k] - start0[k];
            retry |= count0[k] > local_cap;
        }
        if (retry) {
            unsigned x = 0;
            for (unsigned k = 0; k < 256; ++k) {
                start0[k] = p0[k] = x;
                x += count0[k];
            }
            scatter_low(src, c, tmp0, p0);
        }

        scatter_mid<true>(tmp0, start0, count0, tmp1, p1, count2);
        retry = false;
        unsigned x = 0;
        for (unsigned k = 0; k < 256; ++k) {
            count1[k] = p1[k] - start1[k];
            retry |= count1[k] > local_cap;
            p2[k] = x;
            x += count2[k];
        }
        if (retry) {
            x = 0;
            for (unsigned k = 0; k < 256; ++k) {
                start1[k] = p1[k] = x;
                x += count1[k];
            }
            scatter_mid<false>(tmp0, start0, count0, tmp1, p1, count2);
        }

        for (unsigned b1 = 0; b1 < 256; ++b1) {
            const U16* s = tmp1 + start1[b1];
            const unsigned len = count1[b1], common = (b3 << 24) | (b1 << 8);
            unsigned i = 0;
            for (; i + 32 <= len; i += 32) {
                _mm_prefetch(reinterpret_cast<const char*>(
                    reinterpret_cast<std::uintptr_t>(s) + std::size_t(i + 64) * 2), _MM_HINT_T0);
                #pragma GCC unroll 32
                for (unsigned j = 0; j < 32; ++j) {
                    unsigned v = s[i + j];
                    dst[p2[v >> 8]++] = common | _pdep_u32(v, 0x00ff00ff);
                }
            }
            for (; i < len; ++i) {
                unsigned v = s[i];
                dst[p2[v >> 8]++] = common | _pdep_u32(v, 0x00ff00ff);
            }
        }
    }
    std::free(spare0); std::free(spare1); std::free(b);
}
#pragma GCC pop_options

评测结果