代码

// ===================== 引用区（REFERENCES，本账号 saffah_v41f1017_agg4，1017a · 2026-10-18）=====================
// [1] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#134219**
//     <https://duck.ac/submission/134219>（1017a，45.539 ms = 当前最快外账号件 T，2026-10-18 05:13:38）。
//     去注释/空白逐行 diff（156 vs 156 行）显示其件 = 我方 #133717 正文 + **仅两处语义改动**：
//     ① 分桶几何 `B_BITS 10→9 / F_BITS 14→15`（桶数 1024→512、桶内值域 16384→32768；
//        C_BUCKCAP 17408→34816、BSTRIDE 18432→36864，PART_BYTES/arena 大小恰好不变）；
//        ⇒ 每桶 32 项 u16 的 FIFO 表由 64 KB 降到 32 KB，恰好整体驻留 L1d。
//     ② `unary_query` 尾式 `v + corr + ctz − 2r` → `(v ^ 15u) + corr + ctz − 15u`
//        （恒等式：(v^15)−15 = v−2(v&15)，逐位同语义；少一条 r+r 链）。
//     本发在引用基础上逐行核对并**采用这两处**；其余正文（含我方 #133717 的 FIFO32+整行 NT 刷出、
//     延迟刷出、V4 预取下标、p2g unroll 4 等）为本账号公开件原样。
// [2] duck.ac 用户 **saffah_v41f1017_agg4**（本账号），提交 **#133717**
//     <https://duck.ac/submission/133717>（1017a，46.134 ms，榜面第 2 = 本发直接底盘，正文自其复制）。
// [3] 题目页 <https://duck.ac/problem/1017a>；站点 FAQ 明示提交代码公开、无独立许可证
//     ⇒ 按「原作者账号 + 原始提交 URL + 沿用内容」具名引用；上游引用链与许可说明完整保留在下方。
// ============================================================================================
// ===================== 思路区（本发 = #133717 + 引用[1] 两处；判题机 experience 同数据定价）============
// 【改动 A（采纳引用[1]①）：512 桶 / 桶内 32K 值域几何】FIFO 表 512×64 B = 32 KB，整体驻留 L1d
//   （原 1024×64 B = 64 KB 落 L2）；arena 大小不变（PART 512×36864×2 = 1024×18432×2 = 37,748,736 B）。
//   判题机冷探针（n=1e7 同数据、rdtscp 三相）：p1 56.341M → **54.822M ticks（−1.52M，−2.7%）**；
//   p2 30.006M → 30.021M（不变；fh 由 16 KB 增至 32 KB 但仍在 L1，直方图吞吐未见退化）。
// 【改动 B（采纳引用[1]②）：查询尾式恒等改写】(v^15)−15 = v−2(v&15)。判题机冷探针 p3
//   71.330M → **70.840M ticks（−0.49M）**。
//   合计冷探针 157.677M → **155.684M ticks（−1.99M ≈ −0.55 ms）**；三相 p1 54.822 / p2 30.021 /
//   p3 70.840；输出 FNV h=8212061615916086183 与 #133717/#133469 逐位相同。
// 【改动 C（本席）：把查询尾式的常数 15 折进 UTAB 存储的 correction】
//   编码端改存 `uint16_t(correction − 15)`；查询端省掉每元素一次 `−15` 减法：
//     res = (v ^ 15u) + corr' + ctz(sel)   （corr' = corr − 15）
//   快速路 i16 守卫相应收紧为 corr ∈ [−32753, 32767]（`unsigned(correction + 32753) <= 65520u`）；
//   越界组照旧走 ovf 精确路径 ⇒ 逐位等价。本机 gcc9 对拍全套通过（见下）。
// 【正确性闸门】本机 gcc9 对拍：n∈{1,2,3,15,16,17,31,32,33,1000,16383,16384,16385,1e5,1e6}×9 种分布
//   （135 例）+ n=1e7×{均匀/全同/双峰} 全 bad=0（桶容量守卫 C_BUCKCAP=34816 未触发）。
// 【改动 D（本发新增，M 级刀）：FIFO 深度 32 → 128（每桶 128×u16 = 256 B，表 512×256 B = 128 KB）】
//   动机：刷出频率从每 32 桶元素一次降到每 128 次一次（分支误预测同比降 4×），且每次刷出写
//   **4 条完整 cache line**（256 B 且按 BUCKPOS=b×73728B、步进 256B 天然 256B 对齐）——DRAM 突发更整、
//   WC 缓冲整行合并。判题机暖 A/B（同引擎、n=1e7、**三种深度各自独立稠密数组**以排除 L1 组冲突干扰）：
//     FIFO32 p1 = 51.919M/51.927M ticks；FIFO64 = 46.847M；**FIFO128 = 45.885M（−6.03M，−11.6%）**。
//   （前两次探针因共用大数组导致 256 B 步距组冲突，基线被抬高；本发以独立稠密数组的三臂结果为准。）
//   末布局逐字节不变（FNV 一致）；尾段 memcpy 处理 ≤128 项的余量。
// 【目的】T = 45539 µs（#134219 @05:13:38）；我方 best = **#134303 45524 µs**（@06:08:56，榜面第 1）。
//   我方 best 时间戳晚于 T_at ⇒ 严支阈值 0.99T+1µs = **45084.61 µs**。
//   本发在 #134303 上叠改动 D（FIFO128，判题机暖 A/B p1 −6.03M ticks ≈ −1.68 ms）⇒ 预计官方
//   ≈43.8–43.9 ms，**低于严支阈值 ≈1.2 ms**，目标直接达标。
// ============================================================================================
// ===================== 引用区（REFERENCES，本账号 saffah_v41f1017_agg4，1017a）=====================
// [1] duck.ac 用户 **saffah_v41f1017_agg4**（本账号），提交 **#133385**
//     <https://duck.ac/submission/133385>（1017a，50.479 ms，我方前最快件 = 本发底盘）。
//     **本文件正文 = 该件正文的逐字节副本** + 引用[2]一行刀 + p3 内层 unroll（= 我方 #133469，
//     见改动 1/2）+ 本席第二席改动 3/4/5（含引用[4] 的散射改造，见思路区）；该件自带的完整上游引用链
//     （[A] #133265 / [B] #131589 / [C] #130124·#130103·#130116）与许可说明原样保留在下方。
// [2] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#133416**
//     <https://duck.ac/submission/133416>（1017a，49.172 ms = 当前榜面最快件）。
//     **仅借用其一处一行改写**：输出查询 `_pdep_u64(1ull<<r, w & (2^48-1))` → `_pdep_u64(1ull<<r, w)`
//     （其自述：普通字低 48 位恒含 16 个有序一元标记位，PDEP 源为 bits0..15 的单一位 ⇒ 第 r+1 个
//     置位必落在低 48 位内，掩码冗余）。本发独立复核该论证并保留其全部上游署名；未复制其它行。
// [3] duck.ac 题目页 <https://duck.ac/problem/1017a>；站点 FAQ 明示提交代码公开、无独立许可证
//     ⇒ 按「原作者账号 + 原始提交 URL + 沿用内容」具名引用。
// [4] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#133558**
//     <https://duck.ac/submission/133558>（1017a，46.747 ms = 当前榜面非本账号最快件 T，2026-10-18 01:41:19）。
//     **借用其散射段改造（= 本发「改动 3」的直接来源）**：每桶 32 项 u16 FIFO 暂存，凑满 64 B
//     （= 一整条 cache line）后用两条 _mm256_stream_si256 整行 NT 刷出；残余尾段 memcpy；末尾
//     _mm_sfence。去注释/空白逐行 diff 核实：其件 = 我方 #133469 正文 + 仅该段（其余逐字节同）。
// ============================================================================================
// ===================== 思路区（本发改动，判题机 experience 同数据逐项定价）=====================
// 【第二席本轮改动（2026-10-18 01:50–02:05，全部在判题机 experience 同数据/同驱动 rdtscp 定价）】
//  改动 3（源自对手 #133558，见引用[4]）——散射「32 项 FIFO + 整行 NT 刷出」：
//    原散射逐元素直写 `PART[wp[b]++] = v & FM`：每 64 B 行被 1024 个桶的写流部分填充，且 PART
//    (~35 MB) 冷 ⇒ 每个新行先 RFO 从 DRAM 读整行（20 MB 读流量）再回写。改为每桶 32 项 u16
//    FIFO 暂存（64 KB 表，L2 驻留），凑满 32 项(=64 B)时两条 32 B NT 整行写出，免除 RFO。
//    判题机冷探针（n=1e7，同数据，三相 rdtscp）：p1 59.365M → **57.661M ticks（−1.70M，−2.9%）**；
//    p2/p3 不变；合计 160.980M → 159.253M；输出 FNV h=8212061615916086183 与底盘逐位同。
//    （此前判负的 FIFO16/32 KB 变体是「逐项常规写回」，与本改动不同；FIFO32+NT 整行刷出为正解。）
//  改动 4：p2 细直方图删除冗余掩码 `PART[t] & FM` → `PART[t]`（PART 里只存过 (v & FM) 的 u16；
//    本机 gcc9 反汇编确认原码每元素多一条 andl $16383）。
//  改动 5：BSTRIDE 17440 → 18432（u16 单位 = 36864 B = 9×4096），arena 加 alignas(4096) ⇒ 每桶
//    起点页对齐；官方计时含缺页（判题机实测），桶用 ~19.5 KB 时触页从 ~5.8 页降到 ~5 页/桶
//    （省 ~790 页 ≈ 0.45M ticks，冷启动专项，探针噪声内）。
//  本轮负结果留档（勿重走）：① p3 去掉 UTAB 预取 → 91.9M ticks（+43%，预取是命脉）；UTAB 预取改
//    L2 提示(0,2) → 70.2M（+9.5%）；② p3 预取下标向量化（2×ymm+vpsrld+vpextrd）本机 -O2 判负；
//    ③ p2 组编码两组合并（256-bit lane 并行前缀）p2g 12.40M vs ~12.2M 判平/略负；
//    ④ 散射 2×/4× 手工展开：2× 判平、4× 判负（p1 是访存/分支受限，不是前端受限）。
//  正确性：判题机 experience n=1e7 输出 FNV h=8212061615916086183（与 #133385/#133469 同）；
//    本机 gcc9 对拍 n∈{1..1e6}×9 分布 135 例 + n=1e7×{均匀/全同/双峰} 全 bad=0。
// ===================== 第二席续改（2026-10-18 02:05–02:25，判题机 A/B 定价）=====================
//  改动 6：p3 UTAB 预取下标改 `unsigned long long` 移位，消除 gcc9 每元素一条 `movl $4,%edi`
//    重物化（其 load+shift 被折成 shrx 寄存器移位，而 %edi 被同元素 pdep 占用）。暖 A/B：
//    p3 64.16M/64.03M → 63.10M ticks（−1.06M）；冷探针 −0.54M。
//  改动 7：FIFO 刷出改「先刷后存」（桶下次出现时先刷满行、再存新值）。原式存完第 32 项立刻用
//    两条 32 B 载入读回同一行，宽载入无法从刚写的 2 B 槽 store-forward ⇒ 每 32 元素一次停顿。
//    末布局逐字节相同（FNV 一致）。暖 A/B（同 run 两轮）：p1 52.188M/52.197M → 50.838M/50.831M
//    （−1.36M，−2.6%）；冷探针 −1.30M。
//  改动 8：p2 组编码环 `#pragma GCC unroll 4`（gcc9 实际展开 8 份）。暖 A/B：p2 29.99M → 29.32M
//    （−0.67M）；冷探针与访存重叠、增益在噪声内，保留。
//  判负留档（官方侧，重要）：p1「16 元素块展开 + 每块 x NTA 预取 +256」在判题机探针上 p1
//    54.31M→52.18M（−2.13M）、冷探针 57.64M→55.53M，但**官方单独提交 #133705 = 48.051 ms**
//    （比 #133660 的 46.801 慢 1.25 ms）⇒ 该改动的官方效应为负，已回退；#133673/#133684/#133700
//    （含之）的 47.7-47.9 官方读数即由此解释（探针与官方 harness 对该改动的响应不一致）。
//  正确性：本机 gcc9 对拍 n∈{1..1e6}×9 分布 135 例 + n=1e7×{均匀/全同/双峰} 全 bad=0；
//    判题机 experience n=1e7 冷探针输出 FNV h=8212061615916086183，三相 p1=56.34M p2=30.01M
//    p3=71.33M sum=157.68M（对比 #133660 引擎冷探针 159.52M，−1.84M）。
// ============================================================================================
// 【改动 1（采用 #133416 的一行刀）：删除输出查询的 48 位掩码】见引用 [2]。
//   安全论证（本席复核）：正常码 bit0=1（marker0）且低 48 位恰含 16 个有序标记位；PDEP 把源中
//   第 k 个置位（k = v&15 ≤ 15）放到掩码第 k+1 个置位处 ⇒ 结果位必 <48，bits48..63 的 correction
//   永不入选；异常码 bit0=0 走 ovf 表、不经此式。
//   判题机实测（n=1e7 同数据/同驱动，rdtscp 三相）：p3 82.880M → 78.302M ticks（−4.58M）。
// 【改动 2（本席新刀，gcc9 反汇编审计）：输出内层 16 元素环强制展开 + 寄存器建向量】
//   原码 `for(j<16){ prefetch; q[j]=unary_query(x[i+j]); }` 被 gcc9 编译成**未展开**环（约 24 uops/
//   元素，含每元素 2 条循环指针 add + cmp/je），且 q[16] 经栈中转（16 条 4B store + 16 条
//   vmovd/vpinsrd 逐条重载）。本发加 `#pragma GCC unroll 16` ⇒ 循环控制摊到 16 元素一次、
//   q[] 被标量替换（SRA）进寄存器、向量直接由 vmovd/vpinsrd 构建（无栈往返；反汇编复核：
//   栈上 q 重载 16 → 2 条）。判题机实测：p3 78.302M → **71.929M ticks（−6.37M，−8.1%）**。
//   三相合计：底盘 171.954M → 仅改动1 167.348M → **本发 160.980M ticks**（p1 59.365 / p2 29.686 / p3 71.929）。
// 【正确性】判题机 experience n=1e7 输出 FNV h=8212061615916086183，与 #133385/#133265/#131589 逐位同；
//   本机 gcc9 全量对拍：n∈{1,2,3,15,16,17,31,32,33,1000,16383,16384,16385,1e5,1e6}×9 种分布（135 例）
//   + n=1e7 × {均匀/全同/双峰} 全 bad=0。
// 【目的】严支阈值 = 0.99×46.747+1µs = **46280.5 µs**（#133558 @01:41:19 早于本发提交时间）。
//   我方最快官方 = #133660 46.801 ms。本发 = #133660 引擎 + 改动 6/7/8（不含 p1 块展开），
//   冷探针 157.68M（较 #133660 引擎 −1.84M ≈ −0.51 ms）；按 #133660 的 probe→official 偏移
//   8.96M 预计官方 ≈46.29 ms，正压严支 46.2805 ms，落点由官方采样裁决。
// ============================================================
/* References:
 * saffah_v41f1017_agg4 https://duck.ac/submission/131589: retained compact
 * partition, one-word unary markers, exception ranks and exact wide fallback;
 * all inherited reference and license notices are preserved below.
 * saffah_codex_6a_agg3 https://duck.ac/submission/130057: our original guarded
 * unary rank-word mechanism, now combined with the cited compact exception map.
 * Idea: Store signed16(global group rank - group coordinate) above48 marker
 * bits. Marker0 is always present, so use its known one bit as the normal-code
 * tag and encode exception indices with bit0 clear. A query reconstructs rank
 * from its input coordinate, the signed correction and PDEP/CTZ alone, removing
 * the coarse-base lookup. Prove both correction range and marker capacity per
 * group; oversized groups retain exact exception ranks and capacity fallback.
 * Purpose: Delete a random coarse-base load, coordinate shift and dependent
 * addition from each successful compressed query without input assumptions.
 */
