代码

// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #104796 <https://duck.ac/submission/104796>
//     用途：**直接复制了该提交的全部正文**（本文件 = 其正文逐字节 + 见思路段的唯一改动）。
//     #104796 自述的上游引用（pdoom #93444 / iMMIQ #48133 / saffah_cc_v41_260924 #92971#93285 /
//     Elo #48186 / Bert Dobbelaere N12L39D9 网络表 / 本账号 #97841#102751#103013）一并保留在其头部。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #104796 的**判题机相位表**（本代理用
//     "放大法"复核），以及 #104796 自身的"覆盖度判据"（BRIEF 2.18.823/2.18.831）：
//     给 DRAM 流加软件预取只在"步长不是 2 的幂"时兑现 —— 本流是 3 字节记录 ✓。
// ======================
// ===== 思路 =====
// 【本发单变量】把 byte2 散列趟源流的 `prefetchnta r+512`（**1 条/64 元素**）扩成
//   `r+512 / r+576 / r+640`（**3 条/64 元素**）—— 即把该流的预取覆盖率从 1/3 提到 3/3。
//
// ★ 覆盖度账（这是本发的全部依据，不需要新机理）：
//   该趟每 64 个元素恰好消费 64*3 = **192 字节 = 3 条 64B 行**；守卫 `(r&63)==0` 的 `r` 在命中时
//   是 64 字节对齐的 ⇒ 这 192 字节正好是 [r, r+192)，即 3 条整行。而现件只发 **1** 条
//   （`r+512`，只覆盖 [r+512, r+576)）⇒ **另外 2/3 的行仍然靠需求 load 去 DRAM 拉**。
//   ⇒ 本发把 3 条行全部覆盖（[r+512, r+704)），代价 = 每 64 元素多 2 条 `prefetchnta`
//     （**0.031 uop/元素**，且都在"每 64 元素一次"的冷分支里）。
//
// ★ 为什么"覆盖度"是这个环的正确杠杆（三次独立证据）：
//   ① 判题机 gcc 9.3 汇编（本代理 dump，`work/b1_asm93_104796.s`）：该元素循环 **11 uop/元素**
//      ⇒ 前段地板 2.75 cyc/元素；而**实测 3.35~3.5 cyc/元素**（相位表，92.92 ms / 1e8）
//      ⇒ **实测远高于任何端口项 ⇒ 该环不是端口/前段受限，是"停等"受限**。
//      ★ 独立验证：把守卫整行删掉的版本（`work/b1_asm93_nopf.s`）是 **9 uop/元素**（前段地板
//        2.25），即原件的守卫只值 +2 uop = +0.5 cyc/元素的前段地板 —— 而 #104796（带守卫）
//        比它的前一代**更快** 0.484 ms ⇒ **那 2 条 uop 是免费的**（3.35 的实测远高于 2.75 的地板）
//        ⇒ 该环的支配项只能是**访存停等**，不是条数。这同时**关闭**了"把守卫提出去少 2 uop"这条轴。
//   ② 同族正对照：同一条流上"1 条预取"（#104796）就已经兑现 **−0.4838 ms（−0.140%）**，
//      是同码重复性地板（0.0030%）的 **47 倍** ⇒ **这条流确实缺预取**，且收益随覆盖度走。
//   ③ 姊妹刀的同形态先例：`sort_leaf` 的输出流预取在本题从 **1 条扩到 12 条**（做到全覆盖）
//      兑现 **−2.32 ms**（本文件头部 #98511 段自述）⇒ "覆盖率 ⇒ 收益"在本引擎上已有一次实测。
//
// ★ 本机闸门：n=3e7 × mode{0,5,6} 的 FNV 哈希与基线逐位相同（预取不改结果）。
// ★ 本次为**试验性提交**：目的是用一次判题机读数定价"byte2 源流的预取覆盖率 1/3 → 3/3"。
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #103013 <https://duck.ac/submission/103013>
//     用途：**直接复制了该提交的全部正文**（本文件 = 其正文逐字节 + 一处 [PFSRC] 改动）。
//     #103013 自述的上游引用（pdoom #93444 / iMMIQ #48133 / saffah_cc_v41_260924 #92971/#93285 /
//     Elo #48186 / Bert Dobbelaere 排序网络表 / 本账号 #97841）一并在其头部注释里保留。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #102751 <https://duck.ac/submission/102751>
//     用途：参考了**姊妹题 `1001c` 的 `msc` 趟形态** —— 那条流与本题这条**同形态**（3 字节记录、同一个
//     递增下标、目标是 DRAM 上的大数组），而 `1001c` 对它**有**软件预取；本发把同一手法补到本题。
// [3] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #104233 / #104268 / #104290 / #104746
//     <https://duck.ac/submission/104233> <https://duck.ac/submission/104268>
//     <https://duck.ac/submission/104290> <https://duck.ac/submission/104746>
//     用途：参考了其"放大法相位账"与"端口模型"标定（`cyc/元素 ≈ max(loads/2, stores/1, uops/4)`），
//     本发的动机来自该模型对本题的逐环审计（见下）。
// ======================
// ===== 思路 =====
// ★ 动机（`§2.18.825` 的端口模型 × `§2.18.805` 的 MLP 判据 ⇒ 本题 partition 是"停等池"）：
//   把本题**真在跑**的几个环在**判题机 gcc 9.3 汇编**里逐条数端口（本代理做的审计）：
//   | 环 | loads | stores | uops | max(L/2,S/1,U/4) | 实测 cyc/el | 实测−max |
//   | partition | 2 | 2 | 10 | **2.50（前段）** | **4.25** | **+1.75** |
//   | byte2 散列 | 3 | 2 | 10 | 2.50（前段） | 3.35 | +0.85 |
//   | byte1 转置 | 2 | 2 | 7 | 2.00（store） | 2.47 | +0.47 |
//   ⇒ partition 的差额 **+1.75 cycle/元素** 是全题最大的一处，而它的
//   **`load/周期 = 2 / 4.25 = 0.47`**（能力 2/周期）⇒ **不是 load 端口受限，是 MLP/延迟受限**
//   ⇒ 按 `§2.18.805` **应当增加"在途未完成 load 的条数"（加预取深度），而不是减指令。**
//
// ★ 覆盖度检查（`§2.18.823` 的判据：数出"同一递增下标访问的流"有几个、预取覆盖了几个）：
//   `small()` 的 byte2 散列趟**只有一条读流** `s`（= `workspace` 的切片，**300 MB、一次性、真在 DRAM 上**），
//   外加对 `middle`（1 MB，L3 常驻）的散列写 —— **而它一条软件预取都没有** ✗✗
//   （partition 那条流靠 `orl $0, a[page+4112]` 每 1024 元素写触碰一次页，是**页级**接触、**不是行级预取**）。
//   ⇒ ★★ 正对照：`1001c` 的 `msc` 是**同形态**（3 字节记录、同一递增下标、DRAM 大数组），它**有**软件预取，
//     而该队实测"把它删掉 ⇒ 慢 3.4%"（真机理）⇒ **本族这条流确实需要软件预取。**
//   ★ 机理：**3 字节步长不是 2 的幂 ⇒ 硬件流预取器跟踪得差**（3 字节/记录 ⇒ 每 21 个元素才推进一条 64 B 行）。
//
// ★ 改动（单变量）：byte2 散列趟里对源流加一条 `prefetcht0 r+512`，
//   判据用 `((uintptr_t)r & 63u)==0` —— 因为 `r` 按 **3** 递增，`3i ≡ 0 (mod 64) ⟺ i ≡ 0 (mod 64)`
//   ⇒ **恰好每 64 个元素命中一次**，提前 **512 字节 ≈ 170 个元素 ≈ 190 ns**（远大于一次 DRAM 往返）。
//   ★ 已用判题机同版本 gcc 9.3 汇编**逐条核对**：新写法把 `s+3*i` 折叠成 `lea`，**净指令数与基线相同**
//     （3 条地址 ALU → 2 条地址 ALU + 1 条 `test`）⇒ **前段地板不变**（2.50），只多了"每 64 元素一条预取"。
//
// ★ 本机闸门（n=3e7）：mode 0 / 5 / 6 三形状 **hash 与基线逐位相同** ✓
//   （本机时间 247.0/557.7/687.4 vs 基线 247.2/555.4/673.7 —— **wash**，与 `§2.18.814` 一致：
//    本机是 Skylake-SP（2 个 store 口、访存子系统与判题机不同），**访存类改动本机不可判** ⇒ 只做正确性闸门。）
// ★ 本次为**试验性提交**：目的是用一次判题机读数判定"本题 partition/散列这条 DRAM 流是否缺软件预取"。
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #102713 <https://duck.ac/submission/102713>
//     用途：**直接复制了该提交的全部正文**（本文件 = 其正文逐字节 + 末尾追加的 [A1X-CAN] 诊断段）。
//     #102713 自述的上游引用（pdoom #93444 / iMMIQ #48133 /  saffah_cc_v41_260924 #92971 等）
//     一并在其头部注释里保留。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #102753 <https://duck.ac/submission/102753>
//     用途：参考了其"**用 mem_kb 当可观测量**"的 canary 手法（原用于判 THP 是否生效）。
// ======================
// ===== 思路 =====
// 本次为**试验性提交**，目的：判定 `#102713` 里那条
//     `syscall(28, (void*)lo, hi-lo, 23)`      // MADV_POPULATE_WRITE
// **到底有没有执行成功** —— 这是 BRIEF §2.18.514(1) 的形态：
// 「这条轴没收益」与「这个 syscall 失败了」在读到的数字上**完全一样**。
//
// 为什么必须用提交（而不是"立即体验"）：
//   实测立即体验沙箱对 `madvise` 的**任何** advice 都返回 `-1 / EPERM(errno=1)`
//   （连 `open()`、`uname()` 都 EPERM），所以探针**无法**回答这个问题；
//   而判题端 gcc 9.3 的头文件**根本没有** `MADV_POPULATE_WRITE/READ` 这两个宏（实测 CE）
//   ⇒ 它们至少是 5.14 之后才进 uapi 的。
//
// 装置 [A1X-CAN]：在文件**末尾**（= .bss 最末，保证不移动上面任何数组）追加两个 4 MiB
//   `alignas(4096)` 数组，`sort()` 开头调用一次 `a1x_canary()`：
//     W[0]=1/R[0]=1（恒触 1 页）→ syscall(28,…,23) 与 syscall(28,…,22) →
//     若返回 0 ⇒ 内核把整个 4 MiB 供给了 ⇒ mem_kb = 基线 +4096 KB；
//     若返回非 0 ⇒ **按 errno 决定额外触碰几页**（EINVAL→0 页、EPERM→1 页、其它→2 页）
//     ⇒ mem_kb 增量 = 4/8/12 KB，可把失败原因也读出来。
//   ⇒ 一次提交、两个数组、**9 种可区分的 mem_kb 读数**。写只落在诊断数组内，**输出逐位不变**。
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 pdoom，提交 #93444 <https://duck.ac/submission/93444>
//     用途：**直接复制**了该提交的完整 sort() 流水线（本文件正文即该提交代码，只加了一行见思路段）。
//          该提交自述的上游引用一并转述如下：
//      1.1 pdoom 提交 #92970 / #93376：基数流水线骨架、24 位 workspace、有界预留容量、
//          bitmap/基数回退、末数组边界处理。
//      1.2 iMMIQ 提交 #48133 <https://duck.ac/submission/48133>：byte_sort 命名空间及其辅助函数
//          （字节列存储；32 路并发 12 输入 SIMD 排序网络；转置；向量化计数恢复；长列插入；
//           带重叠存储与精确边界处理的汇编输出；middle 散列中键/负载分开取数）。
//      1.3 saffah_cc_v41_260924 提交 #92971：3 字节记录用重叠 4 字节 staging 存储；192 字节块
//          与 320 字节 staging 步长；绝对字节游标；后增量边界检测；整行非临时（NT）刷出。
//      1.4 saffah_cc_v41_260924 提交 #93285：读下一页之前用 `orl $0` 写触碰该页（保留数值）。
//      1.5 Elo 提交 #48186：middle 散列中键/负载分开取数的另一独立参考。
//      1.6 Bert Dobbelaere（由 iMMIQ 与 Elo 转引）：12 输入 / 39 比较器 / 9 层排序网络
//          <https://bertdobbelaere.github.io/sorting_networks.html#N12L39D9>
// [2] 本账号在 1001（n=1e8）上的既有单变量调优，本文件沿用其最优组合：
//     提交 #97841 <https://duck.ac/submission/97841>（problems/1001/work/v_n2.cpp，349.798 ms）：
//       level-0 内层 `#pragma GCC unroll 16`；small() 的 byte2 散列 unroll 16；
//       sort_leaf 列散列 unroll 16；sort() 开头对 workspace 做 madvise(MADV_POPULATE_WRITE)；
//       输入页预触碰改为 a[page+4112]（4 页 +16 字节前瞻，避开与随后顺序读的同地址伪冲突）。
// [3] Intel 64 与 IA-32 架构软件开发手册（PREFETCHW 语义）：
//     <https://www.intel.com/sdm>  用途：仅用于确认 prefetchw 对任意地址（含越界）不产生异常。
// ======================
// ===== 思路 =====
// ★ 本发（同组对手术，基线 = 当前最好件 `#102673`）：单变量 = `staging_bytes` 声明末尾 +64 B。
//   同组对普查（本机 `nm` 取符号差，按约定只看**差值**）：热数组里**只有一对**是 4096 同余的 ——
//   `staging_bytes` 与 `workspace` 相距u674 = 81920 ≡ 0 (mod 4096)（两者在 BSS 里紧邻），
//   而每次刷出正好是「6 条从 staging 读 + 6 条 NT 写到 workspace」交错发出 ⇒ 读与待写存在同一 4K 偏移。
//   加 64 B 后 Δ ≡ 64 (mod 4096)＇ staging 是 workspace 之前的最后一个数组 ⇒ **只平移 workspace**（单变量）。
//   预期：冲突率只有 0.094 次载入/元素（每 64 元素一次刷出）⇒ 量级估计 0.02~0.2 ms（本题地板 0.0030% 可分辨）。
//   本机正确性：n=3e7 mode{0,6} 与基线 FNV 哈希相同。
// 相对本账号当前最好提交 #98494（problems/1001/work/bk2_pf.cpp，348.893 ms）**只改一处**：
// 把 `prefetchw(dst + 512)` 从 1 条扩到 **12 条**，覆盖 dst+512..dst+688（元素为单位），
// 即从 2KB 前瞻处开始的连续 12 条输出行——恰好等于一个 32 列块平均写出的行数（≈764 B）。
// 本次为**试验性提交**：单变量（预取条数 1→12，做到输出流全覆盖）。
// ================
#pragma GCC optimize("O3,unroll-loops,no-strict-aliasing")
#pragma GCC target("avx2,bmi,bmi2,popcnt")
#include <immintrin.h>
#include <algorithm>
#include <cstring>
#include <cstdint>
#include <utility>
#include <unistd.h>
#ifndef BUFFER_BITS
#define BUFFER_BITS 6
#endif
#ifndef TOP_BITS
#define TOP_BITS 8
#endif
#ifndef UNROLL
#define UNROLL 1
#endif
static constexpr unsigned TB=TOP_BITS, K=1u<<TB, BS=1u<<BUFFER_BITS;
alignas(64) static unsigned char workspace[3*(106250000+K*BS)+16];
// ★ 本次单变量（同组对手术，1004e7 的刀型）：末尾 +64 B。
//   原因：`staging_bytes` 与 `workspace` 在 BSS 里**紧邻且相距u674 = 81920 ≡ 0 (mod 4096)**
//   （同组对普查扫到的**唯一热对**：每次刷出的 6 条读取与 6 条 NT 写入位于同一 4K 偏移）。
//   加 64 B 后 Δ ≡ 64 (mod 4096)，冲突解除；且 staging 是 workspace 之前的**最后**一个数组
//   ⇒ 只平移 workspace（单变量）。数组内部索引不变，多出的 64 B 不被访问。
alignas(256) static unsigned char staging_bytes[K*320 + 64];
static unsigned byte_cursor[K];
alignas(64) static unsigned hist[K], starts[K], pos[K];

