代码

// C++17, single thread; interface required by the JudgeDuck task.
// Radix digits: [11 high bits] [10 middle bits] [11 low bits].
// No syscall, timing, input-generator detection, or external dependency.
#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_v3_detail {
using U8 = unsigned char;
using U16 = std::uint16_t;
constexpr unsigned TOP = 2048, LOW = 2048, MID = 1024;
static_assert(sizeof(unsigned) == 4, "This implementation requires 32-bit unsigned.");

inline unsigned load3(const U8* p) {
    unsigned v;
    std::memcpy(&v, p, 4);  // The fourth byte belongs to this allocated 64-byte block.
    return v;
}
inline void store3(U8* p, unsigned v) {
    std::memcpy(p, &v, 4);  // Consecutive records intentionally overlap by one byte.
}
inline void flush64(U8* dst, const U8* src) {
    // Both addresses are 64-byte aligned. Each flush writes a COMPLETE cache line.
    _mm256_stream_si256(reinterpret_cast<__m256i*>(dst),
                       _mm256_load_si256(reinterpret_cast<const __m256i*>(src)));
    _mm256_stream_si256(reinterpret_cast<__m256i*>(dst + 32),
                       _mm256_load_si256(reinterpret_cast<const __m256i*>(src + 32)));
}

// One cache line holds 21 three-byte records and one unused byte.
// 'start' is measured in bytes; every start is a multiple of 64.
void scatter_top(const unsigned* __restrict__ a, unsigned n,
                 U8* __restrict__ b, const unsigned* __restrict__ start,
                 unsigned* __restrict__ count) {
    alignas(64) U8 buffer[TOP][64];
    alignas(64) unsigned filled[TOP] = {};
    alignas(64) unsigned pos[TOP];
    for (unsigned k = 0; k < TOP; ++k) pos[k] = start[k];

    #pragma GCC unroll 8
    for (unsigned i = 0; i < n; ++i) {
        if ((i & 15) == 0) {
            const std::uintptr_t ahead = reinterpret_cast<std::uintptr_t>(a)
                                       + (std::size_t(i) + 128) * 4;
            _mm_prefetch(reinterpret_cast<const char*>(ahead), _MM_HINT_NTA);
        }
        const unsigned v = a[i], k = v >> 21;
        unsigned j = filled[k];
        store3(buffer[k] + j, v);
        j += 3;
        if (__builtin_expect(j == 63, 0)) {
            flush64(b + pos[k], buffer[k]);
            pos[k] += 64;
            j = 0;
        }
        filled[k] = j;
    }
    for (unsigned k = 0; k < TOP; ++k) {
        count[k] = (pos[k] - start[k]) / 64 * 21 + filled[k] / 3;
        if (filled[k]) {
            std::memset(buffer[k] + filled[k], 0, 64 - filled[k]);
            flush64(b + pos[k], buffer[k]);
        }
    }
    _mm_sfence();  // Finish streaming stores before inspecting/reusing their output.
}
}  // namespace duck_sort_v3_detail

