代码

// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #106866 <https://duck.ac/submission/106866>
//     用途：**本文件正文 = #106866 的完整源码**（本地副本 `work/b1v_emit.cpp`），只改 `sort_leaf`
//     的 byte1 散列趟取数形态（见思路段）。#106866 之前的本账号上游链：
//     1.1 <https://duck.ac/submission/106861> 本账号 —— [MSET32]。
//     1.2 <https://duck.ac/submission/106840> 本账号 —— byte2 趟分块 + [PFSRC6]。
//     1.3 <https://duck.ac/submission/106285> / <https://duck.ac/submission/106201> 本账号 —— pad/capacity 与 s2_ 基座。
//     1.4 <https://duck.ac/submission/101817> duck.ac 用户 codex_astra —— `partition`/`sort_leaf` 血统。
//     1.5 <https://duck.ac/submission/105161> 本账号（1001，已达标）—— [PFSRC6]/[MSET32] 来源。
//     1.6 <https://duck.ac/submission/106183> duck.ac 用户 saffah_codex_6s_agg2 —— 慢列向量化发射片段来源。
//     1.7 <https://duck.ac/problem/1001b> 题目页（sort 2^27 个 u32，单测试点）。
// [2] 本账号工作区工件 `work/b1v_mb1.cpp`（本席自写的隔离微基准，**未提交**）——本发刀型的本地依据。
// ======================
// ===== 思路 =====
// **单变量（一处）：`sort_leaf` 的 byte1 散列趟由"逐元素 16 位取数"改成"4 元素/次 64 位取数"。**
//   * 原形态：`U32 v = load<U16>(src+i), h = v>>8, slot = count[h]; count[h]=slot+256; columns[slot]=Byte(v);`
//     ⇒ 每元素 1 条 16 位 load + `mov/movzbl` 两条取高字节 + 游标 RMW + 1 字节存。
//   * 本形态：一次 `memcpy(&q, src+i, 8)` 出 4 个元素，高字节用 `(q>>8k)&0xff` 直接取
//     ⇒ 每元素 0.25 条 load，取高字节的指令数同为 1，游标/数据存不变。
//   * 依据：本席隔离微基准（`work/b1v_mb1.cpp`：middle 1.29 MB / columns 2 MB / count 1 KB 全部 L1-L2 驻留、
//     7 轮取 min）**2.116 → 1.956 cycle/元素（−7.6%）**；同一台架里"目的地址换成 64 B 哑缓冲" = 1.221、
//     "删掉游标 store" = 1.511 ⇒ 该环的楼板 ~1.2，本刀取回其中约 1/5。
//   * 稳定性（LSD 基数排序的必需前提）：同一次 load 的 4 个元素按**低到高**处理，与逐元素版
//     逐位同序 ⇒ 桶内写入顺序逐位不变 ⇒ 输出逐位不变（仍按纪律在生产 n 跑逐元素闸门）。
// 提交目的 = **定价 + 兑现**（缺口 0.809895 ms）。判据 = 与 `#106866`（455.971702 ms）单变量比。
// ★ 声明：只改取数/取字节的形态，不改布局/算法/数据流；失败只关掉这一条路。
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #106861 <https://duck.ac/submission/106861>
//     用途：**本文件正文 = #106861 的完整源码**（本地副本 `work/b1v_m32.cpp`），只改 `sort_leaf`
//     慢列（`count[h] ∈ [17,32]`）的输出发射形态（见思路段）。#106861 之前的本账号上游链一并列出：
//     1.1 <https://duck.ac/submission/106840> 本账号 —— byte2 散列趟分块 + 6 条 `__builtin_prefetch(r+512..832)`。
//     1.2 <https://duck.ac/submission/106285> 本账号 —— BSS pad 2752 + `capacity` 末尾 `+BS`。
//     1.3 <https://duck.ac/submission/106201> 本账号 —— 其直接上游（s2_ 的 SIMD 网络件）。
//     1.4 <https://duck.ac/submission/101817> duck.ac 用户 codex_astra —— `partition`/`sort_leaf`/
//         16 输入网络来源。
//     1.5 <https://duck.ac/submission/105161> 本账号（1001，n=1e8，已达标）—— [PFSRC6] 预取参数与
//         [MSET32] 哨兵填充写法的**直接复制**来源。
//     1.6 <https://duck.ac/problem/1001b> 题目页（sort 2^27 个 u32，单测试点）。
// [2] duck.ac 用户 saffah_codex_6s_agg2，提交 #106183 <https://duck.ac/submission/106183>
//     用途：**直接复制**其 `sort_leaf` 慢列的向量化发射片段（`vlo/vhi` 拆分 + 3~4 条
//     `vpmovzxbd`+`vpor`+`vmovdqu`，以及 `end-dst >= (c<=24?24:32)` 的边界守卫与标量回退）。
//     该用户的文件自述其上游为本账号 #104352、#106150、#106157（本账号的 AVX2 网络/四向量发射）。
//     2.1 K. E. Batcher, "Sorting Networks and Their Applications" (1968)
//         <https://doi.org/10.1145/1468075.1468121> —— 仅用于确认本件沿用的 32 字节网络是合法排序网络
//         （未改动其比较器序列）。
// [3] Intel 64 与 IA-32 架构软件开发手册 <https://www.intel.com/sdm>
//     用途：确认 `PREFETCHh` 不触发异常、`vmovdqa`/`vpmovzxbd`/`vpsrldq`/`vmovdqu` 的语义与写边界。
// ======================
// ===== 思路 =====
// **单变量（一处）：`sort_leaf` 慢列（`count[h]` ∈ [17,32]）的发射由"逐元素标量存"改成向量化发射。**
//   * 原形态：`sort32_byte` 的结果先 `vmovdqu` 存回 `copy[32]`，再
//     `for(j=0;j<c;++j) dst[j]=base|(h<<8)|copy[j]` ⇒ 每列约 2 条向量 op + **c 条标量 load + c 条标量 store**
//     （c≈19 ⇒ ~40 条内存操作/列）。
//   * 本形态（引用 [2] 的片段）：`sorted` 留在寄存器里，`vpmovzxbd` 一次把 8 个字节扩成 8×u32、
//     `vpor` 上前缀、`vmovdqu` 32B 存出 ⇒ **每列 3~4 条（8 值/条）**，且省掉"存回 copy 再逐元素读"。
//     守卫 `end-dst >= (c<=24?24:32)` 保证靠近数组末尾时退回标量路径（不越界写）。
//   * 定价依据：该慢列路径在本题 **58662 次/场**（我方件内注释的实测计数）；原形态 ~100 uops/次、
//     新形态 ~16 uops/次 ⇒ 省 ≈4.9M uops ≈ 1.25 Mcyc ≈ **0.35 ms 量级**（缺口为 0.869063 ms）。
//   * 输出逐位不变：两条路径写入的 `dst[0..c-1]` 完全相同（`sorted` 的前 c 个字节 = 该列升序前 c 个）；
//     向量路径多写的 (24-c) 个位置被同一 `dst += c` 推进的下一个桶覆盖，数组末尾由守卫排除 ✓
//     ⇒ 仍按纪律在生产 n（2^27）跑逐元素闸门。
// 提交目的 = **定价 + 兑现**。判据 = 与 `#106861`（456.030870 ms）单变量比。
// ★ 声明：只改慢列的发射指令形态；失败只关掉这一条路。
// ================
#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>
#if defined(__APPLE__)
#define syscall(...) ((long)-1)
#endif
#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;
static constexpr unsigned NPORT = 134217728u;
alignas(64) static unsigned char workspace[3u*(256u*557056u + 256u*64u) + 4096u + 16u];
alignas(256) static unsigned char staging_bytes[K*320];
static unsigned byte_cursor[K];
alignas(64) static unsigned hist[K], starts[K], pos[K];
static inline unsigned read24(const unsigned char *s){unsigned x;memcpy(&x,s,4);return x&0xffffff;}
static void small_original(unsigned char*s,unsigned*d,unsigned n,unsigned prefix,unsigned*){
for(unsigned i=0;i<n;++i)d[i]=prefix|read24(s+3*i);
std::sort(d,d+n);
}
#define SM7_PAD (2752u)
static_assert(SM7_PAD == 2752u, "sm7_pad config echo");
alignas(64) static unsigned char sm7_pad[SM7_PAD] __attribute__((used));
static_assert(sizeof(sm7_pad) == SM7_PAD, "sm7_pad size echo");
alignas(2097152) static uint16_t middle[1<<21];
namespace fastsort {
constexpr unsigned kRadix=256;
constexpr unsigned kLeafLimit = 8192;
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>{});
}
}
// ===== s2_: SIMD 32-byte sorting network (see s2_mknet.py) =====
namespace s2_net {
alignas(32) static const unsigned char shuf[4][32] = {
  {1,0,3,2,5,4,7,6,9,8,11,10,13,12,15,14,1,0,3,2,5,4,7,6,9,8,11,10,13,12,15,14},
  {2,3,0,1,6,7,4,5,10,11,8,9,14,15,12,13,2,3,0,1,6,7,4,5,10,11,8,9,14,15,12,13},
  {4,5,6,7,0,1,2,3,12,13,14,15,8,9,10,11,4,5,6,7,0,1,2,3,12,13,14,15,8,9,10,11},
  {8,9,10,11,12,13,14,15,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0,1,2,3,4,5,6,7},
};
alignas(32) static const signed char choose_min[15][32] = {
  {-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1},
  {-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1},
  {-1,0,-1,0,0,-1,0,-1,-1,0,-1,0,0,-1,0,-1,-1,0,-1,0,0,-1,0,-1,-1,0,-1,0,0,-1,0,-1},
  {-1,-1,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1},
  {-1,-1,0,0,-1,-1,0,0,0,0,-1,-1,0,0,-1,-1,-1,-1,0,0,-1,-1,0,0,0,0,-1,-1,0,0,-1,-1},
  {-1,0,-1,0,-1,0,-1,0,0,-1,0,-1,0,-1,0,-1,-1,0,-1,0,-1,0,-1,0,0,-1,0,-1,0,-1,0,-1},
  {-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1},
  {-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1},
  {-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1},
  {-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1},
  {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  {-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0},
  {-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0},
  {-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0},
  {-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0},
};
static inline __m256i sort32_byte(__m256i v){
  __m256i p0=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
  __m256i lo0=_mm256_min_epu8(v,p0),hi0=_mm256_max_epu8(v,p0);
  v=_mm256_blendv_epi8(hi0,lo0,_mm256_load_si256((const __m256i*)choose_min[0]));
  __m256i p1=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
  __m256i lo1=_mm256_min_epu8(v,p1),hi1=_mm256_max_epu8(v,p1);
  v=_mm256_blendv_epi8(hi1,lo1,_mm256_load_si256((const __m256i*)choose_min[1]));
  __m256i p2=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
  __m256i lo2=_mm256_min_epu8(v,p2),hi2=_mm256_max_epu8(v,p2);
  v=_mm256_blendv_epi8(hi2,lo2,_mm256_load_si256((const __m256i*)choose_min[2]));
  __m256i p3=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[2]));
  __m256i lo3=_mm256_min_epu8(v,p3),hi3=_mm256_max_epu8(v,p3);
  v=_mm256_blendv_epi8(hi3,lo3,_mm256_load_si256((const __m256i*)choose_min[3]));
  __m256i p4=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
  __m256i lo4=_mm256_min_epu8(v,p4),hi4=_mm256_max_epu8(v,p4);
  v=_mm256_blendv_epi8(hi4,lo4,_mm256_load_si256((const __m256i*)choose_min[4]));
  __m256i p5=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
  __m256i lo5=_mm256_min_epu8(v,p5),hi5=_mm256_max_epu8(v,p5);
  v=_mm256_blendv_epi8(hi5,lo5,_mm256_load_si256((const __m256i*)choose_min[5]));
  __m256i p6=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[3]));
  __m256i lo6=_mm256_min_epu8(v,p6),hi6=_mm256_max_epu8(v,p6);
  v=_mm256_blendv_epi8(hi6,lo6,_mm256_load_si256((const __m256i*)choose_min[6]));
  __m256i p7=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[2]));
  __m256i lo7=_mm256_min_epu8(v,p7),hi7=_mm256_max_epu8(v,p7);
  v=_mm256_blendv_epi8(hi7,lo7,_mm256_load_si256((const __m256i*)choose_min[7]));
  __m256i p8=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
  __m256i lo8=_mm256_min_epu8(v,p8),hi8=_mm256_max_epu8(v,p8);
  v=_mm256_blendv_epi8(hi8,lo8,_mm256_load_si256((const __m256i*)choose_min[8]));
  __m256i p9=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
  __m256i lo9=_mm256_min_epu8(v,p9),hi9=_mm256_max_epu8(v,p9);
  v=_mm256_blendv_epi8(hi9,lo9,_mm256_load_si256((const __m256i*)choose_min[9]));
  __m256i p10=_mm256_permute2x128_si256(v,v,0x01);
  __m256i lo10=_mm256_min_epu8(v,p10),hi10=_mm256_max_epu8(v,p10);
  v=_mm256_blendv_epi8(hi10,lo10,_mm256_load_si256((const __m256i*)choose_min[10]));
  __m256i p11=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[3]));
  __m256i lo11=_mm256_min_epu8(v,p11),hi11=_mm256_max_epu8(v,p11);
  v=_mm256_blendv_epi8(hi11,lo11,_mm256_load_si256((const __m256i*)choose_min[11]));
  __m256i p12=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[2]));
  __m256i lo12=_mm256_min_epu8(v,p12),hi12=_mm256_max_epu8(v,p12);
  v=_mm256_blendv_epi8(hi12,lo12,_mm256_load_si256((const __m256i*)choose_min[12]));
  __m256i p13=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
  __m256i lo13=_mm256_min_epu8(v,p13),hi13=_mm256_max_epu8(v,p13);
  v=_mm256_blendv_epi8(hi13,lo13,_mm256_load_si256((const __m256i*)choose_min[13]));
  __m256i p14=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
  __m256i lo14=_mm256_min_epu8(v,p14),hi14=_mm256_max_epu8(v,p14);
  v=_mm256_blendv_epi8(hi14,lo14,_mm256_load_si256((const __m256i*)choose_min[14]));
  return v;
}
}
using s2_net::sort32_byte;
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;
}
[[gnu::always_inline]] inline void transpose8(const Vec256 *x, Byte *out) {
Vec256 a[8], b[8];
#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));
}
}
[[gnu::always_inline]] inline void sort16_columns(const Byte *src, Byte *out, Byte *out2) {
Vec256 x[16];
repeat<16>([&](auto j) __attribute__((always_inline)) {
x[j] = _mm256_load_si256((const Vec256 *)(src + 256 * j));
});
#define CMP16(A,B) { Vec256 lo = _mm256_min_epu8(x[A], x[B]); \
x[B] = _mm256_max_epu8(x[A], x[B]); x[A] = lo; }
CMP16(0, 13)
CMP16(1, 12)
CMP16(2, 15)
CMP16(3, 14)
CMP16(4, 8)
CMP16(5, 6)
CMP16(7, 11)
CMP16(9, 10)
CMP16(0, 5)
CMP16(1, 7)
CMP16(2, 9)
CMP16(3, 4)
CMP16(6, 13)
CMP16(8, 14)
CMP16(10, 15)
CMP16(11, 12)
CMP16(0, 1)
CMP16(2, 3)
CMP16(4, 5)
CMP16(6, 8)
CMP16(7, 9)
CMP16(10, 11)
CMP16(12, 13)
CMP16(14, 15)
CMP16(0, 2)
CMP16(1, 3)
CMP16(4, 10)
CMP16(5, 11)
CMP16(6, 7)
CMP16(8, 9)
CMP16(12, 14)
CMP16(13, 15)
CMP16(1, 2)
CMP16(3, 12)
CMP16(4, 6)
CMP16(5, 7)
CMP16(8, 10)
CMP16(9, 11)
CMP16(13, 14)
CMP16(1, 4)
CMP16(2, 6)
CMP16(5, 8)
CMP16(7, 10)
CMP16(9, 13)
CMP16(11, 14)
CMP16(2, 4)
CMP16(3, 6)
CMP16(9, 12)
CMP16(11, 13)
CMP16(3, 5)
CMP16(6, 8)
CMP16(7, 9)
CMP16(10, 12)
CMP16(3, 4)
CMP16(5, 6)
CMP16(7, 8)
CMP16(9, 10)
CMP16(11, 12)
CMP16(6, 7)
CMP16(8, 9)
#undef CMP16
transpose8(x, out);
transpose8(x + 8, out2);
}
[[gnu::always_inline]] inline U32 restore_counts(U32 *count, U32 *exceptional) {
U32 *end = count + 256; U32 over;
const Vec256 limit16 = _mm256_set1_epi32(16), 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 %[limit16], %%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), [limit16] "x"(limit16), [limit32] "x"(limit32)
: "rax", "ymm0", "ymm1", "ymm2", "ymm3", "ymm4", "cc", "memory");
return over;
}
[[gnu::always_inline]] inline U32 *emit32_buckets16(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 8*\\lane(%[second]), %%ymm2\n\t"
"vpor %[prefix], %%ymm1, %%ymm1; vpor %[prefix], %%ymm2, %%ymm2\n\t"
"vmovdqu %%ymm1, (%[dst]); vmovdqu %%ymm2, 32(%[dst])\n\t"
"leaq (%[dst],%%rax,4), %[dst]\n\t"
"vpaddd %[step], %[prefix], %[prefix]\n\t"
".endr\n\t"
"addq $64, %[first]; addq $64, %[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;
}
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];
/* [MSET32] 哨兵行填充 4096 B 由 `std::memset` 改成 128 条显式 32B `vmovdqa`。
   判题机 gcc 9.3 对已知长度的 memset 走 `rep stosq`；把「128 条 32B 存储」写成普通循环
   它也会折叠回 rep stosq（1001 已实测），故这里用 `asm volatile` 强制保持独立存储。
   每叶一次 x 65536 叶 = 268 MB 的填充。 */
{
  const __m256i sent = _mm256_set1_epi8((char)255);
  #pragma GCC unroll 128
  for (unsigned q = 0; q < 16u * kRadix; q += 32)
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(__m256i *)(columns + q)) : "x"(sent));
}
for (U32 i = 0; i < 256; ++i) count[i] = i;
/* [B1Q] 4 元素/次 64 位取数：`src` 是 u16 顺序流，原形态每元素 1 条 16 位 load +
   mov/movzbl 两条取高字节；本形态一次 64 位 load 出 4 个元素，高字节用移位直接取。
   本机隔离微基准（work/b1v_mb1.cpp，全 L1/L2 驻留、min-of-7）：2.116 -> 1.956 cyc/元素（-7.6%）。
   稳定性：桶内元素写入顺序与逐元素版逐位相同（同一次 load 的 4 个元素按低到高处理）⇒ 输出逐位不变。 */
{
U32 i = 0;
#pragma GCC unroll 16
for (; i + 4 <= n; i += 4) {
U64 q; std::memcpy(&q, src + i, 8);
U32 s;
s = count[(U32)(q >> 8) & 0xff];  count[(U32)(q >> 8) & 0xff] = s + 256;  columns[s] = (Byte)q;
s = count[(U32)(q >> 24) & 0xff]; count[(U32)(q >> 24) & 0xff] = s + 256; columns[s] = (Byte)(q >> 16);
s = count[(U32)(q >> 40) & 0xff]; count[(U32)(q >> 40) & 0xff] = s + 256; columns[s] = (Byte)(q >> 32);
s = count[(U32)(q >> 56) & 0xff]; count[(U32)(q >> 56) & 0xff] = s + 256; columns[s] = (Byte)(q >> 48);
}
#pragma GCC unroll 16
for (; 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);
const Vec256 idx = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
for (U32 block = 0; block < 256; block += 32) {
alignas(32) Byte first[256], second[256];
#pragma GCC unroll 16
for(unsigned pf=0;pf<16;++pf)asm volatile("prefetchw %0"::"m"(*(const char*)((uintptr_t)dst+2048+64*pf)));
sort16_columns(columns + block, first, second);
Vec256 prefix = _mm256_set1_epi32(base | (block << 8));
if (exceptional[block >> 5] == 0 && end - dst >= 512) {
dst = emit32_buckets16(first, second, count + block, dst, prefix);
continue;
}
for (U32 i = 0; i < 32; ++i) {
U32 h = block + i, c = count[h];
if (__builtin_expect(c <= 16, 1)) {
Vec256 w0 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_loadl_epi64((const Vec128 *)(first + 8 * i))), prefix);
Vec256 w1 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_loadl_epi64((const Vec128 *)(second + 8 * i))), prefix);
if (__builtin_expect(end - dst >= 16, 1)) {
_mm256_storeu_si256((Vec256 *)dst, w0);
_mm256_storeu_si256((Vec256 *)(dst + 8), w1);
} else {
_mm256_maskstore_epi32((int *)dst, _mm256_cmpgt_epi32(_mm256_set1_epi32((int)(c < 8u ? c : 8u)), idx), w0);
_mm256_maskstore_epi32((int *)(dst + 8), _mm256_cmpgt_epi32(_mm256_set1_epi32((int)(c > 8u ? c - 8u : 0u)), idx), w1);
}
} else {
Byte copy[32];
for (U32 j = 0; j < c; ++j) copy[j] = columns[256 * j + h];
// ---- replaces std::sort(copy, copy+c) for c in [17,32] -------------------
// LSD radix, 2 x 4-bit passes on a BYTE key: branchless, no mispredicts.
// Same result as std::sort; saves ~0.75% of the whole run (58662 calls/run,
// each ~1000 cycles as an introsort of 25 bytes vs ~200 here).
// s2_: SIMD 32-byte sorting network (ported from the rival's #106157, which took it from
// our own #104352).  Pad the c real bytes with 255 so the ascending 32-byte sort places them
// first, then the existing consumer reads copy[0..c-1].  Equivalent by construction; the
// network itself was verified standalone (work/s2_nettest.cpp, 200k random inputs, 0 mismatch).
for (U32 j = c; j < 32u; ++j) copy[j] = 255u;
Vec256 sorted = sort32_byte(_mm256_loadu_si256((const __m256i *)copy));
if (__builtin_expect(end - dst >= (c <= 24u ? 24u : 32u), 1)) {
  Vec128 vlo = _mm256_castsi256_si128(sorted), vhi = _mm256_extracti128_si256(sorted, 1);
  Vec256 x0 = _mm256_or_si256(_mm256_cvtepu8_epi32(vlo), prefix);
  Vec256 x1 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_srli_si128(vlo, 8)), prefix);
  Vec256 x2 = _mm256_or_si256(_mm256_cvtepu8_epi32(vhi), prefix);
  _mm256_storeu_si256((Vec256 *)(dst + 0), x0);
  _mm256_storeu_si256((Vec256 *)(dst + 8), x1);
  _mm256_storeu_si256((Vec256 *)(dst + 16), x2);
  if (__builtin_expect(c > 24u, 0)) {
    Vec256 x3 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_srli_si128(vhi, 8)), prefix);
    _mm256_storeu_si256((Vec256 *)(dst + 24), x3);
  }
} else {
  _mm256_storeu_si256((__m256i *)copy, sorted);
  for (U32 j = 0; j < c; ++j) dst[j] = base | (h << 8) | copy[j];
}
// ---- (end) ---------------------------------------------------------------
}
dst += c;
prefix = _mm256_add_epi32(prefix, _mm256_set1_epi32(256));
}
}
}
}
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 mu=(n+255)/256;unsigned need=mu+(unsigned)(6.5*__builtin_sqrt((double)mu)+0.5)+8;unsigned odd=(need+31)/32;if(!(odd&1))odd++;unsigned cap=32u*odd;
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;
const unsigned char *r=s;const unsigned char *rend=s+3u*n;
while(r+192<=rend){
__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);
#pragma GCC unroll 16
for(unsigned j=0;j<64;++j,r+=3){
unsigned k=r[2];uint16_t value;memcpy(&value,r,2);
middle[mp[k]++]=value;
}
}
for(;r<rend;r+=3){
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;
}
void sort(unsigned *a,int n){
{ static int done=0; if(!done){ done=1; syscall(28,(void*)workspace,sizeof(workspace),23);
  syscall(28,(void*)middle,sizeof(middle),14); } }
if(n<256){std::sort(a,a+n);return;}
unsigned capacity=(((unsigned(n)+K-1)/K*17/16+BS-1)&~(BS-1))+BS;
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;
}
}

评测结果