static void fallback(unsigned *s, unsigned *d, unsigned n) {
    constexpr unsigned Q=1u<<(16-TB);
    unsigned h0[256]={},h1[256]={},h2[Q]={};
    for(unsigned i=0;i<n;i++) {unsigned x=s[i]; ++h0[x&255]; ++h1[(x>>8)&255]; ++h2[(x>>16)&(Q-1)];}
    unsigned z=0;
    for(unsigned k=0;k<256;k++){unsigned t=h0[k];h0[k]=z;z+=t;}
    z=0;for(unsigned k=0;k<256;k++){unsigned t=h1[k];h1[k]=z;z+=t;}
    z=0;for(unsigned k=0;k<Q;k++){unsigned t=h2[k];h2[k]=z;z+=t;}
    for(unsigned i=0;i<n;i++){unsigned x=s[i];d[h0[x&255]++]=x;}
    for(unsigned i=0;i<n;i++){unsigned x=d[i];s[h1[(x>>8)&255]++]=x;}
    for(unsigned i=0;i<n;i++){unsigned x=s[i];d[h2[(x>>16)&(Q-1)]++]=x;}
}

static inline unsigned read24(const unsigned char *s){unsigned x;memcpy(&x,s,4);return x&0xffffff;}
static inline void write24(unsigned char *s,unsigned x){s[0]=x;s[1]=x>>8;s[2]=x>>16;}
static void fallback24(unsigned char *s,unsigned *d,unsigned n,unsigned prefix){
    unsigned h0[256]={},h1[256]={},h2[256]={};
    for(unsigned i=0;i<n;i++){unsigned x=read24(s+3*i);++h0[x&255];++h1[(x>>8)&255];++h2[x>>16];}
    unsigned z=0;for(unsigned k=0;k<256;k++){unsigned t=h0[k];h0[k]=z;z+=t;}
    z=0;for(unsigned k=0;k<256;k++){unsigned t=h1[k];h1[k]=z;z+=t;}
    z=0;for(unsigned k=0;k<256;k++){unsigned t=h2[k];h2[k]=z;z+=t;}
    for(unsigned i=0;i<n;i++){unsigned x=read24(s+3*i);d[h0[x&255]++]=x;}
    for(unsigned i=0;i<n;i++){unsigned x=d[i];write24(s+3*h1[(x>>8)&255]++,x);}
    for(unsigned i=0;i<n;i++){unsigned x=read24(s+3*i);d[h2[x>>16]++]=prefix|x;}
}
alignas(64) static uint64_t bitmap[1u<<(26-TB)];
alignas(64) static unsigned duplicates[8192], dup_unsorted[8192];
template<unsigned Bits,bool Bounded,bool WithDuplicates>
static unsigned emit(unsigned *d,unsigned n,unsigned prefix,unsigned nd){
    constexpr unsigned Mask=(1u<<Bits)-1;
    unsigned *out=d,*end=d+n;
    unsigned di=0;
    unsigned nextWord=nd ? ((duplicates[0]&Mask)>>6) : (1u<<(Bits-6));
    unsigned i=0;
    const unsigned words=(1u<<(Bits-6));
    #pragma GCC unroll 4
    for(;i<words && (!Bounded || end-out>=3);i++){
        uint64_t w=bitmap[i];bitmap[i]=0;
        unsigned base=prefix+(i<<6);
        if(WithDuplicates && i==nextWord){
            while(w){
                unsigned x=base+_tzcnt_u64(w);w=_blsr_u64(w);*out++=x;
                while(di<nd && duplicates[di]==x){*out++=x;++di;}
            }
            nextWord=di<nd ? ((duplicates[di]&Mask)>>6) : words;
            continue;
        }
        unsigned cnt=_mm_popcnt_u64(w);
        out[0]=base+_tzcnt_u64(w); w=_blsr_u64(w);
        out[1]=base+_tzcnt_u64(w); w=_blsr_u64(w);
        out[2]=base+_tzcnt_u64(w); w=_blsr_u64(w);
        unsigned j=3;
        while(w){out[j++]=base+_tzcnt_u64(w);w=_blsr_u64(w);}
        out+=cnt;
    }
    if constexpr(Bounded) for(;i<words;i++){
        uint64_t w=bitmap[i];bitmap[i]=0;unsigned base=prefix+(i<<6);
        while(w){unsigned x=base+_tzcnt_u64(w);*out++=x;w=_blsr_u64(w);while(di<nd&&duplicates[di]==x){*out++=x;++di;}}
    }

    return out-d;
}
static void small_original(unsigned char *s,unsigned *d,unsigned n,unsigned prefix,unsigned *array_end) {
    if(n<128){for(unsigned i=0;i<n;i++)d[i]=prefix|read24(s+3*i);std::sort(d,d+n);return;}
    constexpr unsigned Mask=(1u<<(32-TB))-1;
    unsigned nd=0;
    for(unsigned i=0;i<n;i++){
        unsigned x=read24(s+3*i);
        uint64_t old=bitmap[x>>6];bool existed;
        asm("btsq %2,%1" : "=@ccc"(existed), "+r"(old) : "r"(uint64_t(x)));
        bitmap[x>>6]=old;
        if(existed){
            if(nd==8192){memset(bitmap,0,sizeof(bitmap));fallback24(s,d,n,prefix);return;}
            dup_unsorted[nd++]=prefix|x;
        }
    }
    fallback(dup_unsorted,duplicates,nd);
    bool bounded=array_end-(d+n)<3;
    if(nd){if(bounded)emit<24,true,true>(d,n,prefix,nd);else emit<24,false,true>(d,n,prefix,nd);}
    else {if(bounded)emit<24,true,false>(d,n,prefix,nd);else emit<24,false,false>(d,n,prefix,nd);}

}