void sort(unsigned* a, int nn) {
    using namespace duck_sort_v3_detail;
    if (nn <= 1) return;
    const unsigned n = static_cast<unsigned>(nn);
    if (n < 4096 || n > 100000000u) {
        std::sort(a, a + n);
        return;
    }

    // Speculate ONLY on global bucket spacing, never on correctness.
    // The tail guard holds an entire worst-case bucket. Even when the first
    // layout overflows into adjacent buckets, all writes remain allocated and
    // the source a remains intact. Exact counts then permit a safe retry.
    const unsigned stride = static_cast<unsigned>(
        ((std::uint64_t(n) * 9 / (TOP * 8) + 21) / 21) * 64);
    const unsigned guard = ((n + 20) / 21 + 1) * 64;
    const std::size_t bytes = std::size_t(TOP) * stride + guard + 64;
    U8* raw = static_cast<U8*>(std::malloc(bytes));
    if (!raw) { std::sort(a, a + n); return; }
    U8* b = reinterpret_cast<U8*>((reinterpret_cast<std::uintptr_t>(raw) + 63)
                                 & ~std::uintptr_t(63));
    alignas(64) unsigned start[TOP], count[TOP];
    for (unsigned k = 0; k < TOP; ++k) start[k] = k * stride;
    scatter_top(a, n, b, start, count);

    bool retry = false;
    unsigned max_count = 0;
    for (unsigned k = 0; k < TOP; ++k) {
        max_count = std::max(max_count, count[k]);
        retry |= ((count[k] + 20) / 21 * 64 > stride);
    }
    if (retry) {
        unsigned s = 0;
        for (unsigned k = 0; k < TOP; ++k) {
            start[k] = s;
            s += (count[k] + 20) / 21 * 64;
        }
        scatter_top(a, n, b, start, count);
    }

    U16* tmp = static_cast<U16*>(std::malloc(std::size_t(max_count) * 2 + 64));
    if (!tmp) {
        std::free(raw);
        std::sort(a, a + n);  // No element of a has been changed yet.
        return;
    }
    alignas(64) unsigned count_low[LOW], count_mid[MID];
    alignas(64) unsigned start_low[LOW], pos_low[LOW], pos_mid[MID];
    unsigned out = 0;

    for (unsigned k = 0; k < TOP; ++k) {
        const unsigned c = count[k];
        if (!c) continue;
        const U8* src = b + start[k];
        std::memset(count_low, 0, sizeof(count_low));
        std::memset(count_mid, 0, sizeof(count_mid));

        // Exact local histograms. This is a scan, not a distribution pass.
        unsigned rem = c;
        while (rem >= 21) {
            #pragma GCC unroll 21
            for (unsigned j = 0; j < 21; ++j) {
                const unsigned v = load3(src + j * 3);
                ++count_low[v & 2047];
                ++count_mid[(v >> 11) & 1023];
            }
            src += 64;
            rem -= 21;
        }
        for (unsigned j = 0; j < rem; ++j) {
            const unsigned v = load3(src + j * 3);
            ++count_low[v & 2047];
            ++count_mid[(v >> 11) & 1023];
        }
        unsigned s = 0;
        for (unsigned q = 0; q < LOW; ++q) {
            start_low[q] = pos_low[q] = s;
            s += count_low[q];
        }
        s = 0;
        for (unsigned q = 0; q < MID; ++q) {
            pos_mid[q] = s;
            s += count_mid[q];
        }

        // Second distribution: bucket by low 11 bits. Save only middle 10 bits.
        src = b + start[k];
        rem = c;
        while (rem >= 21) {
            #pragma GCC unroll 21
            for (unsigned j = 0; j < 21; ++j) {
                const unsigned v = load3(src + j * 3);
                tmp[pos_low[v & 2047]++] = (v >> 11) & 1023;
            }
            src += 64;
            rem -= 21;
        }
        for (unsigned j = 0; j < rem; ++j) {
            const unsigned v = load3(src + j * 3);
            tmp[pos_low[v & 2047]++] = (v >> 11) & 1023;
        }

        // Third distribution: visit low-bit buckets in ascending order, then
        // bucket by middle bits. Restore the discarded bits from bucket IDs.
        unsigned* dst = a + out;
        out += c;
        for (unsigned lo = 0; lo < LOW; ++lo) {
            const U16* p = tmp + start_low[lo];
            const unsigned len = count_low[lo], prefix = (k << 21) | lo;
            unsigned j = 0;
            for (; j + 16 <= len; j += 16) {
                #pragma GCC unroll 16
                for (unsigned z = 0; z < 16; ++z) {
                    const unsigned mid = p[j + z];
                    dst[pos_mid[mid]++] = prefix | (mid << 11);
                }
            }
            for (; j < len; ++j) {
                const unsigned mid = p[j];
                dst[pos_mid[mid]++] = prefix | (mid << 11);
            }
        }
    }
    std::free(tmp);
    std::free(raw);
}
#pragma GCC pop_options

评测结果