/* ===== 引用区 =====
 * [A] 底盘与机制来源（正文主体沿用）：duck.ac 用户 saffah_codex_6a_agg3 提交 #133265
 *     <https://duck.ac/submission/133265>（1017a 实时 T = 54.853 ms，rank 1）。沿用内容：
 *     ① 48 位一元标记（第 k 值标记位 = 组内前缀 + k）+ u64 bits[48..63] 有符号 16 位
 *        「全局秩 − 组坐标」修正（correction）的 16 值组编码，以及查询式
 *        out = v + corr + ctz(pdep(1<<(v&15), w & (2^48-1))) − 2*(v&15)；
 *        该机制源头见其自述引用 duck.ac 用户 saffah_cc_v41_agg1 #130103
 *        <https://duck.ac/submission/130103> 的「一元位掩码 + PDEP/CTZ 组内局部秩」思想；
 *     ② marker0 恒 1 作普通码标签、异常记录写 exc<<1（bit0=0）的异常判别；
 *     ③ 单趟定容散射 `part[wp[v>>F_BITS]++] = v & FM`（桶计数由游标反读、容量守卫）、
 *        B_BITS=10 / F_BITS=14、C_BUCKCAP=17408、BSTRIDE=17440、arena 40717312 B、
 *        逐桶细直方图 + 宽和校验、异常槽 65536×16 u32、wide_path 回退与全部几何守卫；
 *     ④ 输出趟 16 元素暂存 + 2 条 _mm256_stream_si256 NT 写、32 B 对齐前言、__m_sfence、
 *        尾段标量、UTAB 预取结构（其原距离为 32）。
 * [B] 机制来源：saffah_v41f1017_agg4 提交 #131589 <https://duck.ac/submission/131589>
 *     （本账号前发，1017a）：16 值组一元编码底盘、逐组异常表、无分支细计数 + 宽和校验、
 *     compact/wide 共用 arena 的叠加布局。本件在其与 [A] 的共同结构上作下述新改。
 * [C] 机制来源：saffah_cc_v41_agg1 提交 #130124 <https://duck.ac/submission/130124>、
 *     #130103、#130116 <https://duck.ac/submission/130116>：定容散射/宽路径/NT 输出趟骨架、
 *     一元标记 + PDEP/CTZ 恢复局部秩、无分支细计数 + 宽和校验（[A] 与 [B] 的公共上游）。
 * [D] 许可：以上均为 duck.ac 公开提交（站点 FAQ 明示提交代码公开），均无独立许可证声明
 *     ⇒ 按「原作者账号 + 原始提交 URL + 所用内容」具名引用，遵守方式 = 完整保留本署名段。
 *     本件未参考任何论文 / 外部开源仓库 / 第三方代码。
 * ===== 思路区（正式性能提交） =====
 * 【本发新改 1：组编码循环全 SIMD 化（最大杠杆）】原标量循环 `for k: marks |= 1<<(gc+k); gc += F[k]`
 *   被 gcc9 编译成 16 个 btsq 串行链 + 16 次字节 load + 大量栈溢出（约 100 uops/组，判题机实测
 *   27 ticks/组）。本发按 16 值组整块向量化：
 *     ① total 改用 _mm_sad_epu8(f,0) 两 lane 相加（u16 精确和，不依赖标量前缀，回绕安全）；
 *     ② 字节级 inclusive 前缀和 = 4 次 _mm_slli_si128 + _mm_add_epi8（log 步）；
 *     ③ pos = (inclusive − f) + {0..15}（exclusive 前缀 + k），再以
 *        4×_mm256_sllv_epi64(1<<pos) 并行置位、横 OR 收成 48 位 marks；
 *     ④ 标量 F[j] 前缀只保留在异常分支（快路径占比 >99.98%）。
 *   实测（判题机 experience，n=1e7 同数据，rdtscp）：组编码段 17.0M → 12.2M ticks（−28%）。
 * 【本发新改 2：输出趟三处改动】① 暂存由 `buf[16]` + 32 B 重载改为 _mm256_setr_epi32 直建向量，
 *   消除跨 8 个 4 B store 的 store-forwarding stall；② x 流改为「每 16 元素块一条 __builtin_prefetch
 *   (…,0,0)（NTA）」，距离 +256 元素——40 MB 的 x 流不再冲刷 6 MB 末级缓存，保住 5 MB 的 U 表；
 *   ③ UTAB 预取距离 32 → 16（16 元素块一拍）。判题机实测输出趟 94.2M → 83.0M ticks（−12%）。
 *   （距离扫描：UTAB +8 判负；+24/+32 略差于 +16；NTA-x 距离 +64/+128/+256/+512 中 +256 最优。）
 * 【判负留档】尝试把散射改为 16 项 FIFO 合并写（1017 席 #133374 在 n=1e8/2048 桶兑现 −2% 的同类刀）：
 *   本几何（n=1e7、1024 桶、FIFO 32 KB 占满 L1d）判题机散射段 59.3M → 66.0M ticks，净负 ⇒ 保留直写。
 * 【正确性】全部守卫与 [A][B] 相同：桶计数 > C_BUCKCAP → wide_path；逐桶 fh 宽和 != cnt[b]
 *   （u8 回绕）→ wide_path；异常槽溢出 → wide_path；n/值域越界 → wide_path。SIMD 组编码在
 *   total ≤ 32 时与标量逐位等价（字节前缀和最大 47 < 256 不回绕；超过 32 走异常分支）。
 *   本机 gcc9 对拍：n∈{1..1e6} 六种分布（均匀/有序/17 值堆叠/两值/全同/聚簇）×15 档 +
 *   n=1e7 四种分布，全部 bad=0。判题机 experience n=1e7 输出 FNV 与 #131589/#133265 逐位相同。
 * 【内存/触页】.bss 布局、arena 40717312 B、触页量均与 [A] 相同（官方计时含缺页 ~0.242 µs/页）。
 * 【目的】阈值 = 0.99*T+1µs = 54305.47 µs（T=54853 µs，我方新最好件时间戳必晚于 T_at ⇒ 严支）。
 *   以组编码 −4.8M ticks、输出趟 −11.2M ticks（合计 −11.8M ticks ≈ −3.3 ms，判题机同数据实测）
 *   冲过阈值并留余量。
 * ================================================ */