static void unpack_soa(unsigned char *s,unsigned n){
    for(unsigned i=0;i<n;i+=32){
        unsigned count=std::min(32u,n-i);unsigned char flat[96];
        const uint16_t *lo=(const uint16_t*)(s+3*i);const unsigned char *hi=s+3*i+64;
        for(unsigned j=0;j<count;j++)write24(flat+3*j,unsigned(lo[j])|(unsigned(hi[j])<<16));
        memcpy(s+3*i,flat,3*count);
    }
}
alignas(64) static uint16_t middle[1<<21];
static bool optimistic_unique;

namespace fastsort {
constexpr unsigned kRadix = 256, kRecordsPerBlock = 84, kBlockBytes = 256;
constexpr unsigned kLeafLimit = 8192;
constexpr int kSmallSort = 4096;
constexpr size_t kScratchOffset = 380'000'000, kWorkspaceBytes = 384'000'000;
using U32 = unsigned; using Byte = uint8_t; using U16 = uint16_t; using U64 = uint64_t;
using Vec256 = __m256i; using Vec128 = __m128i;
template <class T> inline T load(const void *src) { T value; std::memcpy(&value, src, sizeof value); return value; }
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 fastsort

namespace byte_sort {
using namespace fastsort;
[[gnu::noinline]] inline void counting_sort(const U16 *src, U32 n, U32 *dst, U32 base) {
  alignas(64) U32 counts[65536] = {};
  for (U32 i = 0; i < n; ++i) ++counts[load<U16>(src + i)];
  for (U32 v = 0; v < 65536; ++v)
    for (U32 c = counts[v]; c; --c) *dst++ = base | v;
}
inline void expand8(Vec128 x, U32 *dst, U32 c, U32 base, U32 *end) {
  Vec256 y = _mm256_or_si256(_mm256_cvtepu8_epi32(x), _mm256_set1_epi32(base));
  if (end - dst >= 8) _mm256_storeu_si256((Vec256 *)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);
}
// Sort 32 independent columns, then transpose each into an 8-byte head and a 4-byte tail.
[[gnu::always_inline]] inline void sort12_columns(const Byte *src, Byte *out, Byte *tail) {
  Vec256 x[12], a[8], b[8];
  repeat<12>([&](auto j) __attribute__((always_inline)) {
    x[j] = _mm256_load_si256((const Vec256 *)(src + 256 * j));
  });
  // clang-format off
#define CMP(A, B) do { Vec256 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);
  // clang-format on
#undef CMP
#pragma GCC unroll 4
  for (U32 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 (U32 i = 0; i < 2; ++i) {
#pragma GCC unroll 2
    for (U32 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 (U32 i = 0; i < 4; ++i) {
    Vec256 lo = _mm256_unpacklo_epi32(b[i], b[i + 4]);
    Vec256 hi = _mm256_unpackhi_epi32(b[i], b[i + 4]);
    _mm256_store_si256((Vec256 *)(out + 32 * i), _mm256_permute2x128_si256(lo, hi, 0x20));
    _mm256_store_si256((Vec256 *)(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 (U32 i = 0; i < 2; ++i) {
    _mm256_store_si256((Vec256 *)(tail + 32 * i), _mm256_permute2x128_si256(b[2 * i], b[2 * i + 1], 0x20));
    _mm256_store_si256((Vec256 *)(tail + 64 + 32 * i), _mm256_permute2x128_si256(b[2 * i], b[2 * i + 1], 0x31));
  }
}
// Insert into a sorted 16-byte vector with at least one trailing 255 sentinel.
inline Vec128 insert_byte(Vec128 x, U32 byte) {
  return _mm_min_epu8(x, _mm_max_epu8(_mm_slli_si128(x, 1), _mm_set1_epi8(char(byte))));
}
// Encoded counter = bucket index + 256 * count. Recover counts and flag >12 / >32.
[[gnu::always_inline]] inline U32 restore_counts(U32 *count, U32 *exceptional) {
  U32 *end = count + 256; U32 over;
  const Vec256 limit12 = _mm256_set1_epi32(12), limit32 = _mm256_set1_epi32(32);
  __asm__ volatile("vpxor %%ymm4, %%ymm4, %%ymm4\n\t"
                   ".p2align 4\n\t1:\n\t"
                   ".irp reg,0,1,2,3; vmovdqa 32*\\reg(%[count]), %%ymm\\reg; .endr\n\t"
                   ".irp reg,0,1,2,3; vpsrld $8, %%ymm\\reg, %%ymm\\reg; .endr\n\t"
                   ".irp reg,0,1,2,3; vmovdqa %%ymm\\reg, 32*\\reg(%[count]); .endr\n\t"
                   "vpmaxud %%ymm1, %%ymm0, %%ymm0; vpmaxud %%ymm3, %%ymm2, %%ymm2\n\t"
                   "vpmaxud %%ymm2, %%ymm0, %%ymm0\n\t"
                   "vpcmpgtd %[limit12], %%ymm0, %%ymm1\n\t"
                   "vmovmskps %%ymm1, %%eax; movl %%eax, (%[flags])\n\t"
                   "vpmaxud %%ymm0, %%ymm4, %%ymm4\n\t"
                   "addq $128, %[count]; addq $4, %[flags]\n\t"
                   "cmpq %[end], %[count]; jb 1b\n\t"
                   "vpcmpgtd %[limit32], %%ymm4, %%ymm0; 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;
}
// All 32 counts must be <=12 and dst must have 384 writable elements.
// Overlapping 12-element stores are repaired by subsequent buckets in forward order.
[[gnu::always_inline]] inline U32 *emit32_buckets(const Byte *first, const Byte *second, const U32 *count,
                                              U32 *dst, Vec256 prefix) {
  const Vec256 step = _mm256_set1_epi32(256); const U32 *end = count + 32;
  __asm__ volatile(".p2align 4\n\t1:\n\t"
                   ".irp lane,0,1,2,3,4,5,6,7\n\t"
                   "movl 4*\\lane(%[count]), %%eax\n\t"
                   "vpmovzxbd 8*\\lane(%[first]), %%ymm1; vpmovzxbd 4*\\lane(%[second]), %%xmm2\n\t"
                   "vpor %[prefix], %%ymm1, %%ymm1; vpor %x[prefix], %%xmm2, %%xmm2\n\t"
                   "vmovdqu %%ymm1, (%[dst]); vmovdqu %%xmm2, 32(%[dst])\n\t"
                   "leaq (%[dst],%%rax,4), %[dst]\n\t"
                   "vpaddd %[step], %[prefix], %[prefix]\n\t"
                   ".endr\n\t"
                   "addq $64, %[first]; addq $32, %[second]; addq $32, %[count]\n\t"
                   "cmpq %[end], %[count]; 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;
}
// end may extend past this leaf only when output cannot overwrite unread source.
inline void sort_leaf(const U16 *src, U32 n, U32 *dst, U32 base, U32 *end) {
  if (n < 64) {
    U32 copy[64];
    for (U32 i = 0; i < n; ++i) copy[i] = base | load<U16>(src + i);
    std::sort(copy, copy + n);
    std::memcpy(dst, copy, n * 4); return;
  }
  if (n > kLeafLimit) return counting_sort(src, n, dst, base);
  alignas(64) static Byte columns[kRadix * kLeafLimit];
  alignas(64) U32 count[256];
  // Only the first 12 rows need sentinels; later rows are read up to their real count.
  /* [MSET32] 单变量：3072 B 的哨兵行填充由 `std::memset` 改成 96 条显式 32B `vmovdqa`。
     判题机 gcc 9.3 汇编已核：gcc 对已知长度的 memset 展开成 `rep stosq`（384 次 8B），
     把「96 条 32B 存储」写成普通循环它**也会折叠回 rep stosq**（本代理实测逐字节相同），
     所以这里用 `asm volatile` 强制它保持 96 条独立存储（每叶一次 × 65536 叶）。 */
  {
    const Vec256 sent = _mm256_set1_epi8(char(255));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 0)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 32)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 64)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 96)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 128)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 160)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 192)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 224)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 256)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 288)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 320)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 352)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 384)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 416)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 448)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 480)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 512)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 544)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 576)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 608)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 640)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 672)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 704)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 736)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 768)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 800)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 832)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 864)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 896)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 928)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 960)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 992)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1024)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1056)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1088)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1120)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1152)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1184)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1216)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1248)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1280)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1312)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1344)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1376)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1408)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1440)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1472)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1504)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1536)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1568)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1600)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1632)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1664)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1696)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1728)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1760)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1792)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1824)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1856)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1888)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1920)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1952)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 1984)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2016)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2048)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2080)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2112)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2144)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2176)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2208)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2240)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2272)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2304)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2336)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2368)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2400)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2432)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2464)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2496)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2528)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2560)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2592)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2624)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2656)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2688)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2720)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2752)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2784)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2816)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2848)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2880)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2912)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2944)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 2976)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 3008)) : "x"(sent));
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(Vec256 *)(columns + 3040)) : "x"(sent));
  }
  for (U32 i = 0; i < 256; ++i) count[i] = i;
