代码

// duck.ac 1001 v4：单线程 MSD + 全程 in-cache 收尾（无系统调用）
// 评测机约束：mmap/clone 不可用 => 静态 BSS 缓冲；单线程
//
// scan1  hist8:  cnt[k>>24]++                          （L1 计数器，DRAM 顺序读）
// scan2  scatter8: a -> tmp，SWC(256×16)+NT 整行写      （桶起始 16 元素对齐）
// finish 每桶独立递归 finish_rec(SRC=tmp桶, OTHER=a桶区, HOME=a桶区, shift=16):
//   大桶: 按次高字节 MSD 散 SRC->OTHER，子桶 ping-pong 递归
//   小桶(≤4KB): L1 内两趟 8-bit 计数排序直落 HOME
//   shift==0: 元素全相等，memcpy 兜底
// DRAM 流量 ≈ 2.4GB，随机访问全部 L1/L2 驻留
#include <algorithm>
#include <cstdint>
#include <cstring>
#include <immintrin.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi2,popcnt,lzcnt")

namespace {

typedef uint32_t u32;
typedef uint64_t u64;

constexpr size_t CAP_N = 100000000 + 4096;
constexpr size_t L1_CAP = 16384;   // 小桶阈值（字节），子桶平均 6KB 走 L1 路径

u32 tmp_[CAP_N] __attribute__((aligned(4096)));
u32 l1buf_[L1_CAP / 4] __attribute__((aligned(64)));

struct PreTouch {
  PreTouch() {
    volatile char* p = (volatile char*)tmp_;
    for (size_t i = 0; i < sizeof tmp_; i += 4096) p[i] = 0;
  }
};
static PreTouch s_pretouch_;

struct SWC {
  u32 buf[256][16];
  u32* wptr[256];
  u32* dstbase[256];
};
SWC g_swc __attribute__((aligned(64)));

inline void swc_scatter(const u32* src, size_t n, u32* dst, u32* starts, int shift) {
  for (int b = 0; b < 256; ++b) {
    g_swc.wptr[b] = g_swc.buf[b];
    g_swc.dstbase[b] = dst + starts[b];
  }
  const u32* p = src;
  const u32* end = src + n;
  for (; p + 8 <= end; p += 8) {
    __builtin_prefetch(p + 64, 0, 0);
    for (int j = 0; j < 8; ++j) {
      u32 k = p[j];
      int b = (k >> shift) & 0xFF;
      u32* w = g_swc.wptr[b];
      *w++ = k;
      if (__builtin_expect(!((uintptr_t)w & 63), 0)) {
        u32* d = g_swc.dstbase[b];
        __m128i v0 = _mm_load_si128((__m128i*)(w - 16));
        __m128i v1 = _mm_load_si128((__m128i*)(w - 12));
        __m128i v2 = _mm_load_si128((__m128i*)(w - 8));
        __m128i v3 = _mm_load_si128((__m128i*)(w - 4));
        _mm_stream_si128((__m128i*)d, v0);
        _mm_stream_si128((__m128i*)(d + 4), v1);
        _mm_stream_si128((__m128i*)(d + 8), v2);
        _mm_stream_si128((__m128i*)(d + 12), v3);
        g_swc.dstbase[b] = d + 16;
        w = g_swc.buf[b];
      }
      g_swc.wptr[b] = w;
    }
  }
  for (; p < end; ++p) {
    u32 k = *p;
    int b = (k >> shift) & 0xFF;
    u32* w = g_swc.wptr[b];
    *w++ = k;
    if (__builtin_expect(!((uintptr_t)w & 63), 0)) {
      u32* d = g_swc.dstbase[b];
      __m128i v0 = _mm_load_si128((__m128i*)(w - 16));
      __m128i v1 = _mm_load_si128((__m128i*)(w - 12));
      __m128i v2 = _mm_load_si128((__m128i*)(w - 8));
      __m128i v3 = _mm_load_si128((__m128i*)(w - 4));
      _mm_stream_si128((__m128i*)d, v0);
      _mm_stream_si128((__m128i*)(d + 4), v1);
      _mm_stream_si128((__m128i*)(d + 8), v2);
      _mm_stream_si128((__m128i*)(d + 12), v3);
      g_swc.dstbase[b] = d + 16;
      w = g_swc.buf[b];
    }
    g_swc.wptr[b] = w;
  }
  _mm_sfence();
  for (int b = 0; b < 256; ++b) {
    size_t f = g_swc.wptr[b] - g_swc.buf[b];
    u32* d = g_swc.dstbase[b];
    for (size_t i = 0; i < f; ++i) d[i] = g_swc.buf[b][i];
    starts[b] = d - dst + f;
  }
}

// 小桶：剩余位为 [0..shift+7] 共 shift+8 位
//   shift<0: 0 位（全相等）；shift=0: 8 位一趟；shift=8: 16 位两趟；shift=16: 24 位三趟
void small_finish(const u32* src, u32* home, size_t m, int shift) {
  alignas(64) u32 c[256];
  if (shift < 0) {
    if (src != home) memcpy(home, src, m * 4);
    return;
  }
  if (shift == 0) {
    memset(c, 0, sizeof c);
    for (size_t i = 0; i < m; ++i) c[src[i] & 0xFF]++;
    u32 s = 0;
    for (int v = 0; v < 256; ++v) {
      u32 x = c[v];
      c[v] = s;
      s += x;
    }
    if (src == home) {
      for (size_t i = 0; i < m; ++i) {
        u32 k = src[i];
        l1buf_[c[k & 0xFF]++] = k;
      }
      memcpy(home, l1buf_, m * 4);
    } else {
      for (size_t i = 0; i < m; ++i) {
        u32 k = src[i];
        home[c[k & 0xFF]++] = k;
      }
    }
    return;
  }
  // 第一趟：low8 -> l1buf_
  memset(c, 0, sizeof c);
  for (size_t i = 0; i < m; ++i) c[src[i] & 0xFF]++;
  u32 s = 0;
  for (int v = 0; v < 256; ++v) {
    u32 x = c[v];
    c[v] = s;
    s += x;
  }
  for (size_t i = 0; i < m; ++i) {
    u32 k = src[i];
    l1buf_[c[k & 0xFF]++] = k;
  }
  if (shift == 8) {
    // 第二趟：l1buf_ -> home 按 bits8-15
    memset(c, 0, sizeof c);
    for (size_t i = 0; i < m; ++i) c[(l1buf_[i] >> 8) & 0xFF]++;
    s = 0;
    for (int v = 0; v < 256; ++v) {
      u32 x = c[v];
      c[v] = s;
      s += x;
    }
    for (size_t i = 0; i < m; ++i) {
      u32 k = l1buf_[i];
      home[c[(k >> 8) & 0xFF]++] = k;
    }
    return;
  }
  // shift == 16：第二趟 l1buf_ -> mid 按 bits8-15，第三趟 mid -> home 按 bits16-23
  u32* mid = (src != home) ? const_cast<u32*>(src) : (l1buf_ + (sizeof l1buf_ / 4) / 2);
  memset(c, 0, sizeof c);
  for (size_t i = 0; i < m; ++i) c[(l1buf_[i] >> 8) & 0xFF]++;
  s = 0;
  for (int v = 0; v < 256; ++v) {
    u32 x = c[v];
    c[v] = s;
    s += x;
  }
  for (size_t i = 0; i < m; ++i) {
    u32 k = l1buf_[i];
    mid[c[(k >> 8) & 0xFF]++] = k;
  }
  memset(c, 0, sizeof c);
  for (size_t i = 0; i < m; ++i) c[(mid[i] >> 16) & 0xFF]++;
  s = 0;
  for (int v = 0; v < 256; ++v) {
    u32 x = c[v];
    c[v] = s;
    s += x;
  }
  for (size_t i = 0; i < m; ++i) {
    u32 k = mid[i];
    home[c[(k >> 16) & 0xFF]++] = k;
  }
}

// SRC: 数据当前位置；OTHER: 本层散列目标；HOME: 最终归宿；剩余位 [0..shift+7]
void finish_rec(const u32* src, u32* other, u32* home, size_t m, int shift) {
  if (shift < 0) {
    if (src != home) memcpy(home, src, m * 4);
    return;
  }
  size_t cap = (shift >= 16) ? L1_CAP / 2 : L1_CAP;  // 24 位路径需 l1buf 后半暂存
  if (m * 4 <= cap) {
    small_finish(src, home, m, shift);
    return;
  }
  alignas(64) u32 c[256];
  memset(c, 0, sizeof c);
  for (size_t i = 0; i < m; ++i) c[(src[i] >> shift) & 0xFF]++;
  u32 pos[256];
  u32 s = 0;
  for (int v = 0; v < 256; ++v) {
    pos[v] = s;
    s += c[v];
  }
  for (size_t i = 0; i < m; ++i) {
    u32 k = src[i];
    other[pos[(k >> shift) & 0xFF]++] = k;
  }
  u32 ends[256];
  {
    u32 acc = 0;
    for (int v = 0; v < 256; ++v) {
      acc += c[v];
      ends[v] = acc;
    }
  }
  u32 beg = 0;
  for (int v = 0; v < 256; ++v) {
    size_t m2 = ends[v] - beg;
    if (m2) finish_rec(other + beg, const_cast<u32*>(src) + beg, home + beg, m2, shift - 8);
    beg = ends[v];
  }
}

}  // namespace

void sort(unsigned* a, int n) {
  if (n < 4096 || (size_t)n + 4096 > CAP_N) {
    std::sort(a, a + (size_t)n);
    return;
  }
  size_t nn = (size_t)n;

  u32 tpos[256], apos[256];
  {
    u32 c[256] = {0};
    for (size_t i = 0; i < nn; ++i) c[a[i] >> 24]++;
    u32 t = 0, s = 0;
    for (int b = 0; b < 256; ++b) {
      tpos[b] = t;
      apos[b] = s;
      t += (c[b] + 15) & ~15u;
      s += c[b];
    }
  }
  u32 tend[256];
  memcpy(tend, tpos, sizeof tend);
  swc_scatter(a, nn, tmp_, tend, 24);

  for (int b = 0; b < 255; ++b) {
    size_t cnt = tend[b] - tpos[b];
    if (cnt) finish_rec(tmp_ + tpos[b], a + apos[b], a + apos[b], cnt, 16);
  }
  size_t cnt = tend[255] - tpos[255];
  if (cnt) finish_rec(tmp_ + tpos[255], a + apos[255], a + apos[255], cnt, 16);
}

评测结果