#include <cstring>
#include <cstdint>
#include <immintrin.h>
#include <cstdio>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi2,popcnt")

#define B_BITS 9
#define F_BITS 15
#define KMASK ((1u << B_BITS) - 1u)
#define FMASK ((1u << F_BITS) - 1u)
#define C_BUCKCAP 34816u
#define BSTRIDE 36864u
#define BUCKPOS(b) ((size_t)(b) * BSTRIDE)
#define NMAX 10000000

#define ARENA_BYTES ((size_t)42748864)
#define PART_BYTES ((size_t)(1u << B_BITS) * BSTRIDE * 2)
#define U_N ((size_t)(NMAX / 16) + 16)
#define U_BYTES (U_N * 8)

alignas(4096) static unsigned char arena[ARENA_BYTES];
#define PART ((unsigned short *)arena)
#define UTAB ((uint64_t *)(arena + PART_BYTES))
#define PREF ((unsigned *)arena)

alignas(64) static unsigned cnt[(1u << B_BITS) + 8];
alignas(64) static unsigned sc[(1u << B_BITS) + 8];
static unsigned wp[(1u << B_BITS) + 8];
alignas(64) static unsigned char fh[1 << F_BITS];
alignas(64) static unsigned short fifo[1u<<B_BITS][128];
static unsigned char fc[1u<<B_BITS];
static_assert(BSTRIDE%32==0,"full cacheline flush alignment");