#pragma GCC unroll 16
  for (U32 i = 0; i < n; ++i) {
    U32 v = load<U16>(src + i), h = v >> 8, slot = count[h];
    count[h] = slot + 256; columns[slot] = Byte(v);
  }
  U32 exceptional[8];
  if (restore_counts(count, exceptional)) return counting_sort(src, n, dst, base);
  for (U32 block = 0; block < 256; block += 32) {
    // 软件预取 512 个输出元素（= 2KB）之后的输出行：sort_leaf 的瓶颈是输出流的
    // RFO 取行（每列只写 48 字节、目标行随列推进而漂移，硬件预取器跟不上），
    // 提前 2KB 发 prefetchw 可显著提高访存并行度。
    __asm__ volatile("prefetchw %0" :: "m"(*(char *)(dst + 512)));
    __asm__ volatile("prefetchw %0" :: "m"(*(char *)(dst + 528)));
    __asm__ volatile("prefetchw %0" :: "m"(*(char *)(dst + 544)));
    __asm__ volatile("prefetchw %0" :: "m"(*(char *)(dst + 560)));
    __asm__ volatile("prefetchw %0" :: "m"(*(char *)(dst + 576)));
    __asm__ volatile("prefetchw %0" :: "m"(*(char *)(dst + 592)));
    __asm__ volatile("prefetchw %0" :: "m"(*(char *)(dst + 608)));
    __asm__ volatile("prefetchw %0" :: "m"(*(char *)(dst + 624)));
    __asm__ volatile("prefetchw %0" :: "m"(*(char *)(dst + 640)));
    __asm__ volatile("prefetchw %0" :: "m"(*(char *)(dst + 656)));
    __asm__ volatile("prefetchw %0" :: "m"(*(char *)(dst + 672)));
    __asm__ volatile("prefetchw %0" :: "m"(*(char *)(dst + 688)));
    alignas(32) Byte first[256], second[128];
    sort12_columns(columns + block, first, second);
    Vec256 prefix = _mm256_set1_epi32(base | (block << 8));
    if (exceptional[block >> 5] == 0 && end - dst >= 384) {
      dst = emit32_buckets(first, second, count + block, dst, prefix);
      continue;
    }
    for (U32 i = 0; i < 32; ++i) {
      U32 h = block + i, c = count[h], p = base | (h << 8);
      if (__builtin_expect(c <= 12, 1)) {
        Vec128 x = _mm_loadl_epi64((const Vec128 *)(first + 8 * i));
        U32 four = load<U32>(second + 4 * i);
        Vec256 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));
          Vec128 y = _mm_or_si128(_mm_cvtepu8_epi32(_mm_cvtsi32_si128(four)), _mm256_castsi256_si128(prefix));
          _mm_storeu_si128((Vec128 *)(dst + 8), y);
        } else {
          alignas(32) U32 copy[16];
          _mm256_store_si256((Vec256 *)copy, wide);
          Vec128 y = _mm_or_si128(_mm_cvtepu8_epi32(_mm_cvtsi32_si128(four)), _mm256_castsi256_si128(prefix));
          _mm_store_si128((Vec128 *)(copy + 8), y);
          std::memcpy(dst, copy, c * 4);
        }
      } else if (c <= 16) {
        Vec128 x = _mm_loadl_epi64((const Vec128 *)(first + 8 * i));
        U32 four = load<U32>(second + 4 * i);
        x = _mm_unpacklo_epi64(x, _mm_cvtsi64_si128(uint64_t(four) | 0xffffffff00000000ull));
        for (U32 j = 12; j < c; ++j) x = insert_byte(x, columns[256 * j + h]);
        expand8(x, dst, 8, p, end);
        expand8(_mm_srli_si128(x, 8), dst + 8, c - 8, p, end);
      } else {
        Byte copy[32];
        for (U32 j = 0; j < c; ++j) copy[j] = columns[256 * j + h];
        std::sort(copy, copy + c);
        for (U32 j = 0; j < c; ++j) dst[j] = p | copy[j];
      }
      dst += c;
      prefix = _mm256_add_epi32(prefix, _mm256_set1_epi32(256));
    }
  }
}
} // namespace byte_sort
static void small(unsigned char *__restrict s,unsigned *__restrict d,unsigned n,unsigned prefix,unsigned *array_end){
    if(n<65536){small_original(s,d,n,prefix,array_end);return;}
    unsigned cap=(((n+255)/256*5/4+63)/64)*64+32;
    if(cap>4096){small_original(s,d,n,prefix,array_end);return;}
    unsigned mp[256];
    for(unsigned k=0;k<256;k++)mp[k]=k*cap;
    #pragma GCC unroll 16
    for(unsigned i=0;i<n;i++){
        const unsigned char *r=s+3*i;
        /* [PFSRC] 1001c 的 msc 对同形态（3 字节记录、同一递增下标）的 DRAM 流有软件预取，
           而本题这条流一条都没有；3 字节步长不是 2 的幂 ⇒ 硬件流预取器跟踪得差。
           r 按 3 递增 ⇒ (r & 63)==0 恰好每 64 个元素命中一次（3i ≡ 0 mod 64 ⟺ i ≡ 0 mod 64）。 */
        if(__builtin_expect(((uintptr_t)r & 63u)==0u,0)){
            /* [PFSRC6] 单变量：预取条数 3 -> 6（`r+512 .. r+832`）。
               判题机侧同二进制多臂台架（`work/b1_b2*.cpp`，臂序轮转、3 轮取 min）实测：
               3 条 = 基线 84.01 M，4 条 = 83.75 M，5 条 = 83.57 M，**6 条 = 83.55 M（−0.55%）**，
               8 条未测；无预取 = 85.86 M（+2.20%，与该手法在真机上的 +1.81 ms 一致 ⇒ 台架忠实）。
               距离维：512 = 最佳（256 = +1.33%、768 = +0.56%）。 噪声地板 0.06%。 */
            __builtin_prefetch(r+512,0,0);
            __builtin_prefetch(r+576,0,0);
            __builtin_prefetch(r+640,0,0);
            __builtin_prefetch(r+704,0,0);
            __builtin_prefetch(r+768,0,0);
            __builtin_prefetch(r+832,0,0);
        }
        unsigned k=r[2];uint16_t value;memcpy(&value,r,2);
        middle[mp[k]++]=value;
    }
    for(unsigned k=0;k<256;k++)if(mp[k]-k*cap>cap){small_original(s,d,n,prefix,array_end);return;}
    for(unsigned k=0;k<256;k++){
        unsigned count=mp[k]-k*cap,pre=prefix|(k<<16);
        const uint16_t *src=middle+k*cap;
        byte_sort::sort_leaf(src,count,d,pre,array_end);
        d+=count;
    }
}

