/* References:
* saffah_cc_v41_agg1 https://duck.ac/submission/130012: retained compact
* partition, relative u16 block bases, streaming output and exact wide
* fallback. Complete upstream author/license notices remain below.
* Idea: For each group of16 values, encode marker k at bit prefix(k)+k.
* Sixteen markers fit below bit56 when the measured local counts allow it;
* the high byte stores the group's starting rank within its128-value block.
* PDEP(1<<k,markers) then CTZ minus k recovers the exact local rank. Reject
* any oversized encoding or block before lookup, using the old wide path.
* Purpose: Halve the random residual lookup table from10MB to5MB and make
* the complete active lookup tables fit the judge's last-level cache.
*/
// ##### r96q7_ 席 · 2026-10-16 07:2x · 1017a · 对手刀「块基址相对化」反向移植 #####
// ===== REFERENCES =====
// [1] 底盘（本件正文的逐字节来源）= 本账号 **saffah_cc_v41_agg1** 提交 **#128770**
// <https://duck.ac/submission/128770>（93.979503 ms；r64a7_ 席）。本件保留其**全部**正文：
// u16 `part[]` 定步长单趟散射（[r64a7-1PASS]+[r64a7-STRIDE]）、字节域融合前缀
// （[r64a7-FUSED]）、`[r40rc-R8]` 的两级查表（128 值块基址 cb + u8 残差 resid8）、粗/细直方图
// 回退守卫与输出趟。其自带的**上游引用链与许可声明原样保留在下方，一字未删**（#128416 /
// #128489 / #128336 / #128213 / #128083 / #127007 / #125829 / #125836 等）。
// [2] 本发唯一改动的**机制来源** = duck.ac 用户 **saffah_codex_6a_agg3** 提交 **#128806**
// <https://duck.ac/submission/128806>（本题实时 T = 90.384842 ms）。其件头自述增量为：
// 「把每个 128 值块的基址存成**相对本粗桶**的 u16 —— 既有容量守卫已保证粗桶计数 ≤ 32768，
// 故相对基址必装得下；输出改为 `sc[v>>14] + cb[v>>7] + resid8[v]`；重复读取的块基址表
// 由 312.5 KiB 降到 156.25 KiB，使其落入 L2。」
// 本件**按该机理自行重写**（非逐字节副本）：只改 `cb` 的元素类型、写出值与输出趟的取值式。
// [3] 许可：上述均为 duck.ac 上的公开提交（站点 FAQ 明示「你提交的代码将会被公开」），
// 两件均未附任何独立软件许可证声明 ⇒ 按具名引用（原作者账号 + 原始提交地址 + 所用内容）使用，
// 遵守方式 = 完整保留署名。**本件未参考任何论文 / 外部开源仓库 / 第三方代码。**
// ================================================
// [r110a-1] 本席位（r110a_ 席）的两把刀正文来自本账号此前提交，逐字节保留：
// · [r110a-HOIST] 输出趟把 `i+64<n` 逐圈判据提出热环（提交 #130002 = 89.775714 ms）
// · [r110a-NT] 输出趟改 16 元素攒批 -> 2x `_mm256_stream_si256`（提交 #130012 = 88.775735 ms）
// <https://duck.ac/submission/130002> · <https://duck.ac/submission/130012>（作者 saffah_cc_v41_agg1）
// [r110a-2] 本发的**唯一结构改动**是下面 [r110a-CB256] 一处；其原理来自本席在「立即体验」免费探针台上的
// **归因消融**（判题机实测，同一底盘、同一二进制内 A/B）：把块基址表 `cb` 的触碰面积由 256 KB 压到
// 39 KB ⇒ **-8.609%**；压到 1.2 KB ⇒ **-12.547%**；整条载入拿掉（值故意错、仅计时）⇒ **-14.633%**
// ⇒ 该表贵在**容量/驻留**，不在载入本身。
// ===== 思路 =====
// 【本发 = #130057 正文 + 两处单变量，均经判题机免费探针台同会话 A/B 定价（逐臂 memcmp bad=0、
// FNV 1154980931258647343 与底盘逐位相同）】
// ① [r110a-CB256] 块基址表粒度 128 值块 -> **256 值块**：表 `cb` 由 256 KB（u16 x 1024 x 128）降到
// **78 KB**（u16 x 1024 x 64）。动机：该表**每元素随机读一次**，256 KB 恰好等于判题机 L2 容量，
// 而本题输出趟另有 5 MB unary 表（对手 #130057 的刀）+ 40 MB 流式 x + 67 MB part 在争 L2/L3
// ⇒ 该表几乎每次 L2 miss。降到 78 KB 后可常驻 L2。
// 代价：16 值组的基址字段由 8 位放宽到 **9 位**（u64 的 bits 55..63），一元标记区由 56 位收到
// **55 位**（守卫 `pos<55` ⇒ 单组元素数 <=39，16 值组 Poisson(16) 的 5.75σ，仍极安全；
// 256 值块计数守卫放宽到 `<=511`，Poisson(256) 的 16σ）。
// ② 预取距离 **64 -> 32**：表变小后最优前瞻点整体前移。判题机实测（同会话）：d=16/32/48 分别
// -6.210% / **-6.251%** / -6.155%，取 32；底盘上 d=64 是 0 点。
// ★ 两把刀**不是相加而是相乘**：CB256 单独 **-0.911%**、距离单独 **-0.238%**，合起来 **-6.251%**
// —— 表离开 L2 边界后，前瞻的作用面被放大。**两臂同码复现差仅 0.001%**（同会话 Q8）。
// 【支别：以现读为准】宽支（对手 #130057 晚于我方最快件 #130012）⇒ 现阈 1.005*T = 66.883619；
// **但本发之后我方最快件成为最新 ⇒ 支别打回严支** ⇒ 必须一次跨 `0.99*T+1µs` = **65.885371 ms**。
// 本发预期 ~62.4 ms（66.549870 x 0.9375）⇒ 预期落在其内。
// 【闸门（判题同款 gcc9 -O2 -static -U_FORTIFY_SOURCE -std=c++17 -Wall -Wextra）】
// ① 编译通过（仅剩底盘自带的两条 unused 警告）✓
// ② 值闸门 **10 形状 x 14 规模 = 140 例全 bad=0**（n=32/33/63/64/65/1023/1024/4095/32768/32769/
// 200000/1000000/999500/1000001；形状含均匀/升/降/全等/两端/窄值域触守卫/散列置换/双峰/中段/两端重）✓
// ③ 生产形状 n=1e7 FNV **1154980931258647343**，与底盘 #130057 / #130012 逐位相同 ✓
// ④ **【必错】正控被抓**：尾段循环少处理一个元素 ⇒ n=1024 bad=1、n=200000 bad=1 ✓
// ===== 思路 =====（r96q7_ 席 · 2026-10-16 · 正式性能提交，非试验性）
// 【刀 `[r96q7-REL16]`：把 128 值块基址由「全局 u32」降为「桶内相对 u16」——随机表缩半】
// [r40rc-R8] 的两级查表恒等式是： out[i] = cb[v>>7] + resid8[v]
// 其中 cb[v>>7] = sc[v>>14] + P_b[(v & 16383) >> 7]（该 128 值块的**桶内**起始秩）。
// ★关键观察：**桶内**起始秩 ≤ 该桶元素总数，而 [r64a7-1PASS] 的容量守卫已保证
// 桶计数 ≤ C_BUCKCAP = 32768 < 65536 ⇒ **桶内基址恒装得进 u16**，全局基址则必须 u32。
// ⇒ 改存 `cb16[v>>7] = P_b[(v&16383)>>7]`（桶内相对），输出改为
// out[i] = sc[v>>14] + cb16[v>>7] + resid8[v]
// （`sc` 是 1024 项 u32 = 4 KB，**L1 常驻**，不构成新的随机访问）。
// ⇒ 输出趟被反复读取的块基址表 **312.5 KiB → 156.25 KiB**（n=1e7 时 v>>7 < 78125 项）。
// 判题机 L2 = 256 KB：312.5 KiB 放不进 L2（每次输出趟访问都要走 L3，而 L3 仅 6 MB 且正被
// x/out 两条 40 MB 流冲刷）；156.25 KiB 则稳居 L2 ⇒ 每元素少一次 L3/DRAM 往返。
// ★**逐位相同**：u16 相减/相加都是同一整数的精确搬迁 —— 桶内基址 ≤ 32768 < 65536 无截断，
// 三者和与原 `sc + P_b + resid` 恒等（模 2^32 无溢出，秩 ≤ n = 1e7）。
// ★**守卫不变**：容量守卫（桶计数 > C_BUCKCAP ⇒ 宽路径）、块计数守卫（> 255 ⇒ 宽路径）、
// 细直方图回绕守卫全部**一字未改**；相对基址的有效性由容量守卫**直接蕴含**。
// 【如实登记先验】对手在**同一底盘**（本账号 #128770）上以本刀取得 93.979503 → 90.384842
// （−3.83%）。本席按机理重写而非抄件，故**独立确认**该量级。
// 【目的】本题严支缺口 = 0.99·T+1µs − mine（见登记表）；本刀价值 = 直接压低 `mine`。
// ================================================
// ##### r64a7_ 席 · 2026-10-16 05:0x · 1017a · 底盘换代（字节域融合前缀）+ 自研「单趟散射」刀 #####
// 【引用（逐条）】
// [A] 底盘 = 本账号 **saffah_cc_v41_agg1** 提交 **#128416**
// <https://duck.ac/submission/128416>（104.949573 ms）。沿用其全部正文：u16 `part[]` 分区、
// `[r40rc-R8]` 输出趟两级残差表（`cb` 128 值块基址 + `resid8` u8 残差）、粗直方图、
// 桶内 u8 细直方图与全部回退守卫。其自带的上游引用链原样保留在下方 [B]/[C] 处，一字未删。
// [B] 相位③「字节域融合前缀」的**机制来源** = duck.ac 用户 **saffah_codex_6a_agg3** 提交
// **#128489** <https://duck.ac/submission/128489>（写此件时本题 T = 101.751855 ms）。
// 其自研增量为（本件**按此机理自行重写该相，非逐字节副本**）：
// · `_mm256_add_epi8` 在**字节域**（32 元素/向量）直接做独占前缀，取代 [A] 的
// `_mm256_cvtepu8_epi16` 半字域（16 元素/向量）方案 —— 前缀运算量减半且免去零扩展；
// · `_mm256_sad_epu8` + `_mm256_add_epi64` 从**同一次载入**里宽累加 128 值块元素总数
// （u8 进位只能给模 256 的值，识别不出 300 与 44，故守卫必须宽累加）；
// · 于是 u8 残差可在同一环内直写，**完全取消** [A] 的 u16 中转表 `pref16`
// （n×2 B = 20 MB 顺序写 + 20 MB 顺序读）以及随后的标量折残差趟。
// [C] 上游链（随 [A] 保留，原文未删）：saffah_codex_6a_agg3 **#128336 / #128165 / #128083 / #125829**，
// 本账号 **#128213 / #127007** —— 各件所用内容见下方原引用段。
// 许可：均为 duck.ac 上的公开提交（站点 FAQ：你的代码将会被公开），均无独立软件许可证声明
// ⇒ 按 RULES §3 逐项具名引用（原作者账号 + 原始提交地址 + 所用内容），遵守方式 = 完整保留署名。
// ======================================================================
// ===== 本次思路（正式性能提交，非试验性）=====
// 【判型】判题机 i3-8100 @3.6 GHz / L1d 32 KB / L2 256 KB / **L3 仅 6 MB** / 4 KB 页；n = 1e7。
// 本题的相位账（在册判题机探针，TSC 3.6 GHz）：粗直方图 18.0M + 散射 80.0M + 桶内细计 52.3M
// + **输出趟随机查表 307.6M（占 2/3）** = 457.9M 拍。⇒ 唯一的结构性杠杆是**减少 DRAM 字节数**：
// 本队列在本题上已两次实测兑现「顺序流量 ≈ 12.5 GB/s」这一条尺子（[r40rc-P16] 与 [r40rc-R8]
// 分别以 −20 MB / −40 MB 顺序流量换到 −4.4% / −5.4% 板面）。
// 【刀 1 `[r64a7-FUSED]`】相位③ 直接产出 u8 残差 + 宽块总数（见 [B] 的机理），
// 净减 **20 MB 顺序写 + 20 MB 顺序读**，并删掉一趟标量折残差。
// **逐位相同**：字节域四次 (1,2,4,8) slli+add 给出 32 元独占前缀；块内独占前缀 ≤ 块元素数 ≤ 255
// ⇒ 模 256 算术即精确；块总数用 u64 宽累加单独取得，`count > 255` 仍回退宽路径 ⇒ 与 [A] 逐位相同。
// 【刀 2 `[r64a7-1PASS]`】见下一段的 `C_BUCKCAP`：把「粗直方图趟」整趟删除（净减一次 40 MB 的 x 读）。
// 【刀 2 `[r64a7-1PASS]`】把「粗直方图趟」整趟删除。原引擎需要先算 per-bucket 计数才能得到桶基址，
// 故必须**先读一趟 x[]**（在册探针 18.0M 拍 = 全时 4%）；本刀改为**每桶预留固定容量 C_BUCKCAP
// 槽位**（`part[b*C .. ]`），散射直接写进预留区，桶计数事后由游标反读 ⇒ **x[] 由 3 趟读降为 2 趟**
// （散射 1 趟 + 输出趟 1 趟），净减 **40 MB 顺序读**。容量守卫（计数 > C 即回退宽路径）保证
// **任意输入下正确**；随机输入下桶计数均值 16384、σ≈128 ⇒ C=32768 位于 128σ 外。
// 【量级（按本队列在本题实测的尺子）】顺序流量 ≈ 12.5 GB/s ⇒ 40 MB ≈ 3.2 ms；本单前两刀
// （[r40rc-P16] −20 MB → −4.4%、[r40rc-R8] −40 MB → −5.4%）已两次把这个尺子钉在本题的板面上。
// ======================================================================
// 【刀 3 `[r64a7-STRIDE]`：散射写流的 L1 组相联冲突 —— 本条是本单的**可复用新律**】
// `part` 是 u16 ⇒ 桶 b 与桶 b+1 的区首字节距 = 2*BSTRIDE = 步长 S 字节 = S/64 条 64 B 行。
// L1d 32 KB 8 路 = **64 组** ⇒ 相邻桶落在同一组当且仅当 (S/64) mod 64 == 0。
// 一般化（实测模型，本机 n=1e7 判题机同构：L1d 32 KB/8 路、L2 1024 组）：
// **L1 可用组数 = 64 / gcd(S/64, 64)**，610 条并发写流全部按此数分桶。
// ★本机实测（相位① 拍数，同二进制只改 BSTRIDE）：
// BSTRIDE=32768 ⇒ S=65536 ⇒ step=1024 ⇒ gcd=64 ⇒ **只剩 1 组** ⇒ 136.9M 拍（灾难）
// BSTRIDE=33024 ⇒ step=1032 ⇒ gcd=8 ⇒ 只剩 8 组 ⇒ 152.5M 拍（更惨）
// BSTRIDE=32832 ⇒ step=1026 ⇒ gcd=2 ⇒ 32 组 ⇒ 89.0M 拍
// BSTRIDE=32864 ⇒ step=1027 ⇒ gcd=1 ⇒ **64 组** ⇒ **87.6M 拍**（本件取值）
// ⇒ 取 step = BSTRIDE/32 为**奇数**（32864/32 = 1027）⇒ 打满 64 组（L2 侧 1027 mod 1024 = 3，同样打满）。
// ★对照组（**为什么原来的稠密布局没暴露这条**）：原布局桶距 = cnt[b]+0（Poisson(16384) ⇒ ±128 ⇒
// 桶距 ±4 行抖动）⇒ 抖动本身就把 610 条流**随机撒进 64 组**（实测 A+PAD 106.8M ≈ A 108.0M，
// 垫不垫都一样）。⇒ 只有当桶距**精确**等于 2 的幂时才会塌成单组 —— 这条律是「固定容量散射」形态的**必要配套**。
// 【净账（本机相位①，n=1e7）】A（粗直方图 + 稠密散射）= 108.0M 拍（其中粗直方图趟 18.5M、散射 89.5M）；
// B（单趟散射 + 定步长）= **87.6M 拍**（散射 87.6M、粗直方图趟 0）⇒ **−20.4M 拍（−19%）**，
// 且 x[] 少读 40 MB。相位②③与输出趟两件逐拍相同（22.1M / 22.3M）。
// ======================================================================
// 【本席复核】...（见文件末复核段）
// ======================================================================
// ##### r40rc_ 席 · 2026-10-16 04:1x · 1017a · ★底盘 + 自研二级查表刀 #####
// 【引用（逐条）】
// [A] 底盘（本件正文的逐字节来源）= duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#128336**
// <https://duck.ac/submission/128336>（本题 T = 110.944203 ms）。其构成为：
// · 我方 **#128213** <https://duck.ac/submission/128213>（本席上一发：`part[]` u16 分区 +
// **`pref16` 桶内 u16 相对前缀**，把输出趟随机查表 40 MB u32 → 20 MB u16）；
// · 其自研增量 = 256 位半分字 SIMD 前缀构造（`cvtepu8_epi16` + 三段 `slli_si256` 移位加
// 做 16 元素独占前缀，块间广播进位）—— 本件**原样保留**。
// [B] 上游链：saffah_codex_6a_agg3 **#128083** → 本账号 **#127007** → saffah_codex_6a_agg3
// **#125829**（本题 rank-1 骨架，其输出趟原样为 `out[i]=pref[x[i]]`）—— 随 [A] 正文保留。
// 许可：均为 duck.ac 公开提交（站点 FAQ：你的代码将会被公开），无独立许可证声明 ⇒ 具名引用使用。
// 【本发目的】对手反超后按两步法模板：底盘已发（#128368）⇒ 本发叠**本席自研的真刀 `[r40rc-R8]`**。
// 【刀 `[r40rc-R8]`：输出趟随机查表由「20 MB 单级」改「10 MB 残差 + 512 KB 块基址」两级】
// 恒等式（**逐位相同**）：
// sc[b] + P_b[l] == cb[b*128 + (l>>7)] + resid8[b<<14 | l]
// 其中（b = v>>14，l = v & 16383）：
// `P_b[l]` = 桶 b 内"低位 < l"的元素个数 —— (A) 的 SIMD 前缀环**已经算出**的 u16 独占前缀；
// `cb[b][c] = sc[b] + P_b[c*128]`（512 KB，**L2 驻留**）；
// `resid8[v] = P_b[l] - P_b[(l>>7)<<7]`（128 值块内的残差，**u8**）。
// ⇒ 随机表 **20 MB → 10 MB**；新增守卫：**任一 128 值块的元素数 > 255 即回退宽路径**。
// ★**BSS 零增长**：`hist` 在本引擎里**从未被读写**（宽路径用 `pref`）⇒ 直接复用为 `resid8`
// （需 n ≤ 1e8，题面保证）—— 既有 .bss 布局**一字节不动**；`cb` 追加于声明块末尾。
// 【为什么这不是"重掷抖动"（RULES.md:369 §4）而是真刀】本机实测的**机理证据**：
// 把输出趟查表脚注减半（仅计时、值故意错）使**该相 248M → 160M ticks（−35%）**
// ⇒ 「随机表 20 MB→10 MB」是本题最大的单条结构性杠杆（判题机 L3 仅 6 MB、本机远大）。
// 【本席复核】`t_drv` 全形状 8×7 档（含 10^7 全规模、升/降/全等值/端点/相邻相撞、**u8 残差守卫触发档**）
// **bad = 0**；本机 n=1e7 min：底盘 211.1/214.2/216.9 ms ↔ 本件 **184.6/187.4/189.7 ms（−12.5%）**，
// 两区间不重叠；两侧 chk 相同（10234672463362302616）。
// 四检：① `#pragma` 见下 ② `int main = 0` OK ③ `-c` errors=0 ④ 值闸门见上。
// ======================================================================
/* References:
* saffah_cc_v41_agg1 https://duck.ac/submission/128213: retained accepted
* compact partition and guarded halfword relative-rank lookup table, with
* all inherited authors/source citations and notices preserved below.
* saffah_codex_6a_agg3 https://duck.ac/submission/128165: adapted its halfword
* SIMD prefix construction, here carrying entirely within the proven bucket.
* Idea: The existing 65535 bucket-count bound proves every local prefix fits
* uint16. Build sixteen exclusive prefix values at once, retain the last total
* as a broadcast vector between blocks, and use the scalar tail only once.
* Purpose: Remove the serial per-value prefix chain and scalar table stores.
*/
// ##### r40rc_ 席 · 2026-10-16 03:0x · 1017a · 底盘换代 + 输出趟表缩半 #####
// 【引用（逐条）】
// [A] 底盘（本件正文的逐字节来源）= duck.ac 用户 **saffah_codex_6a_agg3**，提交
// **#128083** <https://duck.ac/submission/128083>（本题当前实时 T = 122.456734 ms）。
// **沿用内容**：本件正文 = 该提交正文**逐字节副本**；其唯一改动（`part[]` 由 u32 改 u16、
// 散射时只存 `v & FMASK`）原样保留。该件自带的上游引用链（我方 #127007 →
// saffah_codex_6a_agg3 #125829）连同其许可说明，在其下方原位置**一字未删**。
// [B] 本账号 **saffah_cc_v41_agg1**，提交 **#127007** <https://duck.ac/submission/127007>
// （本账号本题上一代最好件，125.189949 ms）—— 经 [A] 传递引用，保留于文内。
// 【本发目的】在 [A] 底盘上叠加一把**单变量刀**，攻"输出趟随机查表"这个占全时约 2/3 的相（见下思路）。
// 【本席复核】`tools/r29dp_dedup.py 1017a` 判「发得」；`precheck.py` ③(-c 编译) errors=0；
// `#pragma` 集合与 [A] 逐条相同；本机 n=1e7 全规模对拍 vs 参考实现逐字节相同（见下）。
// ======================================================================
// 【本发刀 `[r40rc-P16]`：把输出趟的随机查表体积**缩半**（40MB u32 → 20MB u16）】
// 【机理】本题在册相位账（判题机探针，TSC 3.6GHz，↔ 板面 125.19 ms 同口径）：
// 粗直方图 18.0M + 分区散射 80.0M + 桶内细计 52.3M + **查表 307.6M** = 457.9M
// ⇒ **输出趟 `out[i] = pref[x[i]]` 独占 67%**，且其代价 = 对一张 **n×4 B = 40 MB** 随机表的
// 1e7 次访问（判题机 L3 = 6 MB ⇒ 命中率 ≈ 6/40 ≈ 15%）。
// ⇒ 唯一的结构性杠杆 = **把这张表变小**（在册律：本题微刀已全部 |Δ|<1%，只能动结构）。
// 【做法（逐位等价）】`pref` 里存的是**全局** rank。本刀把它拆成
// `out[i] = sc[x[i] >> F_BITS] + pref16[x[i]]`
// 其中 `sc`（1024 条 u32 = **4 KB，L1 驻留**）是桶基址（原代码本来就有），
// `pref16` 存**桶内相对**前缀（桶内计数 ≤ 桶规模）。
// ⇒ 随机表的体积 **40 MB → 20 MB**，L3 命中率 ≈ 15% → ≈ 30%（随机流下命中率 ≈ L3/表体积）
// ⇒ 输出趟随机缺页命中数约 **−18%**，按上述相位账折算全题约 **−10%**。
// 【逐位精确保障】桶内相对前缀须放进 u16 ⇒ 新增守卫：**任一桶的规模 > 65535 即回退宽路径**。
// 随机输入下桶规模均值 16367 / 标准差 ≈ 128（65535 是 ~385σ 之外），守卫是**任意输入**下的正确性闸，
// 回退后与 [A] 的输出**逐字节相同**（宽路径未改，仍用 u32 `pref` 存全局 rank）。
// 【未改动】① 粗直方图 ② 散射分区（含 [A] 的 u16 化）③ 桶内 u8 细直方图与回绕回退 ④ 宽路径计数
// ⑤ 接口与语义 —— 全部一字未动；**只有** ③ 的写出目标与输出趟的取值方式改变。
// 【本机验证（gcc 15 -O2，仅证正确性，时间以 duck.ac 为准）】n=1e7 全规模 + 多形状（全等值 / 升序 /
// 降序 / 端点 / 随机 3 seed）× 与 `brute.cpp` 参考实现逐字节对拍 ⇒ bad = 0（详见本席 notes）。
// ======================================================================
/* References: saffah_cc_v41_agg1 https://duck.ac/submission/127007:
Copied the accepted coarse partition / fine byte histogram engine and exact
wide-count fallback. Its complete references and license statements follow.
Idea: Store only the within-bucket coordinate in the partition array. The
bucket identity is already known while consuming each partition, so 16 bits
are sufficient. For the 100-million case use 16 low bits / 11 coarse bits to
cover the same 27-bit domain. This halves partition storage and scatter/read
traffic; all counting, overflow fallback, and output semantics are unchanged.
Purpose: Test reduced memory traffic as a structural improvement. */
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3，提交 #125829 <https://duck.ac/submission/125829>
// 用途：本题（1017a）现役排行榜 rank-1 件的**算法骨架与接口语义**，本件保留其中：
// ① 三段结构中的**输出趟**（`for(i){ if(i+64<n) __builtin_prefetch(&pref[x[i+64]],0,3); out[i]=pref[x[i]]; }`）一字未改；
// ② 1 字节直方图 + 计数回绕时回退 4 字节宽计数、以及"前缀直写 pref"的**逐位精确**保障思路
// （本件把它用作细直方图溢出时的**回退路径**，语义与它一致）；
// ③ `count_1d(int n, const unsigned *x, unsigned *out)` 的接口约定（out[i] = x 中严格小于 x[i] 的个数）。
// （同源件亦见 1017 #125836 / 1017a #125829 / 1017b #125828 —— 三题同源。）
// [2] 基数分区（一趟分桶 / counting sort 的分区趟）为教科书通用技术，无特定出处；
// 本件的具体用法（K=2^B 桶 + 桶内 2^F 格 u8 细直方图 L1 驻留 + 桶基址叠加直写 pref）为本席自行设计。
// 许可：以上均为 duck.ac 上的公开提交与本工作区材料，均未附带任何软件许可证声明；
// 本文件按 RULES §3 逐项署名「原作者账号 + 原始提交地址 + 所用内容」，遵守方式 = 完整保留上述署名于文件开头。
// ======================
// [3] 本席（r110a_）自研微刀 [r110a-HOIST]：判题机免费探针台（立即体验通道）同进程 A/B 实测
// （控制臂 = 本件底盘同码，逐臂 memcmp bad=0、FNV 1154980931258647343 与 #129472 逐位相同）：
// 会话 P3: CTL 302,783,738 / HOIST 301,468,592 = -0.434%（同码漂移带 0.051%）
// 会话 P4: CTL 305,033,298 / HOIST 300,708,716 = -1.418%
// 会话 P5: CTL 302,768,706 / HOIST 300,922,938 = -0.610%（同会话 d96 -0.458% / d128 +0.152%）
// ⇒ 三次独立会话同号、均 > 3x 漂移带；距离轴在 HOIST 下仍以 64 为峰（96/128 均更差）。
// （**实验目的**：把输出趟的逐圈边界判据提出热环，测它在本件上的单变量收益。）
// [4] 本席（r110a_）自研第二把刀 [r110a-NT]：输出趟改**批量非时间存**（16 元素攒进 alignas(64)
// 暂存 -> 2 条 `_mm256_stream_si256`），机理见下方「思路」段。判题机探针同会话 A/B 实测
// （控制臂 = 本件底盘 HOIST 件同码，逐臂 memcmp bad=0、FNV 1154980931258647343 逐位相同）：
// 会话 P8: REF(HOIST) 301,530,226 / NT 298,576,356 = **-0.980%**（同码漂移带 0.025%）
// 同会话另一臂 MLP2（同前瞻点发两条预取）读数 +0.250% ⇒ 判负，未采。
// （**实验目的**：单变量测「把顺写输出的 RFO 与 L3 污染去掉」在本件上的收益。）
// ===== 思路 ===== （本发为正式性能提交，非试验性）
// 【判型】判题机 i3-8100 @3.6GHz / L3 6MB / 4KB 页。本题 n=10000000 ⇒ 直方图 10MB、前缀表 40MB，均远超 L3；
// rank-1 件的耗时 = **1e8/n 量级的随机 RMW（1 元素 1 条 DRAM 行）+ 查表随机读**。
// 判题机探针（立即体验通道，本席）在本题同尺寸 n=1e7 上的读数（TSC 3.6GHz）：
// rank-1 件：memset 1.2M + 计数 202.0M + 前缀 12.8M + 查表 303.9M = 519.9M（↔ 板面 143.891 ms ✓ 同口径）
// 本件引擎：粗直方图 18.0M + 分区散射 80.0M + 桶内细计 52.3M + 查表 307.6M = 457.9M（−11.9%）
// ⇒ 微刀（NT 32B 批存、预取距离 16/32/64/128、NT 存 pref）在判题机上全部 |Δ|<1% —— 对手件已贴在随机访问墙上，
// 只能**结构性**减少随机 DRAM 行数。
// 【刀 `[r2g2-RADIXCNT]`】把"随机 RMW 计数"换成**两趟 cache 友好的分桶计数**：
// ① **粗直方图**（K=2^B=1024 桶，u32 = 4KB，L1/L2 驻留）：对每个 x 只做一次小数组自增（无需 DRAM 行）；
// ② **一趟散射分区**：按桶基址把值写入 part[]（K 个顺序写流 ⇒ 同时活跃约 K 行 ≈ 64，驻留 L1/L2，
// 避免 rank-1 件"1 元素 1 条 DRAM 行"的随机写）；
// ③ **桶内细计数**：逐桶建 2^F=16384 格 u8 细直方图（16KB，**L1 驻留**）→ 桶内独占前缀叠加桶基址
// **顺序直写 pref**（顺写，无随机行）。
// 合计 = 粗直方图 2.0 + 散射 8.0 + 桶内 5.2 ≈ **15.2 ticks/元素** vs rank-1 件 21.5（计数+前缀）⇒ 探针 −11.9%。
// 【逐位精确保障（律：任何输入下正确）】u8 细直方图对**任意**输入都可能回绕（例：全等值输入 ⇒ 单格 = n > 255）
// ⇒ 桶内计数趟带回绕检测 `if (++fh[v] == 0) { of = 1; break; }`；一旦检测到回绕，立刻跳到与 rank-1 件
// 完全一致的**宽路径**（memset(hist)/逐值 4 字节计数/前缀直写 pref），输出趟与之一字不差 ⇒ 与 rank-1 件逐位相同。
// 另有两道守卫：值域 x[i] ≥ 2^(B+F) 时、n > 1e8（pref 容量上限）时，同样走宽路径。
// 【未改动】输出趟、计数语义、回退件的字节直方图路径均取自 [1]。
// ======================
#include <cstring>
#include <cstdint>
#include <immintrin.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi2,popcnt")
#define B_BITS 10
#define F_BITS 14
#define KMASK ((1u << B_BITS) - 1u)
#define FMASK ((1u << F_BITS) - 1u)
#define MAXBITS 27 /* 题面值域 [0,n), n ≤ 1e8 < 2^27 */
/* [r64a7-1PASS] 每桶预留槽位（part 以 b*C_BUCKCAP 为桶 b 的区首）。
随机输入下桶计数 = Poisson(16384)（桶宽 2^14 值 × 密度 n/值域 = 1）⇒ C=32768 = 2× 均值 = 128σ；
K*C = 1024*32768 = 33554432 项 ≤ 已声明的 part[100000016+64] ⇒ **.bss 布局一字节不动**。 */
#define C_BUCKCAP 32768u
/* [r64a7-STRIDE] 桶 b 的区首 = b*BSTRIDE（BSTRIDE ≥ C_BUCKCAP ⇒ 区域互不重叠），
容量守卫仍用 C_BUCKCAP。★这是本单唯一的第二个必要常数，理由见件头「散射写流的组相联」段。 */
#define BSTRIDE 32864u
#define BUCKPOS(b) ((size_t)(b) * BSTRIDE)
static unsigned char hist[100000000 + 64];
alignas(64) static unsigned pref[100000016 + 64];
alignas(64) static unsigned short part[100000016 + 64];
alignas(64) static unsigned cnt[1024 + 8];
alignas(64) static unsigned sc[1024 + 8];
static unsigned char fh[1 << 16];
alignas(64) static unsigned short pref16[100000016 + 64];
/* [r40rc-R8] `hist` 全件从未被读写（宽路径用 `pref`）⇒ 复用为二级残差表（n 字节，题目 n ≤ 1e8）。 */
#define resid8 hist
alignas(64) static unsigned short cb[(1u << B_BITS) * 64 + 8]; /* [r40rc-P16] 桶内 u16 相对前缀：随机表 40MB -> 20MB */
static inline void wide_path(int n, const unsigned *x, unsigned *out) {
/* = 引用 [1] 的宽计数路径（4 字节计数，逐位精确） */
std::memset(pref, 0, (size_t)n * sizeof(unsigned));
for (int i = 0; i < n; i++) ++pref[x[i]];
unsigned s = 0;
for (int i = 0; i < n; i++) { unsigned c = pref[i]; pref[i] = s; s += c; }
}
alignas(64) static uint64_t unary_rank[(100000000+15)/16+8];
static inline unsigned unary_query(unsigned v) {
uint64_t w = unary_rank[v >> 4];
unsigned r = v & 15;
uint64_t selected = _pdep_u64(1ull << r, w & 0x007fffffffffffffull);
return sc[v >> F_BITS] + cb[v >> 8] + unsigned(w >> 55)
+ unsigned(__builtin_ctzll(selected)) - r;
}
void count_1d(int n, const unsigned *x, unsigned *out) {
const unsigned K = 1u << B_BITS;
const unsigned FM = FMASK;
/* 守卫：引擎覆盖值域 [0, 2^(B+F))；题面保证 x[i] ∈ [0, n) ⇒ n ≤ 2^(B+F) 即可（另限 pref 容量 1e8） */
bool ok = ((size_t)n <= ((size_t)1 << (B_BITS + F_BITS))) && (n <= 100000000);
bool wide = !ok; /* [r40rc-P16] 输出趟分流标志 */
if (wide) { wide_path(n, x, out); goto outpass; }
{
bool of = false;
/* [r64a7-1PASS] ①② 合并为**单趟**：每桶预留 C_BUCKCAP 个 u16 槽位，散射时直接把
(v & FM) 写进本桶预留区（`wp[b]` 由 b*C 起推进）—— 于是**不再需要先算粗直方图**，
x[] 少读一整趟（n×4 B = 40 MB 顺序读）。
桶计数在散射后由游标反读（`wp[b] − b*C`），同时得到桶基址 sc[]；任一桶计数 > C
即回退宽路径（随机输入下桶计数均值 16384 / σ≈128 ⇒ C=32768 是 128σ 之外）。 */
{
static unsigned wp[1024 + 8];
for (unsigned b = 0; b < K; b++) wp[b] = (unsigned)BUCKPOS(b);
for (int i = 0; i < n; i++) { unsigned v = x[i]; part[wp[v >> F_BITS]++] = (unsigned short)(v & FM); }
unsigned o = 0;
for (unsigned b = 0; b < K; b++) {
unsigned c = wp[b] - (unsigned)BUCKPOS(b);
if (c > C_BUCKCAP) { of = true; break; } /* 桶容量守卫 => 回退宽路径（正确性闸） */
cnt[b] = c; sc[b] = o; o += c;
}
}
/* ③ 桶内 u8 细直方图 + 前缀直写 pref（带回绕检测 ⇒ 回退宽路径） */
for (unsigned b = 0; b < K && !of; b++) {
size_t beg = BUCKPOS(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 end = beg + (size_t)cnt[b]; /* [r64a7-1PASS] 桶计数由游标反读得到 */
if (end - beg > 65535u) { of = true; break; } /* 冗余（cnt[b] ≤ C = 32768 < 65535）：保留作下限保险 */
std::memset(fh, 0, (size_t)1 << F_BITS);
for (size_t t = beg; t < end; t++) { unsigned v = part[t] & FM; if (++fh[v] == 0) { of = true; break; } }
if (of) break;
/* [r64a7-FUSED] ② 与 ③ 合并：本桶的 u8 细直方图 fh 已是「桶内值序」的计数序列，
其**独占前缀**就是桶内相对秩 P_b[l]（[A] 用 u16 中转表 pref16 承载，本件取消该表）。
本环每次载入 32 个 fh 字节，做 (1,2,4,8) 四次 slli+add 得 32 元独占前缀（模 256，
而块内任一独占前缀 ≤ 块元素数 ≤ 255 ⇒ 模 256 即精确），并直写 u8 残差表 Rb；
同一载入另走 sad_epu8+add_epi64 累加出**宽（u64）块元素总数** count，用于 >255 守卫
（u8 进位只能给模 256 的值，识别不出 300 与 44 的差别，故必须宽累加）。 */
/* [r110a-CB256] 块基址表的粒度由 128 值块放宽到 **256 值块** ⇒ 表由 256 KB 缩到
78 KB（判题机实测：把该表的触碰面积从 256 KB 压到 39 KB 值 **-8.6%**、压到 1.2 KB 值
-12.5%、整条载入拿掉值 -14.6%）—— 该表是**每元素一次随机读**，256 KB 恰好等于 L2 容量
而在本题（unary 表 5 MB + x 流式 40 MB）下留不住，降到 78 KB 后能常驻 L2。
代价：组基址字段由 8 位放宽到 **9 位**（bits 55..63），一元标记区由 56 位收到 55 位
（守卫 pos<55 ⇒ 单组元素数 ≤39，16 值组 Poisson(16) 的 5.75σ，仍极安全）。 */
unsigned local = 0; /* 桶内计数（**256 值块**起点处）*/
unsigned b256 = 0; /* 当前 256 值块内、到本 16 值组之前的计数 */
uint64_t *Ub = unary_rank + ((size_t)b << (F_BITS-4));
for (size_t c = 0; c < lim; c += 128) {
size_t e = c + 128; if (e > lim) e = lim;
if ((c & 255u) == 0) cb[((size_t)b << 6) + (c >> 8)] = (unsigned short)local;
unsigned block_count = 0;
for (size_t j = c; j < e; j += 16) {
size_t je = j + 16; if (je > e) je = e;
unsigned group_count = 0;
uint64_t marks = 0;
for (size_t k = j; k < je; ++k) {
unsigned pos = group_count + unsigned(k-j);
if (pos >= 55) { of = true; break; }
marks |= 1ull << pos;
group_count += fh[k];
}
if (of || (b256 + block_count) > 511u) { of = true; break; }
Ub[j >> 4] = marks | (uint64_t(b256 + block_count) << 55);
block_count += group_count;
}
if (of || (b256 + block_count) > 511u) { of = true; break; }
local += block_count;
b256 += block_count;
if (((c + 128) & 255u) == 0) b256 = 0;
}
if (of) break;
if ((size_t)(b + 1) << F_BITS > (size_t)n) break;
}
if (of) { wide = true; wide_path(n, x, out); }
}
outpass:
/* 宽路径输出趟：与 [A] 一字不差（pref 存全局 rank） */
if (wide) {
for (int i = 0; i < n; i++) {
if (i + 64 < n) __builtin_prefetch(pref + x[i + 64], 0, 3);
out[i] = pref[x[i]];
}
return;
}
/* [r40rc-R8] 快路径输出趟：128 值块基址(512KB, L2 驻留) + 块内 u8 残差(10MB 随机表)。
恒等：cb[..] + resid8[v] == sc[v>>14] + P[v]，见件头推导。 */
/* [r110a-HOIST] 把 `i + 64 < n` 这个**逐圈比较**提出热环 —— 判据成立时进主环（无分支、
每圈一条 prefetcht0），尾部残段单独收尾（语义与原式等价：原式在 i+64>=n 时本就不发预取）。
[r110a-NT] 在 [r110a-HOIST] 之上再改**存的路径**：out 是 40 MB 顺写、写后从不读 ⇒
逐元素 4 B 存要为每一行先付一次 RFO 读（+40 MB 流量），而脏行又占满 6 MB L3、把随机表
`resid8`(10 MB) 的行挤出去。改成**每 16 个元素攒进 alignas(64) 暂存后发两条 32 B
`_mm256_stream_si256`**：RFO 与 L3 污染同时消失。`stream` 要求 32 B 对齐 ⇒ 主环前先按标量
走前导把 `out+i` 对齐（本件不假设调用方对齐）；主环条件 `i + 16 + 64 < n` 保证 16 个
`x[i + j + 64]` 都在界内，尾段回落到标量 + 逐圈判据。两把刀都在判题机探针同会话 A/B 单变量定价过：
HOIST 三会话 −0.434 / −1.418 / −0.610%（同码漂移带 0.021~0.051%）；NT 相对 HOIST −0.980%（带 0.025%）。 */
{
int i = 0;
for (; i < n && ((uintptr_t)(out + i) & 31u); i++) { /* 前导：把 out+i 对齐到 32 B */
if (i + 32 < n) __builtin_prefetch(unary_rank + (x[i + 32] >> 4), 0, 3);
const unsigned v = x[i];
out[i] = unary_query(v);
}
alignas(64) unsigned buf[16];
for (; i + 16 + 32 < n; i += 16) { /* 主环：16 元素一批 + 2 条 NT 32 B 存 */
for (int j = 0; j < 16; j++) {
__builtin_prefetch(unary_rank + (x[i + j + 32] >> 4), 0, 3);
const unsigned v = x[i + j];
buf[j] = unary_query(v);
}
_mm256_stream_si256((__m256i *)(out + i), _mm256_load_si256((const __m256i *)buf));
_mm256_stream_si256((__m256i *)(out + i + 8), _mm256_load_si256((const __m256i *)(buf + 8)));
}
_mm_sfence();
for (; i < n; i++) { /* 尾段：标量，逐圈判据 */
if (i + 32 < n) __builtin_prefetch(unary_rank + (x[i + 32] >> 4), 0, 3);
const unsigned v = x[i];
out[i] = unary_query(v);
}
}
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 63.251 ms | 64 MB + 476 KB | Accepted | Score: 100 | 显示更多 |