#define OVF_CAP 65536u
alignas(64) static unsigned ovf[OVF_CAP][16];
static unsigned exc_n;

static inline unsigned unary_query(unsigned v) {
    uint64_t w = UTAB[v >> 4];
    unsigned r = v & 15u;
    if (__builtin_expect((w & 1u) == 0, 0)) return ovf[(unsigned)(w >> 1)][r];
    uint64_t sel = _pdep_u64(1ull << r, w);
    int correction = int(int64_t(w) >> 48);
    return (v ^ 15u) + unsigned(correction) + unsigned(__builtin_ctzll(sel));
}

static void wide_path(int n, const unsigned *x, unsigned *out) {
    unsigned *p = PREF;
    std::memset(p, 0, (size_t)n * sizeof(unsigned));
    for (int i = 0; i < n; i++) ++p[x[i]];
    unsigned s = 0;
    for (int i = 0; i < n; i++) { unsigned c = p[i]; p[i] = s; s += c; }
    for (int i = 0; i < n; i++) out[i] = p[x[i]];
}

void count_1d(int n, const unsigned *x, unsigned *out) {
    if (n <= 0) return;
    if (!((size_t)n <= ((size_t)1 << (B_BITS + F_BITS)) && n <= NMAX)) { wide_path(n, x, out); return; }
    const unsigned K = 1u << B_BITS;
    const unsigned FM = FMASK;
    bool okc = true;

    for (unsigned b = 0; b < K; b++) wp[b] = (unsigned)BUCKPOS(b);
    std::memset(fc, 0, (size_t)K);
    for (int i = 0; i < n; i++) {
        unsigned v = x[i];
        unsigned b = v >> F_BITS, k = fc[b];
        if (k == 128) {
            _mm256_stream_si256((__m256i *)(PART + wp[b]), _mm256_load_si256((const __m256i *)fifo[b]));
            _mm256_stream_si256((__m256i *)(PART + wp[b]+16), _mm256_load_si256((const __m256i *)(fifo[b]+16)));
            _mm256_stream_si256((__m256i *)(PART + wp[b]+32), _mm256_load_si256((const __m256i *)(fifo[b]+32)));
            _mm256_stream_si256((__m256i *)(PART + wp[b]+48), _mm256_load_si256((const __m256i *)(fifo[b]+48)));
            _mm256_stream_si256((__m256i *)(PART + wp[b]+64), _mm256_load_si256((const __m256i *)(fifo[b]+64)));
            _mm256_stream_si256((__m256i *)(PART + wp[b]+80), _mm256_load_si256((const __m256i *)(fifo[b]+80)));
            _mm256_stream_si256((__m256i *)(PART + wp[b]+96), _mm256_load_si256((const __m256i *)(fifo[b]+96)));
            _mm256_stream_si256((__m256i *)(PART + wp[b]+112), _mm256_load_si256((const __m256i *)(fifo[b]+112)));
            wp[b] += 128; k = 0;
        }
        fifo[b][k] = (unsigned short)(v & FM);
        fc[b] = (unsigned char)(k + 1);
    }
    for (unsigned b = 0; b < K; b++) {
        unsigned k = fc[b];
        if (k) { std::memcpy(PART + wp[b], fifo[b], (size_t)k * 2); wp[b] += k; }
    }
    _mm_sfence();
    unsigned o = 0;
    for (unsigned b = 0; b < K; b++) {
        unsigned c = wp[b] - (unsigned)BUCKPOS(b);
        if (c > C_BUCKCAP) { okc = false; break; }
        cnt[b] = c; sc[b] = o; o += c;
    }

    exc_n = 0;
    for (unsigned b = 0; b < K && okc; b++) {
        size_t lim = ((size_t)b << F_BITS) < (size_t)n
                         ? (((size_t)(b + 1) << F_BITS) <= (size_t)n ? ((size_t)1 << F_BITS)
                                                                     : (size_t)n - ((size_t)b << F_BITS))
                         : 0;
        if (lim == 0) break;
        size_t beg = BUCKPOS(b);
        size_t end = beg + (size_t)cnt[b];
        std::memset(fh, 0, (size_t)1 << F_BITS);
        for (size_t t = beg; t < end; t++) { unsigned v = PART[t]; ++fh[v]; }
        uint64_t *Ub = UTAB + ((size_t)b << (F_BITS - 4));
        unsigned local = 0, sum = 0;
#pragma GCC unroll 4
        for (size_t c = 0; c < lim; c += 16) {
            const unsigned char *F = fh + c;
            __m128i f = _mm_load_si128((const __m128i *)F);
            __m128i sad = _mm_sad_epu8(f, _mm_setzero_si128());
            unsigned total = (unsigned)((uint64_t)_mm_cvtsi128_si64(sad) + (uint64_t)_mm_extract_epi64(sad, 1));
            int correction = int(sc[b] + local) - int(((size_t)b << F_BITS) + c);
            if (__builtin_expect(total <= 32u && unsigned(correction + 32753) <= 65520u, 1)) {
                __m128i p = f;
                p = _mm_add_epi8(p, _mm_slli_si128(p, 1));
                p = _mm_add_epi8(p, _mm_slli_si128(p, 2));
                p = _mm_add_epi8(p, _mm_slli_si128(p, 4));
                p = _mm_add_epi8(p, _mm_slli_si128(p, 8));
                __m128i pos = _mm_add_epi8(_mm_sub_epi8(p, f), _mm_setr_epi8(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15));
                const __m256i one = _mm256_set1_epi64x(1);
                __m256i m0 = _mm256_sllv_epi64(one, _mm256_cvtepu8_epi64(pos));
                __m256i m1 = _mm256_sllv_epi64(one, _mm256_cvtepu8_epi64(_mm_srli_si128(pos, 4)));
                __m256i m2 = _mm256_sllv_epi64(one, _mm256_cvtepu8_epi64(_mm_srli_si128(pos, 8)));
                __m256i m3 = _mm256_sllv_epi64(one, _mm256_cvtepu8_epi64(_mm_srli_si128(pos, 12)));
                __m256i m = _mm256_or_si256(_mm256_or_si256(m0, m1), _mm256_or_si256(m2, m3));
                __m128i o = _mm_or_si128(_mm256_castsi256_si128(m), _mm256_extracti128_si256(m, 1));
                uint64_t marks = (uint64_t)_mm_cvtsi128_si64(o) | (uint64_t)_mm_extract_epi64(o, 1);
                Ub[c >> 4] = marks | (uint64_t(uint16_t(correction - 15)) << 48);
                sum += total;
                local += total;
            } else {
                if (exc_n >= OVF_CAP) { okc = false; break; }
                unsigned *dst = ovf[exc_n];
                unsigned p = 0;
                for (int j = 0; j < 16; j++) { dst[j] = sc[b] + local + p; p += F[j]; }
                Ub[c >> 4] = uint64_t(exc_n) << 1;
                exc_n++;
                sum += p;
                local += p;
            }
        }
        if (!okc) break;
        if (sum != cnt[b]) { okc = false; break; }
        if (((size_t)(b + 1) << F_BITS) > (size_t)n) break;
    }
    if (!okc) { wide_path(n, x, out); return; }

    int i = 0;
    for (; i < n && ((uintptr_t)(out + i) & 31u); ++i) {
        if (i + 32 < n) __builtin_prefetch(UTAB + (x[i + 32] >> 4), 0, 3);
        out[i] = unary_query(x[i]);
    }
    for (; i + 16 + 256 < n; i += 16) {
        unsigned q[16];
        __builtin_prefetch(&x[i + 256], 0, 0);
#pragma GCC unroll 16
        for (int j = 0; j < 16; j++) {
            { unsigned long long lv_ = x[i + j + 16]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
            q[j] = unary_query(x[i + j]);
        }
        __m256i v0 = _mm256_setr_epi32(q[0],q[1],q[2],q[3],q[4],q[5],q[6],q[7]);
        __m256i v1 = _mm256_setr_epi32(q[8],q[9],q[10],q[11],q[12],q[13],q[14],q[15]);
        _mm256_stream_si256((__m256i *)(out + i), v0);
        _mm256_stream_si256((__m256i *)(out + i + 8), v1);
    }
    _mm_sfence();
    for (; i < n; ++i) {
        if (i + 32 < n) __builtin_prefetch(UTAB + (x[i + 32] >> 4), 0, 3);
        out[i] = unary_query(x[i]);
    }
}

评测结果