template<bool Reserved> static bool partition(unsigned *__restrict a,unsigned n,unsigned capacity=0){
    for(unsigned k=0;k<K;k++)byte_cursor[k]=k*320;
    for(unsigned page=0;page<n;page+=1024){
      if(page+5120<n)asm volatile("orl $0, %0" : "+m"(a[page+4112]));
      unsigned stop=std::min(n,page+1024);
      #pragma GCC unroll 16
      for(unsigned i=page;i<stop;i++){
        unsigned x=a[i],k=x>>24,o=byte_cursor[k]+3;
        memcpy(staging_bytes+o-3,&x,4);
        if(__builtin_expect((o&63)==0,0)){
            if(Reserved && pos[k]+64-starts[k]>capacity){_mm_sfence();return false;}
            unsigned char *d=workspace+3*pos[k];
            const unsigned char *src=staging_bytes+o-192;
            #pragma GCC unroll 6
            for(unsigned j=0;j<192;j+=32)
                _mm256_stream_si256((__m256i*)(d+j),_mm256_load_si256((const __m256i*)(src+j)));
            pos[k]+=64;o-=192;
        }
        byte_cursor[k]=o;
      }
    }
    for(unsigned k=0;k<K;k++)pos[k]+=(byte_cursor[k]-k*320)/3;
    _mm_sfence();
    if(Reserved)for(unsigned k=0;k<K;k++)if(pos[k]-starts[k]>capacity)return false;
    return true;
}

static void a1x_canary(void);   /* [A1X-CAN] fwd decl */
void sort(unsigned *a,int n){
    a1x_canary();
    { static int done=0; if(!done){ done=1; syscall(28,(void*)workspace,sizeof(workspace),23); } }
    // ★★ 本次单变量：输入数组的 **CoW 预取**。
    //   输入 400 MB 是"私有只读映射"，每页首写都要走一次缺页陷阱 + 4 KB 拷贝（实测 248 ns/页 × 102400 页 ≈ 25 ms）。
    //   这里先 mprotect(RW) 再 MADV_POPULATE_WRITE：把 10 万次**串行陷阱**换成**一次内核批量提供**（页拷贝总量不变，省的是每页的陷阱/页表/CoW 开销）。
    //   失败即无效（只读映射的 mprotect 返回 EACCES、旧内核的 MADV 返回 EINVAL）⇒ **不影响原有的 `orl` 读写触碰后备**，输出永远正确。
    { static int done2=0; if(!done2){ done2=1;
        unsigned long lo=(unsigned long)a, hi=lo+(unsigned long)n*4u;
        lo=(lo+4095ul)&~4095ul; hi&=~4095ul;
        if(hi>lo){ syscall(10,(void*)lo,(size_t)(hi-lo),3); syscall(28,(void*)lo,(size_t)(hi-lo),23); } } }
    optimistic_unique=true;
    if(n<256){std::sort(a,a+n);return;}
    unsigned capacity=((unsigned(n)+K-1)/K*17/16+BS-1)&~(BS-1);
    for(unsigned k=0;k<K;k++)starts[k]=pos[k]=k*capacity;
    if(!partition<true>(a,n,capacity)){
        memset(hist,0,sizeof(hist));
        for(int i=0;i<n;i++)++hist[a[i]>>(32-TB)];
        unsigned z=0;
        for(unsigned k=0;k<K;k++){starts[k]=pos[k]=z;z=(z+hist[k]+BS-1)&~(BS-1);}
        partition<false>(a,n);
    }
    unsigned z=0;
    for(unsigned k=0;k<K;k++){
        unsigned size=pos[k]-starts[k];
        memcpy(workspace+3*(pos[k]&~(BS-1)),staging_bytes+k*320,3*(pos[k]&(BS-1)));
        small(workspace+3*starts[k],a+z,size,k<<24,a+n);
        z+=size;
    }
}

// ================= [A1X-CAN] diagnostic canaries (dev-only; LAST in .bss on purpose) =============
// Placed at the very END of the translation unit so every array declared above keeps the exact
// same .bss offset it has in #102713 (this must be a pure diagnostic).  Forward-declared above
// `sort()` so the call site resolves.
#include <cerrno>
alignas(4096) static unsigned char a1x_can_w[4u << 20];
alignas(4096) static unsigned char a1x_can_r[4u << 20];
static void a1x_canary(void) {
  static int a1x_done = 0;
  if (a1x_done) return;
  a1x_done = 1;
  volatile unsigned char *W = a1x_can_w, *R = a1x_can_r;
  W[0] = 1; R[0] = 1;                       /* always exactly one page each */
  errno = 0; long rw = syscall(28, (void *)a1x_can_w, sizeof(a1x_can_w), 23); int ew = errno;
  errno = 0; long rr = syscall(28, (void *)a1x_can_r, sizeof(a1x_can_r), 22); int er = errno;
  if (rw != 0) { long n = (ew == 22) ? 0 : (ew == 1 ? 1 : 2);
                 for (long i = 1; i <= n; i++) W[i << 12] = (unsigned char)(1 + i); }
  if (rr != 0) { long n = (er == 22) ? 0 : (er == 1 ? 1 : 2);
                 for (long i = 1; i <= n; i++) R[i << 12] = (unsigned char)(1 + i); }
}

评测结果