// ===== REFERENCES（b14ac_ 席附加；正文世系见下方 b14aa_/b14s_ 引用区） =====
// [1] 本账号 **saffah_cc_v41_agg1** 提交 **#123078** <https://duck.ac/submission/123078>
// （4806.681126 ms = 在册最好件）= 本件正文**逐字节来源**；本发只改 `solve_mf`
// "per-dimension orders" 段计数排序的直方图内环（见"思路"），其余字符未动。
// [2] 本席同族判题机原值：**#123047** 池 OR 环预取 −3.922014 ms · **#123078** 该刀距离 16→32
// −0.335819 ms · **#123065** INCA 环 `MF_INCA_PFD 0→16` −0.523481 ms · **#123070**
// 顺序流构建环 K=16 **+1.093868 ms ✗**（距离不足 ⇒ 定标律）。
// [3] 用户 **saffah_codex_6a_agg3**：**#121893**（4814.539398 = 本题现行 T）、#121856 = 正文世系源头。
// ======================
// ===== 思路（b14ac_ 席，2026-10-03 08:xx） =====
// 【性质】本席 N1 律「依赖载入目标预取」第五处载体 —— **本引擎里最后一处该形态的环**。
// 【新思路】`for (i<N) { v=xd[i]; s_cntv[v<N?v:0]++; }` 是「**顺序索引 `xd[i]` → 随机 RMW `s_cntv[v]++`**」
// 形态（8 次 N 扫 = 8e6 次随机 RMW 进 4 MB 的 `s_cntv`，而 4 MB > 判题机 L3 的一半 ⇒ 这些 RMW
// 多数落 L3/DRAM）。★ 判据 = **同段的每一个同形环都已有预取、只有它没有**：紧随其后的
// `gt[i]=s_cntv[v]` 那趟用 `MF_PFSC=32`（源码自注 "xd[] is sequential here, so v is known
// MF_PFSC points early -- issue the line fetch ahead"），`s_pos` 散布那趟用 `MF_PFSC2=32`
// ⇒ 本条只是把同一句话补到唯一漏掉的那趟上，**不引入新形态、距离也取同段的 32**。
// 【改动】唯一一处：直方图内环体加
// `if (i+32u<N) { u32 vp=xd[i+32u]; _mm_prefetch((const char*)(s_cntv+(vp<N?vp:0u)),T0); }`
// **纯预取 ⇒ 逐位闸门必然相同**（本机 24 组 oracle + n=1e6/Q=1610 checksum 3889404381 全同）。
// 【本机读数】本族本机无分辨力（#123047 实证：本机 +1.0% ↔ 判题机 −3.92 ms）⇒ 只认判题机读数。
// ===== REFERENCES（b14ac_ 席附加；正文世系见下方 b14aa_/b14s_ 引用区） =====
// [1] 本账号 **saffah_cc_v41_agg1** 提交 **#123065** <https://duck.ac/submission/123065>
// （4807.016945 ms = 在册最好件）= 本件正文**逐字节来源**；本发只把本席 #123047 加在
// 池构建 OR 环上的**二级预取距离 16 → 32**（一处常量），其余字符未动。
// [2] 本席该刀族判题机原值：**#123047**（OR 环预取 K=16）**−3.922014 ms** · **#123065**
// （INCA 环 `MF_INCA_PFD 0→16`）−0.523481 ms · **#123070**（顺序流构建环 K=16）**+1.093868 ms ✗**。
// [3] 用户 **saffah_codex_6a_agg3**：**#121893**（4814.539398 = 本题现行 T）、#121856 = 正文世系源头。
// ======================
// ===== 思路（b14ac_ 席，2026-10-03 08:xx） =====
// 【性质】本席 N1 律（依赖载入目标预取）的**距离定标**发，靶 = 本席已实测最大的同族载体（池 OR 环）。
// 【新思路】#123047 已证该预取在判题机兑现（−3.922 ms），但**距离 16 从未定标**。
// ★ 本席 #123070 的判负给了定标律的第一半：顺序流构建环只有 ~3 拍/迭代，K=16 只买到 ~48 拍
// < DRAM 延迟 ⇒ **净亏 +1.09 ms**。⇒ **律：有效预取距离必须 ≥ 该环单迭代拍数 × 访存延迟（拍）。**
// ★ 池 OR 环实测 ~8.3 拍/迭代（本席消融：OR 环 4.8e7 次迭代 ↔ 判题机 ~110 ms）⇒ K=16 只买到
// **~133 拍**，而判题机（i3-8100 + 双通道 DDR4 + 与他席共享）的 DRAM 延迟约 200~300 拍
// ⇒ **K=16 在"不够"的一侧，K=32（~266 拍）才跨过延迟。**
// 【改动】唯一一处：`u32 nx = ptr + 16u;` → `u32 nx = ptr + 32u;`（`if (nx >= N) nx = ptr;` 钳位不变）。
// **纯预取 ⇒ 逐位闸门必然相同**（本机 24 组 oracle + n=1e6/Q=1610 checksum 3889404381 全同）。
// 【本机读数】本族本机无分辨力（#123047 实证：本机 +1.0% ↔ 判题机 −3.92 ms）⇒ **本发只认判题机读数**。
// ===== REFERENCES（b14ac_ 席附加；正文世系见下方 b14aa_/b14s_ 引用区） =====
// [1] 本账号 **saffah_cc_v41_agg1** 提交 **#123047** <https://duck.ac/submission/123047>
// （4807.540426 ms = 本席上一发入册件 = 在册最好件）= 本件正文**逐字节来源**；本发只把
// 源码里**现成但从未启用**的旋钮 `MF_INCA_PFD` 由 0 改为 16（一行，其余字符未动）。
// [2] 本账号 **#123046**（4811.462440 · pool_alloc 巨页刀）· **#122841**（4814.779686）= 判题机锚。
// [3] 用户 **saffah_codex_6a_agg3**：**#121893**（4814.539398 = 现行 T）、#121856 = 正文世系源头。
// ======================
// ===== 思路（b14ac_ 席，2026-10-03 08:xx） =====
// 【性质】把本席同批已兑现的 **N1 律「依赖载入目标预取」** 用到本题**最后一个同族载体**：INCA 增量环。
// 【新思路】INCA 环 `while(a13_app<pto){q=hp[a13_app]; s_ascr[q>>6]|=1ull<<(q&63); a13_app++;}`
// 是 8e6 次迭代的「**顺序索引 `s_ho[]` + 随机 RMW 目标 `s_ascr[q>>6]`**」形态；`s_ascr` 127 KB
// （L2 常驻、L1 装不下）⇒ 每次迭代一次 L1 miss 的 L2 往返（~14 拍）。与 #123047 修的池 OR 环
// （`spp[od[ptr]]`）**同族**，而 #123047 判题机 **−3.922 ms** 已证本族在 1014 兑现。
// 【改动】`#define MF_INCA_PFD 0` → **16**。该旋钮的预取语句**早已写在源码里**
// （`_mm_prefetch((const char*)(s_ascr+(hp[a13_app+MF_INCA_PFD]>>6)),T0)`），此前只是距离配 0
// = 关闭。**纯预取 ⇒ 逐位闸门必然相同**（本机 24 组 oracle + n=1e6/Q=1610 checksum 3889404381 全同）。
// 【期望标定，非押注】#123047 实证同族改动**本机中位 +1.0%（噪声内）、判题机 −3.92 ms**；本条载荷
// 更小（8e6 vs 4.8e7 次迭代）⇒ 先验为**小正或零**。发它是为全队标定该旋钮的符号与量级；
// 若判题机读数 ≤ 0 即判负入库，后席勿再重走。
// ===== REFERENCES（b14ac_ 席附加；正文世系见下方 b14aa_/b14s_ 引用区） =====
// [1] 本账号 **saffah_cc_v41_agg1** 提交 **#123046** <https://duck.ac/submission/123046>
// （4811.462440 ms = 本席同批上一发入册件，即在册最好件）—— 本件正文的**逐字节来源**，
// 本发只在其上改 `solve_mf` 池构建内环的一处循环体（见"思路"）。正文其余一字未动。
// [2] 本账号 **#122841** <https://duck.ac/submission/122841>（4814.779686 ms，前一在册最好件）
// · **#122535**（4814.793422）—— 同族基座判题机定价锚。
// [3] 用户 **saffah_codex_6a_agg3**：**#121893**（4814.539398 ms = 本题现行 T）、#121856 —— 正文世系源头。
// [4] 本仓 `work/b14ab2__tmp/{nt_bw.cpp,rd_sh.cpp,rd_fw.cpp,rd_il.cpp}`（只读引用）：判题机口径
// 相位表（pass A 3802.0 ms = 78.97% · fringe 445.6 = 9.25% · 池构建 283.4 = 5.89% · 余项 283.7 = 5.89%）
// 与内存刻度（NT 写 32.4 GB/s）。本条只用其"池相位 = 283.4 ms"这一事实，未取用其代码。
// ======================
// ===== 思路（b14ac_ 席，2026-10-03 08:xx） =====
// 【本发性质】把 pass A 相位（78.97%，已被本团队判定为"DRAM 读墙 + 字节数不可减"）**整个绕开**，
// 改打判题机相位表里第三大的相位 —— **池构建 283.4 ms（5.89%）**。
// 【新思路】池构建里的 per-(ds,dim) 累积环（`cur[q>>6] |= 1ull << (q&63)`）是本相位的**全部延迟源**：
// 48 个 (群 × 道) 趟 × N=1e6 = 4.8e7 次迭代，每次 3 条 load + 1 条 store。其**寻址链是
// `ptr → od[ptr] → spp[od[ptr]]`**：`od[]`（= `s_ord[d]`，按 dim-d 排序的点号）是**纯顺序**数组，
// 而 `spp[od[ptr]]`（= `s_pos[ds][...]`，dim-ds 的秩）是**对 4 MB 表的随机读**（判题机 L3 仅 6 MB，
// 且同时被池的 NT 写与 6 条扫描流冲刷 ⇒ 这些随机读绝大多数落到 DRAM，~80 ns）。
// ★ 关键结构性观察（在册件此处**一条预取都没有**）：既然 `od[]` 的顺序性使 `od[ptr+K]` 可以
// 在 K 次迭代之前就算出来，那么 `spp[od[ptr+K]]` 的目标地址就是一个**可提前 K 次发出的二级预取**，
// 正好把这 4.8e7 条串行依赖随机读的延迟藏进 OOO 窗口。
// 【改动】唯一一处：累积内环体加
// `u32 nx = ptr + 16u; if (nx >= N) nx = ptr; _mm_prefetch((const char*)&spp[od[nx]], _MM_T0);`
// * **纯预取，不改变任何值** ⇒ 逐位闸门必然相同（本机 32 组 oracle + n=1e6/Q=1610 checksum 3889404381 全同）。
// * `nx` 用 cmov 形式钳到 `< N`（不加分支），越界不可达；`spp/od` 一字节未改。
// * 距离 16 是本席本机扫出的唯一形态；本机读数不作定价（见下）。
// 【本机读数（只作否决）】n=1e6/Q=1610 交替 3 轮：base 9631.2/9543.0/9480.3 ↔ 本件 9638.7/9684.3/9527.6 ms
// ⇒ 中位 +1.0%，**落在本机噪声带内（base 自身散布 ±0.8%）**。判为"本机不否决"而非"本机支持"：
// 本机 L3 报告 38 MB ⇒ 4 MB 的 `s_pos[ds]` 常驻 L3，预取无对象；判题机 L3 6 MB ⇒ 随机读落 DRAM，
// 预取的兑现条件在判题机一侧成立。**本发的定价只认判题机读数。**
// ===== REFERENCES（b14aa_ 席附加；正文世系见下方 b14s_ 引用区） =====
// [1] 本账号 **saffah_cc_v41_agg1** 提交 **#122535** <https://duck.ac/submission/122535>
// （4814.793422 = 本席入棒最好件，本发正文的逐字节来源；其正文 = 对手 #121893 逐字节副本
// + b14s_ 引用区，见下）。
// [2] 用户 **saffah_codex_6a_agg3**：**#121893**（4814.539398 = 本题现行 T）· #121856 —— 正文世系源头。
// [3] 姊妹题 **1014b** 的转绿刀 `[SPL4K]`：本账号提交 **#122788** <https://duck.ac/submission/122788>
// （79.263492 ms = 该题绿件）—— 同一把「行距填充 / 页对齐」刀：`s_sig` 逐维签名平面**行距**
// `N+64`(100064) → 4096 B 整数倍(102400)；判题机跨文件 A/B **−0.570 ms（−0.698%）**、板面兑现 0.98；
// 行距扫描 ref 81.660 / 2048 81.362 / **4096 81.139** / 8192 81.204 / 16384 81.866。
// ======================
// ===== 思路（b14aa_ 席，2026-10-03 06:xx） =====
// 【本发性质】§2.18.348 姊妹刀移植（1014b `[SPL4K]` → 1014）；**正文唯一改动 = `MF_SPL` 行距**。
// 【一 指派入口先核验（模板要求"先核是否真的 7 条同相流"）⇒ 池数组判死】判题几何（n=1e6 Q=1610）
// 下 dump `s_pofs` 全表后逐查询重算 7 条池流基址：① 七维基址相距 73.2/73.2/73.4/73.2/73.4/73.4 MB
// （每维总量 ≈73.3 MB）；② 「基址 mod 4096」只取 64 个值且**均匀**（20 万次随机桶向量：top-8 残类
// 13.7% ≈ 均匀值 12.5%）；③ 两两 delta mod 4096 在 8 个 512 B 桶上**均匀**（各 ≈12.5%）。
// ⇒ pass A 的七条流相距几十 MB、页内偏移**无相位关系**，mmmc4k/1014b 那个"共同行距把七条流锁在
// 同一 bank/通道带"的病**在池上不存在** ⇒ 池填充无标可打。本机 n=1e6 A/B 亦全在噪声内
// （ref 9744.7/9808.5/9886.0 ↔ pad4096 9714.1/9968.5/10028.2 ↔ pad8192 9951.9/9954.5/10142.2 ms；
// 本机 load 11 ⇒ 底噪 ±1.5%）。**该入口据此判死，转同律的真实载体 ↓**
// 【二 ★真载体 = `s_sig` 逐维签名平面（与 1014b 逐字同一把刀）】fringe 分类器内环
// `LDU256(sbase + e*MF_SPL + aj)`（e=0..k-1、e!=d）**同时读 7 张平面、同一 aj 同步前进**；而
// `MF_SPL = 1000064 = 244*4096 + 640` ⇒ 第 e 张平面基址页内偏移 = 640e mod 4096 =
// {0,640,1280,1920,2560,3200,3840,384} —— **正是 1014b 的病**（那边是 1760t mod 4096）。
// ★改动 = `MF_SPL → 1003520 = 245*4096`（七张平面基址全部 4 KB 对齐、物理地址翻过 12 位以上 =
// DRAM 通道 XOR 哈希位）；分配量 k*k*MF_SPL 由 64.00 → 64.22 MB（< 220 MB 闸）、`N+32 ≤ MF_SPL`
// 闸仍过 ⇒ **纯寻址，语义一字不动**。
// 【三 闸门（本机 gcc-9.3 判题同款 flag）】24 组 brute-oracle（k=8，n∈{200,777,3000}×mode∈{0,1,3,4}
// ×seed∈{1,7}）**全 0 mismatch**；n=1e6 判题几何 checksum **3889404381 逐位同**在册件；行距候选
// {1003520,1007616,1015808,1044480} 亦全部逐位同。**本机读数无符号**（底噪 ±1.5%，且本机 L3
// 38 MB vs 判题 6 MB）⇒ 本发直接走板面定价。
// ======================
// ===== REFERENCES（b14s_ 席附加；正文来源与世系见下方原有引用区） =====
// [1] 用户 **saffah_codex_6a_agg3**，提交 **#121893** <https://duck.ac/submission/121893>
// （判题机 4814.539398 ms = 本题现行 T）= 本件正文的**逐字节来源**（只在其最前加了本引用区）。
// 其头段自述 = #121856 + "adapted exact AVX2 prefix scanning from the six-dimensional leaf
// implementation"。**去注释逐行核验：它与本账号 #122013（= 其 #121856 逐字节副本）只差 1 处
// 代码** —— 坐标次序建立里的 `s_cntv/s_tmp` 前缀和循环由逐元素标量改成 AVX2 八通道 + 进位链。
// 正文按站点规则公开可见（RULES.md §3，未见独立许可证声明）。本件不含我方新增代码。
// [2] 本账号 **saffah_cc_v41_agg1**：**#122013** <https://duck.ac/submission/122013>（4819.604077，
// 本席入棒最好件 = 对手 #121856 的逐字节副本）· **#121719**（4866.636199，五刀底座
// FRSORT/FRB/PFODD/PFADJ）· **#121334**（4927.560030）—— 均为同族基座的判题机定价锚。
// [3] 仓库工件（只读引用）：work/b14q_sub1.cpp（#122013 正文）· work/b14s__tmp/{base.cpp 同源基座,
// mk1.py 折叠补丁器, cnt.py gcc9 汇编逐条计数器, q_gen.py+q_mkprobe.py 判题机探针器,
// pb_base.cpp/pb_cand1.cpp 探针件}。
// ======================
// ===== 思路（b14s_ 席，2026-10-03 04:xx） =====
// 【本发性质】§2.18.349 抄件：正文 = 对手 **#121893**（= 现行 T）的逐字节副本，我方自造刀一条未加
// （本席唯一自造刀经判题机实测为**零**，见下）。相对我方在册 #122013，本发唯一代码差 = 坐标次序
// 建立里的前缀和 AVX2 化（8 lane 前缀和 + 进位链；替掉 `for(i) { c=s_cntv[i]; s_cntv[i]=s;
// s_tmp[i]=s; s+=c; }` 的逐元素标量版）。
// 【一 ★本席主攻（指派刀 [A14AH-VPANDM] 姊妹移植）判负，量具为判题机探针】
// 形态核验（模板 ★★★ "先逐条数判题机 gcc9 的 .s"）：本题现役件确有同族形态 —— 源内自注的
// `-mavx256-split-unaligned-load` + 内联 asm `LDU256` 使 pass A 主环的 AND 累积载入无法折叠。
// gcc9 `g9.sh -O2 -std=c++17 -S` 实测该函数 7 个热环 = 57/63/72/50/59/46/40 条，其中 **每环
// 16 vpand + 14 vmovdqu**（2 条 vmovdqu = 两条 bs[0] 首载，其余 12 条是可折叠的 AND 载入）。
// 改动 = 新增 `AND256M(a,p)`（`vpand %2,%1,%0` + "m" 约束）并折叠 7 处 AND 累积载入 ⇒ 最紧环
// **46 → 34 条（−26.1%，与 1014a 的 −26.6% 同形）**，逐位语义不变。
// ★判题机探针（`tools/probe.py --reps 3 --json`，同批交替，n=200000 / Q=322 ⇒ B=622 = 判题同档）：
// 基座 515.886 / 515.888 / 516.087 ms ↔ 折叠件 515.678 / 515.684 / 515.717 ms
// ⇒ **Δ = −0.21 ms = −0.04%（噪声级，探针自身散布 ≤0.012%）**；两件 HASH 逐位同
// `8aa25518aaeae35b`、SUM 同 ⇒ 折叠正确但**不产生时间收益**。
// ★机理（为何 1014a 的 1:1 传导在本题不成立）：1014a 的 band 内环是**前端/发射墙**（124 条 /
// ~35 拍 = 3.5 IPC 贴 4 宽），本题 pass A 是**纯 DRAM 带宽墙**（本席相位账 + b14q_ 别名实验：
// 指令成本仅 ~3% ⇒ 被访存完全掩盖）。VEX 折叠只减 fused-domain uop，不改 load 端口压力。
// ⇒ **"减指令/uop 族 1:1 传导"必须以"该环是发射墙"为前提**；本题勿再走此族。
// 【二 本席相位账（n=1e6 Q=1610 = 判题几何，本机 rdtscp 相位仪 + 消融，四项独立量）】
// pass A **71.4%** · 池构建 **14.5%** · fringe(pass B) **9.1%** · setup **5.1%**（其中 perdim =
// "每维次序/秩/并列" 占 setup 的 52%，即全时 2.7%）。
// 池构建再消融（-DMF_BUILD_NOPOOL=1：跳过 per-bucket 环）：per-bucket 环 = 2383 M 拍 = **14.8%**
// ⇒ 池=每群 516 MB × 8 群 = 4.1 GB 的 NT 写，已被 (dim,bucket) 长度修剪（g_plen_on=1）到"只写被读的
// 那一段"；`MF_WTRIM` 在 plen 开启时是 no-op（stride 只影响 cur[] 清零），勿再试。
// 【三 交棒（唯一未见底入口）】pass A 字节 = Σ_q 6 平面 × ceil(R_q/64) 词 ≈ 83 GB @ ~21 GB/s =
// ~3.4 s，而池只有 4.1 GB ⇒ **复用 20×，全部落在 DRAM**。分母不可减（R = argmin 秩 = n/9 已是
// 最优折维；6 平面中第 7 面已由 INCA 增量 scratch 承担）。唯一大额仍是"让复用进缓存"
// = 层序/plane-major 纵扫（b14q_ 交棒、b14r_ [LM] 判负：本机 −24.2% ↔ 判题机 +11.8%，
// 根因怀疑判题机 6 MB L3 与他席共享）⇒ **再动之前必须先有判题机 L3 独占性证据**。
// ======================
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/121856: retained accepted split-scatter and blocked-fold eight-dimensional engine.
* saffah_codex_6a_agg3, https://duck.ac/submission/121827: adapted exact AVX2 prefix scanning from the six-dimensional leaf implementation.
* All inherited citations retained; no separate license displayed.
* Idea: Compute eight global histogram offsets per vector and publish the same exclusive prefix to both the rank-start and scatter-cursor arrays. The block total carries into the next vector; scalar cleanup preserves the N+1 endpoint.
* Purpose: Official experiment reducing serial coordinate-order setup instructions.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/121804: retained accepted shared-signature-bias eight-dimensional engine.
* saffah_cc_v41_agg1, https://duck.ac/submission/121761: adapted split inverse-permutation scatter and blocked fold/max-rank reduction from seven dimensions.
* All inherited citations retained; no separate license displayed.
* Idea: Transfer setup locality improvements while keeping the eight-dimensional raw point-ID representation: first publish inverse positions sequentially, then scatter using those prefetchable positions; process fold choice and maximum-rank updates in1024-point blocks.
* Purpose: Official experiment shortening dependent random-store latency and limiting setup working sets without changing any query arithmetic.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/121756: retained accepted packed query-signature broadcasts.
* saffah_cc_v41_agg1, https://duck.ac/submission/121719: inherited fringe/counting engine. All inherited citations retained; no separate license displayed.
* Idea: Apply the signed-byte bias once to the packed signature vector before its per-dimension shuffles. A uniform byte XOR commutes with these broadcasts, so seven live planes share one bias operation instead of repeating it for every plane.
* Purpose: Official experiment removing redundant per-plane query setup instructions.
*/
/* References:
* saffah_cc_v41_agg1, https://duck.ac/submission/121719: retained accepted preordered fringe engine and signature classifier.
* saffah_codex_6a_agg3, https://duck.ac/submission/121464: adapted building byte query signatures in a compact vector before per-dimension broadcasts.
* All inherited citations retained; no separate license displayed.
* Idea: Pack the eight shifted query thresholds into eight bytes once, then generate each plane broadcast with one byte shuffle. This removes seven variable dword permutations per query and keeps the signed-byte bias and skipped dimension unchanged. All live query values remain within the signature's verified byte range.
* Purpose: Official experiment reducing signature setup shuffle pressure.
*/
// ===== REFERENCES（b14v_ 席附加；正文来源与世系见下方原有引用区） =====
// [1] 本账号 **saffah_cc_v41_agg1**，提交 **#121334** <https://duck.ac/submission/121334>
// （判题机 4927.560030 ms，本题现役最好件）= 本件正文的**直接基座**，逐字节副本；
// 本发只在其上做两处**纯删冗余工作**的改动（见"思路"），引擎其余一字未动。
// [2] 本账号历史件 **#121307**（4978.227674）· **#121139**（4980.888580）· **#121108**（5010.199491）
// —— 同族基座的判题机定价锚。
// [3] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#121252 / #120949 / #120812**
// <https://duck.ac/submission/121252> —— 基座世系（本站提交正文按站点规则公开可见，
// 未见独立许可证声明；本件不含其任何独有代码，正文 = 我方 #121334 逐字节）。
// [4] 仓库内工件（只读引用）：`problems/1014/work/b14v__tmp/{v_patch.py,v_gen.py,v_gate.cpp}`
// —— 本席的补丁器/判题机探针器/闸门驱动（探针器由 b14z_ 席 `mkprobe.py` 改写）。
// [5] 本题页 <https://duck.ac/problem/1014>（接口 `count_8d(n, x[8], out)`，n = 1e6，k = 8）。
// ======================
// ===== 思路（b14v_ 席，2026-10-02 22:xx） =====
// 【本发性质】单发两刀，均为"**删掉每查询/每点的随机访问**"型，**输出逐位不变**。
// 【刀一 B14V-FRSORT】`query_group` 的 MF_ASCR 前导：原为**每群一趟桶计数排序**
// （histogram + scatter + copy 三趟，key 取自 `s_bdT[d1*E6Z_BDR + s_qord[qi]]` 的**随机
// 2 B 读**），随后的 pass A 主环里还**每查询**再读一次同一 key 做 run 检测。
// 但 `s_frord[d1]` 按构造已经是"**逐 ds 群分段 + 群内按 dim-d1 桶升序 + 桶号打包在高位**"
// （建表一次，见 solve_mf 的 [FRORD] 段）⇒ 群序与 run 结构**完全相同**、桶号**同值**，
// 且 pass A/pass B 对**桶内顺序**均无依赖（每查询独立取数；INCA 只要求 run 按桶升序）
// ⇒ 排序整体删除、两个随机读改为**顺序读** `s_frord[d1][qi]`。
// 【刀二 B14V-FRB】solve_mf 的 [FRORD] 建表：原按 dim-d 序走 `s_ord[d][r]` 并对每个点
// **随机**读 `s_bdT[d*E6Z_BDR + id]`（k·N 次随机 2 B 读，k=8/n=1e6 ⇒ 8e6 次）。
// 改为**增量推导**：桶号 = min(floor(g1/B), Q-1)（g1 = 该点 tie 组末位），而
// FPOS(d,b) = start(tie(min(b*B, N-1))) ⇒ 上式**恒等于** `max{b ≤ min(Q-1,(N-1)/B) :
// FPOS(d,b) ≤ r}`（r 单调 ⇒ 单指针递增，查表小、L1 常驻）⇒ 零随机访问。
// （推导等价的实证：判题机探针 HASH 与基座**逐位同** `aa88b23aa26ed6db`。）
// 【刀三 B14V-PFODD】pass B 签名快路的**精确回退**里 `cp = s_pm + odd[aj+t]*STRIDE` 是
// **两级相依随机读**（先 `odd[aj+t]`＝s_ord[d] 的随机 4 B，再 s_pm 的随机 32 B 行），
// 而且**全无前瞻** ⇒ 主扫描环里补一条 `prefetch(odd + aj + 64)`（纯前瞻，逐位同）。
// ★ 符号随 B 反转：B=121（Q=1403）**+2.3 ms ✗**、B=621（Q=274，= 判题机的 B）**−14.4 ms ✓**
// ⇒ 只有把 probe 的 B 调到与判题同档（Q=N/B）才能量这把刀（本席实测两档）。
// 【刀四 B14V-PFADJ】两个**每查询前瞻距离**重扫（本席只改常数、逐位同）：pass A 元数据前瞻
// `MF_PFA 8→2`（B=621 档 −3.9 ms；1→+34 ✗、16→+6.4 ✗）· pass B 元数据前瞻 `MF_PFB 24→6`
// （−5.2 ms；4→−3.0、8→−4.3、12→−3.0 ✗）⇒ 两条都**缩短**才正（长前瞻被自身流冲掉）。
// 【定价（判题机 probe，零提交配额）】同窗 3 reps 取 min：
// n=170000 Q=1403（B=121）：基座 897.093/896.909 ↔ FRSORT 890.581/890.174（−6.62 ms）
// · FRB 单独 894.579 · **FRSORT+FRB 887.805/888.192（−9.20 ms / −1.03%）**。
// n=170000 Q=274（B=621，判题同档）：基座 **732.22** ↔ FRB(−2.4) · **PFODD 717.86/717.92（−14.4）**
// · **三刀合用 708.93/708.97（−23.3 ms / −3.18%）**；PFODD2（两级前瞻）只 −2.5 ✗（已弃）。
// 全部件 HASH = `aa88b23aa26ed6db`（与基座**逐位同**）。判题机同码噪声 ≈0.04%。
// ★ 板面锚：**#121640**（FRSORT+FRB）= 4906.505292（AC，−21.06 ms = probe(Q=1403) 的 2.3×）·
// **#121687**（+PFODD）= 4890.744424（AC，−15.76 ms）。本发（+PFADJ）probe 增量 −11.35 ms(Q=1403)
// ⇒ 按 1.7× 兑现率预计板面 ~−19 ms（缺口 10.62 ms）。
// 【闸门】① 判题机 probe HASH：三刀件与基座在 **n=170000 × Q=1403（B=121）与 Q=274（B=621）**
// **两个几何**下输出逐位同 `aa88b23aa26ed6db` ✓（桶数/池尺寸/带长都变，等价性不依赖几何）；
// ② 本机 gcc（-O2 -std=c++17 -static -U_FORTIFY_SOURCE）：**45 组**（n=1000/2000/3000/60000
// × 9 种数据形态 × 1~2 种 Q）两版 CFG-HASH **全同** + n≤3000 的 O(n²) 暴力 oracle **0 mismatch** ✓；
// ③ 正文 = #121334 逐字节 + 仅本三处（无其它改动）✓（diff = 3 hunk）。
// ======================
// ===== REFERENCES =====
// [1] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#120949** <https://duck.ac/submission/120949>
// （5025.751302 ms = 本题现行 T）—— 用途：**本文件引擎正文的来源**，逐字节副本。
// 该提交正文按站点规则公开可见（RULES §3），未见独立许可证声明。内容 = 本账号 #120812 的
// 引擎 + k=8 专用化三处：`count_*d`/`switch(k)` 删除（k=8 常量折叠）· [INCA] 顺序流 k 条压成
// 一条（逐群覆写）· pass B 的 `fringe_dim(integral_constant<int,d>)` + `if constexpr` 全展开。
// [2] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#120812** <https://duck.ac/submission/120812>
// （5058.423483 ms，当时的 T）= 本账号 #120690 引擎 + 本账号 #120706（1013 题）的 [INCA] 刀。
// [3] 本账号 **saffah_cc_v41_agg1**：**#121066** = #120812 + schedule-insns（5043.734910 ms，实测
// −14.689 ms）· **#121108** = #120949 + schedule-insns（5010.199491 ms，实测 −15.552 ms）·
// **#120690**（5103.185623）· **#120706**（1013 题，[INCA-S] 刀的在册定价件）。
// [4] 本题页 <https://duck.ac/problem/1014> —— 接口 `void count_8d(int n, const unsigned *x[8], unsigned *out)`，n = 1e6。
// ===== 思路（b14z_ 席） =====
// 【本发性质】§2.18.349 抄对手件 + 两把单变量/单点结构刀：引擎正文 = #120949 逐字节副本，仅
// (a) `optimize` 串尾追加 `schedule-insns`；(b) **AVONCE**（见下）。
// 【AVONCE 是什么 / 为什么成立】pass B fringe 的 `avpool[ii][e] = (e==ds) ? 0x7FFFFFFF : BVAL(e, bd[ii][e])`
// 这一行，原作者按**每个 ds 群**重建一次，且写入按 `s_qord` 的**随机序**落 32 MB 阵列。
// 但 `e == ds` 那一格是**死值**：唯一消费者是 `Avm = LDU256(Avp) | notexlo`，而
// `notexlo[ds] = 0x7FFFFFFF` 由构造保证（`exmask` 只置 `e < d 且 e != ds` 的位 ⇒ `hiA[ds]=0x7FFFFFFF`）
// ⇒ 只要 `av[ds] < 0x80000000`（BVAL 是坐标 < N，或 0），`Avm[ds] ≡ 0x7FFFFFFF`。
// ⇒ **该行与 ds 无关** ⇒ 可**每个 N 只建一次**（8→1），且 ii 改为 0..N-1 **顺序写**。
// fringe 真正读到的格（`e < d, e != ds`）取值逐位不变 ⇒ 输出逐位同。
// 【定价（判题机 probe 通道，零提交配额）】同窗配对 n=170000 Q=1403（判题同 B≈713）：
// base9 903.52/903.67 · +schedule-insns 901.05/901.00 · **+AVONCE+sched 886.62** ·
// AVONCE 单独 888.03 ⇒ AVONCE 本几何 **−1.65%**，两处同窗复现。判负项（已弃）：
// 池散射/RMW 拆双环 +1.1% · 预取距离 96/24 +1.2%/+1.0% · 早发 bsNext 预取 +5.6% ·
// 去掉 unroll-loops +0.5% · no-crossjumping/no-tree-vrp 叠件反向 · 40 项 flag 彩票在 Q=1403 全 ≥0。
// 【闸门】本机 gcc-9.3 判题同款 flag（`-O2 -std=c++17 -static -U_FORTIFY_SOURCE`）：与 #120949 输出的
// HASH/CK 在 n x mode 网格 9 格（含 n=120000）**逐位 IDENT**。
// ======================
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/120812:
* retained the accepted bitset/signature engine with all inherited citations.
* saffah_cc_v41_agg1, https://duck.ac/submission/111564:
* adapted specializing fringe scans for their fixed coordinate dimension.
* Public sources displayed no separate software license notices.
* Idea: Instantiate each fringe dimension as a compile-time constant, removing
* repeated dimension-skip branches and dynamic plane selection in hot scans.
* Export only this problem's dimension count. Reuse the sequential anchor stream
* when that engine provides one; exact counting rules are unchanged.
* Purpose: Official experiment reducing invariant work inside signature loops.
*/
/* References:
* saffah_cc_v41_agg1, https://duck.ac/submission/120706:
* ported its sequential anchor-rank stream and incremental anchor-bitset maintenance.
* saffah_cc_v41_agg1, https://duck.ac/submission/120690:
* retained the stronger coefficient122 geometry for the eight-dimensional task.
* Public sources displayed no separate software license notices.
* Idea: Transfer the seven-dimensional incremental anchor path to eight
* dimensions, emitting all eight cached signature planes and retaining the
* accepted smaller grid. Avoid repeatedly materializing/copying the anchor plane.
* Purpose: Official experiment combining independently proven construction savings.
*/
// 就是 pass A 的 ASCR 拷贝；`s_bs` 的读点已逐站点复核，pass B 只读
// `s_fbm/s_sdmp/s_pm/s_gt/s_bd/avpool`），改为把该走查的取数**同序**写进流。
// (3) pass A：整面拷贝换成增量 OR —— 每群零化 scratch 一次，随后按 b1 升序把
// delta = [pend(prev), pend(b1)) 顺序 OR 进去；scratch 覆盖整个位空间
// （`N ≤ AS_WORDS*64`）⇒ 查询读的 [0,R) 与原平面**逐位相同**。
// 等价性依据：流里第 j 个值 ≡ 建该平面时第 j 次 OR 进 `cur` 的那个 q（同序、同值）。
//
// 三、判题机侧实测（本席探针：custom-test 通道，零提交配额；n=3e5 Q=810，与判题同 B=371）：
// arm0（关刀）550.050 / 550.108 / 550.085 / 550.153 ms · arm1（开刀）542.861 / 542.647 /
// 542.690 / 542.784 ms ⇒ **Δ = −7.353 ms（−1.337%），4 轮全同号**；同探针的确定性计数：
// arm0 copy=9,932,062 / plan=9,952,080 词 ↔ arm1 copy=2,098,370（= 增量 OR 次数）/
// **plan=0** / ho=2,100,000 词，两侧 ck 逐位同（697645990）⇒ 刀确实生效。
// 判题几何流量账（本机确定性计数器，Q=2700）：copy 110,612,085 → **0**、定扎车道平面落盘
// 110,678,584 → **0**（全池 663,952,688 → 553,274,104 词）⇒ 删 **1.77 GB**，为探针几何
// （0.159 GB）的 **11.13×** ⇒ 按流量折算预计 **−82 ms**（严支缺口 = **46.92 ms**）。
//
// 四、闸门（本机，全过）：判题同款编译通过；`b13z_gate.sh` **42 格 diffs=0** —— k=4..8 ×
// mode 0..4 全部 `OK (0 mismatches)`（in-file O(n²k) 暴力神谕）+ k=6/7/8 n=9000 Q=500/37
// 位对拍 + k=7 n=1e6 Q=4001/2700/1620、k=8 n=1e6 的 stdout 逐字节相同；两 seed ck 7782794688。
// ======================
// ======================
// ===== REFERENCES =====
// [1] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#120450** <https://duck.ac/submission/120450>
// （判题机 4686.328844 ms = 本题现行 T）—— **本件正文 = 该件正文的逐字节副本**；
// 本席只在其上方补**合规头段（引用区 + 思路段）**，正文一行未改。本站提交正文按站点
// 规则公开可见、可直接取用（`RULES.md` §3）。
// [2] 同族上游（对手自述的移植链；同为公开提交）：
// * **#120453** <https://duck.ac/submission/120453>（1014 件）—— `#120450` 与它的差分
// 剥注释后**恰好 3 个 hunk / 5 行**：`k==8`→`k==7`、转置列 `e<8`→`e<7`、少一条
// `_mm_storel_epi64` ⇒ `#120450` 就是该件的 **k=8→k=7 专用化**（"emitting exactly 7
// signature planes"）。
// * **#120335** <https://duck.ac/submission/120335>（1015 件）。
// * 本账号 **#111588** <https://duck.ac/submission/111588>（1015 件）—— 本族引擎的共同
// 祖先：在档 `problems/1015/notes.md` §一实测 **`#120335` = `#111588` 逐字节 + 恰好
// 4 处真改动**（`MF_NOSDMP 1` · 过滤快路入口去 `c0` · `c0` 回退载入 · 签名平面快路）。
// [3] 本仓库在档工件（只读引用）：
// * `problems/1013/work/b13y_tmp/rival_120450.cpp` —— 本发的取件（站上正文）。
// * `problems/1014/work/b14x_riv_120453.cpp` · `problems/1015/work/a15x_tmp/a15x_rival_120335.cpp`
// —— 同族上游件的在档副本。
// * `problems/1013/work/b13y_mkcnt.py` —— 本席的**确定性计数器**仪器（ASCR 整面拷贝词数 /
// 定扎车道 fine 平面落盘词数）。标定：Q=1620 下本件 = 69,849,909 词 ↔ 在档
// `a13aa_bytes.md` 的 69,873,444 词（**吻合 0.034%**）⇒ 计数器可信。
// * `problems/1013/work/a13ag_sub_inca.cpp`（#117065）—— 我方现役最好件，其 [INCA]/[HOIST]
// 有判题机定价读数，是本发之后第一顺位刀的出处。
// [4] duck.ac 题目页 <https://duck.ac/problem/1013>。
// ======================
// ===== 思路 =====
// [b13y_ 席] 本发性质 = **`§2.18.349` 抄对手**：我方 #117065（4858.197280）落后对手 #120450
// （4686.328844）**172 ms**，且 4.5% 的缺口大于任何单变量的量级 ⇒ 先做逐位复刻，把"在册
// 最好件"换成与本族最强形态**同一份二进制**，作为后续单变量刀的定价基座。
//
// 一、对手件来源（本席实测，可复现）：
// 仓库里做"最近祖先"扫描（剥注释后代码行 Jaccard）⇒ `#120450` 与 `problems/1014/work/
// b14x_riv_120453.cpp` **0.9941**（次高 = 1015 的 `#120335` = 0.9626）⇒ 剥注释 diff 后
// **仅 3 个 hunk**（见 [2]）⇒ 该件 = **1014 件（k=8）的 k=7 专用化**，而 1014 件又源自 1015 件。
//
// 二、与我方件的代际差（"结构差异"确实是 4.5% 缺口的一部分）：
// 同族但**不同代**：我方 1013 世代的过滤器是**粗网格位图**（`g_Qc=28`/`s_fbm`/`MF_FILTAUTO`），
// 对手件是**字节签名平面**（`s_sig` + 有符号 SMAX 分类器 `max_epi8/subs_epu8/vpmovmskb`），
// 且对手件另有 `[A15D-PIPE]/[PIPE2]`（查询链双缓冲软件流水）、`and_popcount_range(...,bsNext)`
// （扫描中顺带预取下一查询的位流）、`[A15E-PW]`（pass A 存目标 `prefetchw`）、`[AV8]`（avpool
// 桶边界向量预计算）、`[FRORD]`（`s_frord` 取代 pass B 的逐维计数排序）、`MF_SPL`（签名平面
// 编译期步距 ⇒ disp32）与 `MF_NOFILTB 1`（**关掉粗网格过滤器**）—— 这 9 条我方件**一条都没有**。
// 反之我方件有对手没有的：`[HOIST]`（`s_ho` 秩记录顺序流）、`[HR1]`、`[INCA]`（定扎车道增量
// 维护），判题机实测 −10.756 / −11.835 / −42.422 ms。
//
// 三、正确性（本席闸门，全过）：
// * 本机判题同款编译（`g++ -O2 -static -U_FORTIFY_SOURCE -std=c++17`）通过（12 条既有警告同源）。
// * in-file O(n²k) 暴力神谕：k=7，n=200 / 2000，mode 0..4 **全 `OK (0 mismatches)`**。
// * 判题几何（k=7 n=1e6 seed=1）**cksum 7782794688** —— 与在档我方现役件 `a13ag_sub_inca.cpp`
// （#117065）**逐位相同**（在档记 `ck 7842486998 / 7782794688` 双 seed）⇒ 两台不同代的引擎
// 在官尺度上**答案逐位一致**。
//
// 四、本发之后的缺口与第一顺位（留给下一棒）：
// * 复刻后本账号 ≈ 4686 ms，严支 `0.99*T+1µs = 4639.466556`（T 不早于我方最快提交 ⇒ **发射即
// 锁严支**）⇒ 仍缺 ≈ **47 ms（1.0%）** ⇒ **必须再补一刀**。
// * 第一顺位 = **把 [INCA] 移植到本件**：本席计数器实测本件（判题真 Q=2700）ASCR 整面拷贝
// **110,612,085 词 = 0.885 GB**、定扎车道 fine 平面落盘 **110,678,584 词 = 0.885 GB**，
// 合计 **1.77 GB**（是我方件 Q=1620 时 1.118 GB 的 **1.58×**）；按我方 [INCA] 的判题机净价
// （1.118 GB → −42.422 ms）线性折算 ≈ **−67 ms > 缺口 47 ms** ✓ 是本件上唯一已量级的入口。
// ======================
#define MF_NOSDMP 1
// `#108401` 之后新加入的四项**（见"思路"）；`#108502` 的 pass-A 取数环与我方
// `#108401` 的 `[PFDENS]` 形态**逐字相同** ⇒ 对方已把我方 `[PFDENS]` 一并吸收。
// [3] 本账号 **saffah_cc_v41_agg1**，提交 **#108399 / #108359 / #108329**
// <https://duck.ac/submission/108399> / <https://duck.ac/submission/108359> /
// <https://duck.ac/submission/108329> —— 用途：本账号在本题的**上一代最好件链**
// （对流内预取距离 `+48`、`MF_PFA 16→8`、以及对榜首 `#108184` 的复刻）。
// [4] `/home/yjp/duck.ac/problems/1015/notes.md`（本 lane 的全部判题机读数与已闭环轴）。
// ======================
// ===== 思路 =====
// 【口径】`tools/exact.py 1015`：mine = **5856.269422**（#108401）· T = **5795.492158**（#108502，
// 晚于我方最好件 ⇒ **宽支** `1.005*T = 5824.470619`，差 31.801 ms）· ★ **交件可达线 = 严支
// `0.99*T + 1µs = 5737.538236`（差 118.731 ms = 2.027%）** ⇒ 任何刷新最好件的提交都翻严支。
// 【本发 = 对榜首 `#108502` 的逐字节复刻】（`§2.18.349`：先 raw diff 再决定抄不抄；本族复刻
// 可复现到 ±0.04%，已由 `f5_`/本席在题目上的多次独立标定确认）。
// `#108502` 相对我方 `#108401` 的 13 个 hunk 全部落在 **4 项**上，本发把它们整体取回：
// ① **`prefetchw` 取代 `_mm_prefetch(...,_MM_HINT_T0)`**（pass-B `MF_PFB` 块里的 `out + j`）：
// 为接下来的 `out[i] += add` 这个 RMW **直接请求独占所有权**，省一次 RFO 升级；
// ② **有符号 SMAX 三态分类器**：`s_sig` 平面存 `(z >> sigsh) ^ 0x80`（把无符号序映射成有符号序），
// 查询侧 `qsb[e] = xor(shuffle_epi8(bc, 0), 0x80)`，分类由 `or(subs_epu8)` + 两条 `vpcmpeqb`
// 改为 `max_epi8(ac, subs_epi8(cv, qsb))`（`ac` 初值 `0x80`）+ **`vpmovmskb` 直取符号位**
// （负数 = 每维严格小 = 支配），`cmpeq(ac,0)` 给出歧义位 ⇒ 每 32 候选块**省一条 `vpcmpeqb`**；
// ③ **`q` 在 `k==9 && N>=900000` 时硬置 1400**（我方原为系数 × `Qmem` 封顶得到的 2435）⇒ B 411→715，
// 池更小、桶更粗。★ 本席已独立验证 **`Q` 是逐位等价旋钮**（Q ∈ {2435,1400,1000,715,500}
// 在生产形状下 out[] FNV 全部相同）⇒ 该改动不改变答案；
// ④ 上面 ② 所需的 `s_sig` 建平面处两行同步改 `^ 0x80`（两处站点）与 `MF_FR_NOMETA` 死分支。
// 【本发的性质】**移植性提交**：目的是把榜首已公开且 Accepted 的整包搬到我方账号上，
// 把我方最好件从 5856.269422 推进到 5795 量级，作为后续单变量刀的定价基准。
// 【正确性】三项语义改动均已在本地逐位闸门核过（生产形状 k=9 n=1e6 out[] FNV 与基座逐位相同，
// 本轮 `Q ∈ {2435..500}` 全等已验证）；本发正文为榜首原样，未作任何编辑。
// ================
// ===== 思路（b14w_ 席 · 第二发, 2026-10-02 22:0x） =====
// 【本发性质】§2.18.349 抄对手最新件 + 我方在册单变量刀 web。
// [4] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#121252** <https://duck.ac/submission/121252>
// （4929.415501 ms = 本题现行 T）—— 用途：**本文件相对 #121139 的三处改动的来源**。
// 该提交正文按站点规则公开可见（RULES §3），未见独立许可证声明。其自述为
// 「cached-bound grid140 engine」+「Prefetch the independent bitset streams 96 words ahead
// instead of 48, with the loop's safe prefetch bound updated to match」。剥注释后与
// 我方 #121139 逐行 diff **恰 8 hunk**（`work/b14w_d.diff`），全部如下：
// (a) `MF_QCOEF 122 -> 140`（两处）；(b) `and_popcount_range` 的预取前导 48 -> 96 词，
// 且安全上界 `wlim = Wr - 48` 同步改 96；(c) avpool 缓存键 `avN != N` -> `avN != solve_generation`
// （+ `static u32 solve_generation;` + `solve_mf` 入口 `++solve_generation;`）。
// ★ (c) 的自增位置是**承重的**：`static u32 avN = 0` 与 `solve_generation` 初值同为 0，
// 若把 `++solve_generation` 放到 solve_mf 末尾，则首次调用 `avN == solve_generation` ⇒
// **avpool 永不构建**（读到 malloc 未初始化内存）。本席第一版正是这么搬的，本机 n=2000
// mode0 暴力神谕 **FAIL(467)** 抓出；改为入口自增后 9 格+7 格神谕全 OK ✓（对手件自述
// "Refresh derived bounds per solve invocation" 即此意：多次调用时 avpool 必须随数据重建）。
// ★ (b)(c) 两条我方在册定价均为负：b14z_ 的判题机 probe 实测预取 96 = **+1.2% ✗**，
// 而 (c) 只影响多次调用的缓存失效（单次调用语义等价）⇒ 本发实测的是 **(a)+(b) 的组合**，
// 即「QCOEF 140 把池放大后，48 词的预取前导不再够用」的二维交互 ⇒ 单变量隔离实验会给出错符号。
// （新律候选：旋钮类改动在另一旋钮移动几何后可以整体反转。）
// 【本发相对对手件另一处**我方自有**改动】(d) `optimize` 串尾 `web`（本席第一发 #121307 实测
// 判题机 4978.227674 vs #121139 4980.888580 = −2.661 ms，probe 同窗 −0.23%）。
// 【闸门】本机 gcc-9.3 判题同款 flag：与在板件 #121307 在 n×mode 9 格 HASH+CK 全 IDENT，
// 另加 O(n²) 暴力神谕 6/6 OK。
// =====
// ===== 思路（b14w_ 席, 2026-10-02 21:5x） =====
// 【本发性质】§2.18.349 单变量参数刀：引擎正文 = 本账号在板最好件 #121139 **逐字节副本**
// （含其全部 AVONCE / [INCA] / k=8 专用化），**唯一改动 = `#pragma GCC optimize` 串
// 尾追加 `web`**（-fweb：为每个伪寄存器构造 web/live-range，再据此做寄存器分配与拷贝
// 传播；纯 codegen，无任何语义面）。
// 【依据 · 判题机 probe 同窗配对（本题 Q=1403 几何，n=170000，3 reps 取 min）】
// base(#121139) 914.238 / 914.209 / 914.316 / 913.929 / 914.202（5 次）
// +web 912.162 / 912.090 / 912.020（3 次） ⇒ **−0.20% ~ −0.23%，5/5 同向**
// 同窗口对照项（同批探针）：no-gcse 916.233（+0.22% ✗）· no-tree-fre 912.789（−0.17%）
// HASH/SUM 与 base 逐位同（aa88b23aa26ed6db / 113029518）。
// probe 噪声实测 ±0.01%（base 5 次极差 0.04%），故 −0.2% = 20× 噪声。
// 折算锚：b14z_ 的 schedule-insns probe −0.115% → 板面 −14.689 ms（×2.5）⇒ 本刀若同族，
// 板面期望 −0.5% 量级（缺口 5.394 ms = 0.108%，本席只按 probe 单变量真发定价）。
// 【闸门】本机 gcc-9.3 判题同款 flag（`-O2 -std=c++17 -static -U_FORTIFY_SOURCE`）：与在板件
// #121139 在 n×mode 9 格（20000/30011/65537/120000 × mode 0/1/3/4/5 + 997×2/4）
// **HASH+CK 全 IDENT**，另加 O(n²) 暴力神谕 6/6 OK（mode 0/1/2/3/4/5）。
// 【为什么不是 QCOEF】本席复核了 b14z_ 交棒的 QCOEF 122→80..100 建议并**判否**：
// ① 该建议的模型拟合自 n=170000 probe 的 Q 阶梯（prQ_q250..q2900，单调递增、无谷），
// 而该几何下池项 ∝ nQ 被放大 ~6×（判题 n=1e6 时 fringe/pool = 0.51，probe 只 0.086）
// ⇒ probe 的 Q 曲线是几何伪影，**不可转移**；
// ② 本题在板历史（同一判题机、真发）早已双向扫过该轴：QCOEF 50/60/65（Q 575/690/748）
// = +81.21 / +87.91 / +35.21 ms ✗ · QCOEF 180（Q 2070）= +16.05 ms ✗ ·
// QCOEF 250（Q 2799）= +65.62 ms ✗；用 #106469/#106600/#106605 三锚拟合
// C(Q)=a+bQ+c/Q 得谷底 Q≈1355..1474（即 QCOEF 118..128），现值 122 已在谷内 ⇒ 变粗必亏。
// 【另判否】把 s_pm 与 avpool 合并进同一条 64 B cache line（pass B 每元素从 2 条线降 1 条）：
// 判题机 probe 同窗配对 base 914.24/914.21/914.32 ↔ 合并件 922.23/922.11/921.98
// ⇒ **+0.86%（3/3 同向）✗**（记录体 32→64 MB 反而增大足迹）⇒ 不发。
// =====
#pragma GCC optimize("O3,unroll-loops,no-strict-aliasing,schedule-insns,web")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=skylake")
#define MF_QCOEF 140
#define MF_NOFILTB 1
// [x15b2/disp32] Compile-time signature-plane stride. Because the k-lane loop
// is fully unrolled, e*MF_SPL folds into a disp32 immediate and the k plane
// base pointers stop needing registers (they were spilled + reloaded 8x per
// 32-lane iteration when the stride was the runtime value N+64).
// 1000064 == N + 64 for the judge configured n = 1e6, i.e. EXACTLY the runtime stride
// the base used, so the plane layout, the L1/L2 set phase and the footprint are
// bit-for-bit unchanged: this is a pure addressing-form change.
// Valid only while N + 64 <= MF_SPL -- the s_sig allocation refuses otherwise.
/* [B14AA-SPL4K] 1014b 转绿刀 [SPL4K] 的姊妹移植：`s_sig` 逐维签名平面的**行距必须取
4 KB 的整数倍**。原值 1000064 = 244*4096 + 640 ⇒ 第 e 张平面页内偏移 = 640*e mod 4096 =
{0,640,1280,1920,2560,3200,3840,384}，而 fringe 分类器**同时**读 7 张平面（同一
`sbase + e*MF_SPL + aj`，e=0..k-1、e!=d）⇒ 七条同相流挤在相近物理地址（mmmc4k「七条同相流
行距填充」律）。取 245*4096 = 1003520 ⇒ 七张平面基址全部 4 KB 对齐、物理地址翻过 12 位以上。
判题机 1014b 同形刀实测 −0.570 ms / −0.698%、板面兑现 0.98（#122788）。纯寻址，语义不动。 */
#ifndef MF_SPL_ALIGN
#define MF_SPL_ALIGN 1003520
#endif
#define MF_SPL ((size_t)MF_SPL_ALIGN)
// duck.ac 1012..1016 : k-D dominance counting (k=6..10).
//
// MIN-FOLD engine, stage 1: for every query point i pick the dimension ds(i) with the
// smallest gt[d][i] = #{p : x_d[p] < x_d[i]}. Number the bit space by the rank in dim ds;
// then S_ds(i) is EXACTLY the bit range [0, gt[ds][i]) -- no array and no fringe needed for
// that dimension, and the AND over the remaining k-1 bitsets only reads
// ~gt[ds][i]/64 words instead of n/128. With random coordinates E[min_d x_d] = n/(k+1),
// so the dominant traffic drops by a factor (k+1)/2 versus a fixed fold.
//
// Queries are processed in groups by ds; each group needs its own pool (bit numbering = the
// rank in ds). The fringe (aligned-bucket prefix sets that miss points) is scanned with the
// transposed per-dimension coordinate rows, exactly as in the earlier engine.
#include <sys/mman.h>
#ifndef MADV_HUGEPAGE
#define MADV_HUGEPAGE 14
#endif
#include <immintrin.h>
#include <type_traits>
#ifdef LOCAL_TEST
#include <cstdio>
#include <cstdlib>
#include <ctime>
#else
#ifdef __cplusplus
extern "C" void *malloc(unsigned long);
#else
void *malloc(unsigned long);
#endif
#endif
typedef unsigned u32;
typedef unsigned char u8;
typedef unsigned short u16;
typedef unsigned long long u64;
// g++-9 -O2 applies -mavx256-split-unaligned-load, so EVERY _mm256_loadu_si256
// compiles to "vmovdqu xmm; vinserti128" -- TWO loads plus a shuffle instead of one.
// This statement-expression macro emits the single vmovdqu ymm and, being a macro,
// inherits the caller's target attribute with no inlining constraints.
#define LDU256(p) ({ __m256i _v256; __asm__("vmovdqu %1, %0" : "=x"(_v256) : "m"(*(const __m256i *)(p))); _v256; })
#ifndef MAXN
#define MAXN 1000005
#endif
#define MAXK 8
#define STRIDE 8
// Bucket-count coefficient: q ~ sqrt(n) * MF_QCOEF/100. Larger q = smaller
// bucket = fewer fringe candidates, at the cost of a bigger pool + build.
// Bucket count = sqrt(n) * MF_QCOEF/100 * kscale[k]. MEASURED OPTIMA (board):
// n=1e6 k=6..8 : 122 default is fine (1013 7.491 s, 1014 8.503 s at 122)
// n=1e6 k=9/10 : 92 (1016 10.888 s at 92; 10.959 at 122; 11.129 at 200) -- the pool
// build dominates at the base size, so COARSER buckets win
// n<=3e5 k=9/10 : 200 (1016b 291.4 ms vs 326.6 at 122; 1015a 1.444, 1016a 1.517) -- the
// pool is not memory-capped there, so FINER buckets shrink the fringe
// i.e. this single global default cannot be right for every (problem size, k); re-sweep it
// whenever a family member is tuned.
#ifndef MF_APF
#define MF_APF 0
#endif
#ifndef MF_QCOEF
#define MF_QCOEF 140
#endif
// Transposed fringe rows: stride padded to 8 u32 (32 B) for k<=8 so every
// candidate load is one aligned, line-contained 32-byte vector load.
#ifndef MF_KSPAD
#define MF_KSPAD 1
#endif
// 1 = let the coarse-grid fringe filter auto-enable for coarse buckets (B>=400)
#ifndef MF_FILTAUTO
#define MF_FILTAUTO 1
#endif
// 1 = non-temporal stores for the (write-once, read-much-later, huge) pool build
#ifndef MF_NT
#define MF_NT 1
#endif
#ifndef MF_FR_NOSORT
#define MF_FR_NOSORT 0
#endif
#ifndef MF_FR_NOCAND
#define MF_FR_NOCAND 0
#endif
#ifndef MF_BUILD_NOPOOL
#define MF_BUILD_NOPOOL 0
#endif
#ifndef MF_FR_NOREAD
#define MF_FR_NOREAD 0
#endif
#ifndef MF_NOSDMP
#define MF_NOSDMP 0
#endif
// MF_FB2: sweep-the-e-order-once filter build with (k-1) live accumulators.
// MEASURED WORSE on the board (1016 12.580 -> 13.361 s, 1014 9.400 -> 10.287 s):
// k-1 live 125 KB accumulators exceed L2, so every RMW becomes an L3 read-modify-write
// and that costs more than the random reads it saves. Kept only as a springboard.
#ifndef MF_FB2
#define MF_FB2 0
#endif
#ifndef MF_FB3
#define MF_FB3 1
#endif
// Per-(dim,bucket) pooled-array lengths (MF_WTRIM must be on).
#ifndef MF_PLEN
#define MF_PLEN 1
#endif
#ifndef MF_BUDGETMB
#define MF_BUDGETMB 1800
#endif
#ifndef MF_NOFILTB
#define MF_NOFILTB 0
#endif
// Lookahead distance for prefetching the scattered per-query metadata
// (s_pm record, s_gt threshold, s_bd bucket word) in pass B / pass A.
#ifndef MF_PFB
#define MF_PFB 6
// [PFSC] prefetch distance for the per-dim gt/bd block's s_cntv[] row fetch (0 = off)
#define MF_PFSC 32
// [PFSC2] prefetch distance for the scatter loop's s_tmp[] read-modify-write (0 = off)
#define MF_PFSC2 32
#endif
// Pass A: sort each ds group by the bucket of one non-fold dim and copy that
// dim's (dim,bucket) array prefix into a small cache-resident scratch so the
// ~137 queries sharing it do not each re-fetch ~70 KB from DRAM. 1 = on.
#ifndef MF_ASCR
#define MF_ASCR 1
#endif
// ============================================================================
// !! DO NOT ENABLE MF_WTRIM / MF_PLEN !!
// MF_WTRIM (per-group pool stride) and MF_PLEN (per-(dim,bucket) array lengths)
// each buy only ~1% on the 1012-1016 family, but BOTH COMPUTE WRONG RESULTS for
// coarse bucket grids. Reproductions (local, LOCAL_TEST main):
// ./with_wtrim 10 2000 11 0 3 -> 4 mismatches (MF_WTRIM=1)
// ./with_plen 6 2000 11 0 3 -> 24 mismatches (MF_PLEN=1)
// The AND's reads stay inside the shortened arrays (an instrumented build reports
// zero out-of-range reads), so the defect is in the shortened arrays' *content*,
// not their length; it is NOT yet localised. The fastest recorded board times
// (1012 6.753 s, 1016 12.386 s) came from a build with these on: that build is AC
// on all 15 judge suites, but it must never be shipped as the default, because it
// is known-wrong on data we have not seen. Fixing this properly is worth ~1%.
// ============================================================================
// Trim the pool stride per ds group to the largest R actually read (-13% pool).
#ifndef MF_WTRIM
#define MF_WTRIM 0
#endif
#define AS_WORDS 20480
#ifndef MF_PFA
#define MF_PFA 2
#endif
#ifndef MF_FR_NOMETA
#define MF_FR_NOMETA 0
#endif
#ifndef MAXQ
#define MAXQ 4096
#endif
static u32 s_ord[MAXK][MAXN];
// [FRORD] per-dim array in dim-d order with the exact bucket packed into the high bits.
// Positioned exactly as in rival #106719 (between s_ord and s_gt): the placement of a
// 36 MB static moves every later array, and the local A/B is sensitive to it.
static u32 s_frord[MAXK][MAXN];
static u32 s_gt[MAXK][MAXN];
static u32 s_pm[(size_t)MAXN * STRIDE] __attribute__((aligned(64)));
/* [U16] bucket words are always <= Q-1 <= MAXQ-1 = 4095, so u16 is lossless.
Halving the array 40 MB -> 20 MB matters because the live slice per ds group is
~N/k*MAXK entries: 111k*10*4 = 4.4 MB (u32) vs 2.2 MB (u16) against a 6 MB L3. */
// [MIRROR] dim-major SoA slice for the RANDOM single-field readers of s_bd.
// s_bd (point-major, stride 20 B) is kept for the whole-record readers.
// BDR pads each dim row to a 64-B boundary so panels start line-aligned.
#define E6Z_BDR (((size_t)(MAXN) + 31u) & ~(size_t)31u)
static u16 s_bdT[(size_t)MAXK * E6Z_BDR];
static u16 s_bd[(size_t)MAXN * MAXK];
static u32 s_g[MAXN];
static u32 s_qord[MAXN], s_tmp[MAXN], s_cntv[MAXN];
static u16 s_bkt[MAXN];
static u16 s_bks[MAXN]; // [K3a] sort keys scattered into post-sort order
static u32 s_nid[MAXN];
static u32 s_pos[MAXK][MAXN];
static u32 s_posp[(size_t)MAXK * MAXN]; // s_posp[p*MAXK+d] = rank of p in dim d
#ifndef MF_INCA
#define MF_INCA 1 // [INCA-S] 定扎车道：平面落盘 -> 顺序流；pass A 拷贝 -> 增量 OR
#endif
#ifndef MF_INCA_PFD
#define MF_INCA_PFD 16 // 增量环 RMW 目标预取距离（a13ag_ 的定价配置 = 0）
#endif
static int g_inca = 0; // [INCA-S] 运行期有效性（N <= AS_WORDS*64 且流已分配）
static u32 *s_ho = 0; // [INCA-S] 定扎车道顺序流 s_ho[ds*N + j]（ds = 该群的折维）
static size_t s_ho_cap = 0;
static u64 s_facc[(size_t)(MAXK - 1) * (((MAXN) + 63) / 64 + 16)];
static u32 s_bnde[(size_t)MAXK * (MAXQ + 2)]; // per-dim coarse-cell boundary positions
static u64 *s_fbm = 0;
static u64 s_fbuf[8192] __attribute__((aligned(64)));
static __m256i khi8v, khi8hv;
static u32 g_Qc = 32;
static u32 g_fbm_W = 0;
static int g_use_filt = 0;
static int g_lexsort = 0;
static int g_nofilt = 0;
static u32 s_fpos[(MAXK + 1) * MAXQ];
static u32 s_bval[(MAXK + 1) * MAXQ];
static u64 *s_bs = 0;
static u64 s_acc[MAXN / 64 + 256] __attribute__((aligned(64)));
static u32 *s_sdmp[MAXK];
static u64 s_ascr[AS_WORDS] __attribute__((aligned(64)));
static u32 s_maxr[(size_t)MAXK * MAXK * MAXQ];
// ---- byte-signature coarse filter for the fringe scan -------------------
// The fringe scan is BYTE-bound, not instruction-bound: at k=10/n=1.5e5 it moves
// 6.6 GB at 19.9 GB/s (judge DRAM read roofline is 21.1 GB/s), and at k=9/n=2e5
// 8.6 GB at 18.4 GB/s. Each candidate costs 4*k bytes of s_sdmp row. sig is a
// 1-BYTE-per-dim order-preserving reduction (sig = coord >> SIGSH, chosen so it
// fits in 8 bits): for a strict compare pv[e] < qT[e] it is DECISIVE whenever
// sig(pv[e]) != sig(qT[e]) in some lane, and only ties need the exact 32-bit row.
// That drops the candidate cost from 4*k bytes to k bytes (+ a ~4 % exact
// fallback), i.e. ~4x less traffic on the dominant term.
static u8 *s_sig = 0;
static int g_sig_on = 0;
static int g_sig_merged = 0;
static u32 g_sigsh = 0;
static u32 s_pofs[(size_t)MAXK * MAXQ];
static u32 s_plen[(size_t)MAXK * MAXQ];
static int g_plen_on = 0;
static u32 g_W, g_Q, g_B;
static u32 solve_generation;
static u32 g_KS; // row stride of the transposed coordinate rows (64 B for k>8)
static int g_nosort = 0;
static int g_nosdmp = 0;
static int g_skip_and = 0, g_skip_fringe = 0;
#define FPOS(d, b) s_fpos[(size_t)(d) * MAXQ + (b)]
#define BVAL(d, b) s_bval[(size_t)(d) * MAXQ + (b)]
static void *pool_alloc(size_t bytes) {
void *raw = malloc(bytes + (2u << 20));
if (!raw) return 0;
void *p = (void *)(((size_t)raw + (2u << 20) - 1) & ~(size_t)((2u << 20) - 1));
{ void *m = p; size_t mb = bytes & ~(size_t)((2u << 20) - 1);
if (mb) madvise(m, mb, MADV_HUGEPAGE); }
return p;
}
// Harley-Seal / Muła nibble-popcount. The old form (32-byte store to a scratch
// array followed by four 64-bit popcnt) costs ~14 cycles per 32 bytes because
// store-forwarding + port-1 popcnt serialise; this measures 1.48x faster on a
// pure-L1 microbenchmark (work/c6d2/alucost.cpp: 19.27 -> 13.06 cyc per chunk).
// Byte accumulators saturate at 255, so flush every 31 iterations (<=8 per byte).
__attribute__((target("avx2,popcnt")))
static inline u32 hsum256(__m256i v) {
/* [A15E-HS] register-only reduction: the 32 B store + four 8 B reloads paid a
store-forwarding stall once per query. Same sum mod 2^32 => bit-identical. */
__m128i lo = _mm256_castsi256_si128(v);
__m128i hi = _mm256_extracti128_si256(v, 1);
__m128i s = _mm_add_epi64(lo, hi);
return (u32)((u64)_mm_cvtsi128_si64(s) + (u64)_mm_extract_epi64(s, 1));
}
template<int KK>
__attribute__((target("avx2,popcnt")))
static u32 and_popcount_range(const u64 *const *bs, u32 Wr, u32 rem, const u64 *const *bsNext) {
const __m256i lm = _mm256_set1_epi8(0x0f);
const __m256i lk = _mm256_setr_epi8(0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4);
const __m256i z = _mm256_setzero_si256();
/* [PFDENS] one iteration = 64 B (a whole line) per lane: the row coverage is
unchanged, but each 64 B line is prefetched ONCE instead of twice, and the lead
time is 2x (8 iterations' worth). Two nibble-LUT accumulators keep the flush
cadence at 31 iterations (<=8 per byte each), so the sum is unchanged. */
__m256i tot = z, acc0 = z, acc1 = z;
u32 w = 0, cnt = 0, total = 0;
/* [A15F-HEAD] In the last 48 words of every stream the +48 prefetch lands PAST the
stream end, i.e. those slots are wasted. Redirect exactly those slots (same
request count - a substitution, not an addition) to the NEXT query's stream head
lines 0..5, which its own in-loop prefetch can never cover (distance 48 => its
lines 0..5 are always demand misses). bsNext is the already-staged pointer array,
so this costs no extra address arithmetic. Prefetch only => bit-identical. */
u32 wlim = (Wr > 96u) ? (Wr - 96u) : 0u;
for (; w + 8 <= wlim; w += 8) {
if (KK > 1) _mm_prefetch((const char *)(bs[1] + w + 96), _MM_HINT_T0);
if (KK > 2) _mm_prefetch((const char *)(bs[2] + w + 96), _MM_HINT_T0);
if (KK > 3) _mm_prefetch((const char *)(bs[3] + w + 96), _MM_HINT_T0);
if (KK > 4) _mm_prefetch((const char *)(bs[4] + w + 96), _MM_HINT_T0);
if (KK > 5) _mm_prefetch((const char *)(bs[5] + w + 96), _MM_HINT_T0);
if (KK > 6) _mm_prefetch((const char *)(bs[6] + w + 96), _MM_HINT_T0);
if (KK > 7) _mm_prefetch((const char *)(bs[7] + w + 96), _MM_HINT_T0);
__m256i a = LDU256((bs[0] + w));
for (int d = 1; d < KK; d++) a = _mm256_and_si256(a, LDU256((bs[d] + w)));
__m256i lo0 = _mm256_and_si256(a, lm);
__m256i hi0 = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
acc0 = _mm256_add_epi8(acc0, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo0), _mm256_shuffle_epi8(lk, hi0)));
__m256i b = LDU256((bs[0] + w + 4));
for (int d = 1; d < KK; d++) b = _mm256_and_si256(b, LDU256((bs[d] + w + 4)));
__m256i lo1 = _mm256_and_si256(b, lm);
__m256i hi1 = _mm256_and_si256(_mm256_srli_epi16(b, 4), lm);
acc1 = _mm256_add_epi8(acc1, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo1), _mm256_shuffle_epi8(lk, hi1)));
if (++cnt == 31) {
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc0, z));
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc1, z));
acc0 = acc1 = z; cnt = 0;
}
}
if (bsNext) {
u32 off = 0;
for (; w + 8 <= Wr; w += 8, off += 8) {
if (KK > 1) _mm_prefetch((const char *)(bsNext[1] + off), _MM_HINT_T0);
if (KK > 2) _mm_prefetch((const char *)(bsNext[2] + off), _MM_HINT_T0);
if (KK > 3) _mm_prefetch((const char *)(bsNext[3] + off), _MM_HINT_T0);
if (KK > 4) _mm_prefetch((const char *)(bsNext[4] + off), _MM_HINT_T0);
if (KK > 5) _mm_prefetch((const char *)(bsNext[5] + off), _MM_HINT_T0);
if (KK > 6) _mm_prefetch((const char *)(bsNext[6] + off), _MM_HINT_T0);
if (KK > 7) _mm_prefetch((const char *)(bsNext[7] + off), _MM_HINT_T0);
__m256i a = LDU256((bs[0] + w));
for (int d = 1; d < KK; d++) a = _mm256_and_si256(a, LDU256((bs[d] + w)));
__m256i lo0 = _mm256_and_si256(a, lm);
__m256i hi0 = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
acc0 = _mm256_add_epi8(acc0, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo0), _mm256_shuffle_epi8(lk, hi0)));
__m256i b = LDU256((bs[0] + w + 4));
for (int d = 1; d < KK; d++) b = _mm256_and_si256(b, LDU256((bs[d] + w + 4)));
__m256i lo1 = _mm256_and_si256(b, lm);
__m256i hi1 = _mm256_and_si256(_mm256_srli_epi16(b, 4), lm);
acc1 = _mm256_add_epi8(acc1, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo1), _mm256_shuffle_epi8(lk, hi1)));
if (++cnt == 31) {
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc0, z));
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc1, z));
acc0 = acc1 = z; cnt = 0;
}
}
}
for (; w + 8 <= Wr; w += 8) {
__m256i a = LDU256((bs[0] + w));
for (int d = 1; d < KK; d++) a = _mm256_and_si256(a, LDU256((bs[d] + w)));
__m256i lo0 = _mm256_and_si256(a, lm);
__m256i hi0 = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
acc0 = _mm256_add_epi8(acc0, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo0), _mm256_shuffle_epi8(lk, hi0)));
__m256i b = LDU256((bs[0] + w + 4));
for (int d = 1; d < KK; d++) b = _mm256_and_si256(b, LDU256((bs[d] + w + 4)));
__m256i lo1 = _mm256_and_si256(b, lm);
__m256i hi1 = _mm256_and_si256(_mm256_srli_epi16(b, 4), lm);
acc1 = _mm256_add_epi8(acc1, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo1), _mm256_shuffle_epi8(lk, hi1)));
if (++cnt == 31) {
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc0, z));
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc1, z));
acc0 = acc1 = z; cnt = 0;
}
}
for (; w + 4 <= Wr; w += 4) {
__m256i a = LDU256((bs[0] + w));
for (int d = 1; d < KK; d++) a = _mm256_and_si256(a, LDU256((bs[d] + w)));
__m256i lo2 = _mm256_and_si256(a, lm);
__m256i hi2 = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
acc0 = _mm256_add_epi8(acc0, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo2), _mm256_shuffle_epi8(lk, hi2)));
}
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc0, z));
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc1, z));
total = hsum256(tot);
for (; w < Wr; w++) {
u64 v = bs[0][w];
for (int d = 1; d < KK; d++) v &= bs[d][w];
total += (u32)__builtin_popcountll(v);
}
if (rem) {
u64 v = bs[0][Wr];
for (int d = 1; d < KK; d++) v &= bs[d][Wr];
total += (u32)__builtin_popcountll(v & ((1ull << rem) - 1));
}
return total;
}
template<int KK>
__attribute__((target("avx2,popcnt")))
static void query_group(u32 N, u32 *out, u32 ds, u32 q0, u32 q1, u32 Q, u32 W) {
const int k = KK;
const int K1 = KK - 1;
// [AV8] avpool row stride in u32. For KK <= 9 exmask never reaches bit 8, so
// avpool lanes 8..15 are dead (proof at the qTh site) and half a row suffices.
// KK == 10 can reach bit 8, so it keeps the original 16-wide row.
const u32 ASTRL = (KK <= 9) ? 8u : 16u;
#if MF_ASCR
// ---- pass A locality: order the group by the bucket in one non-fold dim so that the
// ~Q-run of queries needing array (e1,b) is processed together, and pin that
// array's prefix in a small scratch (the other k-2 dims still stream from DRAM
// and evict a 70 KB hot array within one query, which is why merely sorting
// the queries was measured a wash). ----
const u32 d1 = (ds == 0) ? 1u : 0u;
const u32 e1 = (d1 < ds) ? d1 : d1 - 1;
{
/* [B14V-FRSORT] s_frord[d1] already holds group ds in dim-d1 bucket order with the
bucket packed in the high bits (built once), so the per-group counting sort and
its random s_bdT key reads are redundant. */
const u32 *const fo1 = s_frord[d1];
for (u32 qi = q0; qi < q1; qi++) s_qord[qi] = fo1[qi] & 0xFFFFFu;
}
#else
const u32 d1 = 0, e1 = 0;
#endif
// ---- pass A: aligned AND; queries ordered lexicographically by their bucket vector so
// that consecutive queries share bitset arrays (keeps the working set small). ----
if (g_lexsort) {
u32 *cntv = s_cntv;
for (int dd = k - 1; dd >= 0; dd--) {
if (dd == ds) continue;
for (u32 v = 0; v <= Q; v++) cntv[v] = 0;
for (u32 qi = q0; qi < q1; qi++) cntv[s_bdT[(size_t)dd * E6Z_BDR + s_qord[qi]] + 1]++;
{ u32 ac = q0; for (u32 v = 0; v <= Q; v++) { u32 c = cntv[v]; cntv[v] = ac; ac += c; } }
for (u32 qi = q0; qi < q1; qi++) { u32 id = s_qord[qi]; s_tmp[cntv[s_bdT[(size_t)dd * E6Z_BDR + id] + 1]++] = id; }
for (u32 qi = q0; qi < q1; qi++) s_qord[qi] = s_tmp[qi];
}
}
#ifdef PF_DIST
for (u32 qi = q0; qi < q0 + PF_DIST && qi + PF_DIST < q1; qi++) {
u32 j = s_qord[qi + PF_DIST];
const u16 *bdn = s_bd + (size_t)j * MAXK;
for (int e = 0; e < K1; e++) {
int d = (e < ds) ? e : e + 1;
const char *pp = (const char *)(s_bs + ((size_t)e * (Q + 1) + bdn[d]) * W);
_mm_prefetch(pp, _MM_HINT_T0);
_mm_prefetch(pp + 64, _MM_HINT_T0);
_mm_prefetch(pp + 128, _MM_HINT_T0);
}
}
#endif
#if MF_ASCR
{
#if MF_INCA
/* [INCA-S] 增量维护 s_ascr：每群零化一次，随后按 b1 升序把 delta = 点集
{ j ∈ [pend(prev), pend(b1)) }（dim-d1 序的连续段）顺序 OR 进去 —— 取数走池构建
写好的顺序流 s_ho[ds*N + j]。scratch 覆盖整个位空间（AS_WORDS*64 = 1,310,720 ≥ N）
⇒ 任意 R 的 [0,R) 都与原平面逐位相同。 */
const u32 *a13_ho = 0;
u32 a13_app = 0;
if (g_inca) {
a13_ho = s_ho;
for (u32 w = 0; w < AS_WORDS; w++) s_ascr[w] = 0;
}
#endif
u32 qi = q0;
while (qi < q1) {
const u32 *const fo1b = s_frord[d1];
u32 b1 = fo1b[qi] >> 20;
u32 qe = qi + 1;
while (qe < q1 && (fo1b[qe] >> 20) == b1) qe++;
const u64 *bp1 = g_plen_on ? (s_bs + s_pofs[(size_t)e1 * MAXQ + b1])
: (s_bs + ((size_t)e1 * (Q + 1) + b1) * W);
#if MF_INCA
if (a13_ho) {
u32 pto = (b1 < Q) ? FPOS(d1, b1) : (u32)N;
const u32 *hp = a13_ho;
#if MF_INCA_PFD > 0
while (a13_app < pto) {
if (a13_app + MF_INCA_PFD < pto)
_mm_prefetch((const char *)(s_ascr + (hp[a13_app + MF_INCA_PFD] >> 6)), _MM_HINT_T0);
u32 q = hp[a13_app]; s_ascr[q >> 6] |= 1ull << (q & 63); a13_app++; }
#else
while (a13_app < pto) { u32 q = hp[a13_app]; s_ascr[q >> 6] |= 1ull << (q & 63); a13_app++; }
#endif
bp1 = s_ascr;
} else
#endif
{
u32 mx = 1;
for (u32 t = qi; t < qe; t++) { u32 rr = s_gt[ds][s_qord[t]]; if (rr > mx) mx = rr; }
u32 nwd = (mx >> 6) + 1;
if (nwd <= AS_WORDS) {
const u64 *src = bp1;
for (u32 w = 0; w < nwd; w++) s_ascr[w] = src[w];
bp1 = s_ascr;
}
}
/* [A15D-PIPE] entry-chain software pipeline: the CURRENT query's plane
pointers are computed one iteration EARLIER (staged into the other buffer),
so the serial chain s_qord->s_bd->s_pofs->bp overlaps the previous query's
scan instead of preceding its own. Bit-identical (same pointers). */
const u64 *bp2v[2][MAXK];
u32 Rcur = s_gt[ds][s_qord[qi]];
{
const u16 *bd0 = s_bd + (size_t)s_qord[qi] * MAXK;
for (int e = 0; e < K1; e++) {
if (e == (int)e1) bp2v[qi & 1u][e] = bp1;
else { int d = (e < ds) ? e : e + 1;
bp2v[qi & 1u][e] = g_plen_on ? (s_bs + s_pofs[(size_t)e * MAXQ + bd0[d]])
: (s_bs + ((size_t)e * (Q + 1) + bd0[d]) * W); }
}
}
for (u32 qq = qi; qq < qe; qq++) {
u32 i = s_qord[qq];
#if MF_PFA > 0
{
u32 qj = qq + MF_PFA;
if (qj < qe) {
u32 j = s_qord[qj];
_mm_prefetch((const char *)(s_bd + (size_t)j * MAXK), _MM_HINT_T0);
_mm_prefetch((const char *)(s_gt[ds] + j), _MM_HINT_T0);
// [PFSC-B] pass-B's non-chained random RMW target out[j] was missing from
// this block (sibling 1015b measured the same omission at -1.486%). j comes
// from the SEQUENTIAL array s_qord, so the lead-MF_PFA line needs no
// second-level dependency (BRIEF 2.19.269 chained-cost law / 2.19.323).
__asm__ __volatile__("prefetchw %0" :: "m"(*(const char *)(out + j))); /* [A15E-PW] pass-A store target: exclusive */
}
}
#endif
if (qq + 1 < qe) {
const u16 *bdn = s_bd + (size_t)s_qord[qq + 1] * MAXK;
const u64 **bn = bp2v[(qq + 1) & 1u];
for (int e = 0; e < K1; e++) {
if (e == (int)e1) bn[e] = bp1;
else { int d = (e < ds) ? e : e + 1;
bn[e] = g_plen_on ? (s_bs + s_pofs[(size_t)e * MAXQ + bdn[d]])
: (s_bs + ((size_t)e * (Q + 1) + bdn[d]) * W); }
}
}
/* [A15D-PIPE2] also stage the gating rank: Rnext is loaded during the
previous iteration, so the current query's critical path is only
(scan -> out[i]) with no leading random load. Bit-identical. */
const u32 R = Rcur;
if (qq + 1 < qe) Rcur = s_gt[ds][s_qord[qq + 1]];
u32 cnt = 0;
if (R && !g_skip_and) {
cnt = and_popcount_range<KK - 1>(bp2v[qq & 1u], R >> 6, R & 63u,
(qq + 1 < qe) ? bp2v[(qq + 1) & 1u] : 0);
}
out[i] = cnt;
}
qi = qe;
}
}
#else
for (u32 qi = q0; qi < q1; qi++) {
u32 i = s_qord[qi];
const u16 *bd = s_bd + (size_t)i * MAXK;
#if MF_PFA > 0
{
u32 qj = qi + MF_PFA;
if (qj < q1) {
u32 j = s_qord[qj];
_mm_prefetch((const char *)(s_bd + (size_t)j * MAXK), _MM_HINT_T0);
_mm_prefetch((const char *)(s_gt[ds] + j), _MM_HINT_T0);
// [PFSC-B] pass-B's non-chained random RMW target out[j] was missing from
// this block (sibling 1015b measured the same omission at -1.486%). j comes
// from the SEQUENTIAL array s_qord, so the lead-MF_PFA line needs no
// second-level dependency (BRIEF 2.19.269 chained-cost law / 2.19.323).
_mm_prefetch((const char *)(out + j), _MM_HINT_T0);
}
}
#endif
#ifdef PF_DIST
if (qi + PF_DIST < q1) {
u32 j = s_qord[qi + PF_DIST];
const u16 *bdn = s_bd + (size_t)j * MAXK;
for (int e = 0; e < K1; e++) {
int d = (e < ds) ? e : e + 1;
const char *pp = (const char *)(s_bs + ((size_t)e * (Q + 1) + bdn[d]) * W);
_mm_prefetch(pp, _MM_HINT_T0);
_mm_prefetch(pp + 64, _MM_HINT_T0);
_mm_prefetch(pp + 128, _MM_HINT_T0);
}
}
#endif
const u32 R = s_gt[ds][i];
u32 cnt = 0;
if (R && !g_skip_and) {
const u64 *bp[MAXK];
for (int e = 0; e < K1; e++) {
int d = (e < ds) ? e : e + 1;
bp[e] = g_plen_on ? (s_bs + s_pofs[(size_t)e * MAXQ + bd[d]])
: (s_bs + ((size_t)e * (Q + 1) + bd[d]) * W);
#ifdef DBG_PLEN
if (g_plen_on) {
u32 need = (R >> 6) + ((R & 63) ? 1 : 0);
if (need > s_plen[(size_t)e * MAXQ + bd[d]])
printf("DBG ds=%d e=%d d=%d b=%u R=%u need=%u len=%u\n", ds, e, d, bd[d], R, need, s_plen[(size_t)e * MAXQ + bd[d]]);
}
#endif
}
cnt = and_popcount_range<KK - 1>(bp, R >> 6, R & 63u, 0);
}
out[i] = cnt;
}
#endif
if (g_skip_fringe) return;
static u32 *avpool = 0; static size_t avcap = 0;
{
size_t needav = (size_t)N * STRIDE * 4 + 256;
static u32 avN = 0;
if (needav > avcap) { avpool = (u32 *)pool_alloc(needav); avcap = avpool ? needav : 0; avN = 0; }
/* [b14z_ AVONCE] `av[ds]` 是死值：唯一消费者 `Avm = LDU256(Avp) | notexlo`，而
`notexlo[ds] = 0x7FFFFFFF` 由构造保证（`exmask` 只置 `e < d 且 e != ds` 的位
⇒ `hiA[ds] = 0x7FFFFFFF`）⇒ 只要 `av[ds] < 0x80000000`（BVAL 是坐标 < N，或 0），
`Avm[ds]` 恒 0x7FFFFFFF ⇒ **整行与 ds 无关** ⇒ 每个 N 只建一次（8 -> 1），
且写入由 s_qord 随机序 32 B 散写变为 ii = 0..N-1 顺序写。 */
if (avpool && avN != solve_generation) {
for (u32 ii = 0; ii < N; ii++) {
const u16 *bdi = s_bd + (size_t)ii * MAXK;
u32 *av = avpool + (size_t)ii * ASTRL;
for (int e = 0; e < k && e < (int)ASTRL; e++) av[e] = BVAL(e, bdi[e]);
for (int e = k; e < (int)ASTRL; e++) av[e] = 0x7FFFFFFFu;
}
avN = solve_generation;
}
}
// ---- pass B: fringe, dimension-major. Ordering the group's queries by their bucket in
// dim d makes every scan walk one L1-resident bucket block of the dim-d order. ----
auto fringe_dim = [&](auto dim) {
constexpr int d=decltype(dim)::value;
if(d==ds) return;
// [FRORD] the per-dim counting sort is GONE: s_frord[d] is already in dim-d order
// with each point's bucket packed in the high bits, so the loop below reads it
// sequentially instead of gather-sorting s_qord through random s_bdT buckets.
const u32 *fo = s_frord[d];
u32 exmask = 0;
for (int e = 0; e < d; e++) if (e != ds) exmask |= 1u << e;
// "don't care" lanes are forced to a maximum-unsigned value, so one unsigned max test
// per candidate decides domination *and* the exclusion rule together.
u32 hiA[8], hiAh[8];
for (int e = 0; e < 8; e++) hiA[e] = ((exmask >> e) & 1u) ? 0u : 0x7FFFFFFFu;
for (int e = 8; e < 16; e++) hiAh[e - 8] = ((exmask >> e) & 1u) ? 0u : 0x7FFFFFFFu;
const __m256i notexlo = LDU256(hiA);
const __m256i notexloh = LDU256(hiAh);
const __m256i all8 = _mm256_set1_epi32(-1);
// [x15b2/disp32] one base register; the per-plane offset e*MF_SPL is a
// compile-time constant and therefore a disp32 immediate in the load.
const u8 *const sbase = s_sig + (size_t)d * k * MF_SPL;
const u32 *const odd = s_ord[d];
for (u32 qi = q0; qi < q1; qi++) {
u32 i = fo[qi] & 0xFFFFFu;
#if MF_PFB > 0
{
u32 qj = qi + MF_PFB;
if (qj < q1) {
u32 j = fo[qj] & 0xFFFFFu;
_mm_prefetch((const char *)(s_pm + (size_t)j * STRIDE), _MM_HINT_T0);
_mm_prefetch((const char *)(s_gt[d] + j), _MM_HINT_T0);
_mm_prefetch((const char *)(avpool + (size_t)j * ASTRL), _MM_HINT_T0);
/* [PFB3-OUT / 2.19.339+2.19.344] pass-B's RMW target out[] was absent here: the
body does out[i] += add (lines 779/950) and the block prefetched only the
metadata rows. RMW + 1.2 MB (n=3e5) + lookahead MF_PFB steps. Same cell that
paid -24.1 ms (#106747) / -19.4 ms (#106762, green) on 1015a; the pass-A
store variant on this problem was only -4.5 ms. Pure prefetch, bit-identical. */
__asm__ __volatile__("prefetchw %0" :: "m"(*(const char *)(out + j)));
}
}
#endif
const u32 lo = FPOS(d, fo[qi] >> 20); // [K3a] sequential key, not a cold s_bd line
const u32 hi = s_gt[d][i];
if (lo >= hi) continue;
const u32 *rec = s_pm + (size_t)i * STRIDE;
const u32 *Avp = avpool + (size_t)i * ASTRL;
__m256i qr = _mm256_or_si256(_mm256_load_si256((const __m256i *)rec), khi8v);
__m256i Avm = _mm256_or_si256(LDU256(Avp), notexlo);
__m256i qT = _mm256_min_epi32(qr, Avm);
__m256i qTh;
if (k > 9) {
// k = 10: d can reach 9, so exmask bit 8 is reachable -> keep the real test.
__m256i qrh = _mm256_or_si256(LDU256((rec + 8)), khi8hv);
__m256i Avmh = _mm256_or_si256(LDU256((Avp + 8)), notexloh);
qTh = _mm256_min_epi32(qrh, Avmh);
} else if (k > 8) {
// [AV8] k = 9: expmask stays inside bits 0..7 => hiAh is all-0x7FFFFFFF
// => Avmh is identically 0x7FFFFFFF => qTh = min_epi32(qrh, 0x7FFFFFFF)
// == qrh. avpool lanes 8..15 (and this load + min) are dead code.
qTh = _mm256_or_si256(LDU256((rec + 8)), khi8hv);
} else {
qTh = all8;
}
u32 add = 0;
const u32 *c0 = s_sdmp[d] ? (s_sdmp[d] + (size_t)lo * g_KS) : 0;
if (g_use_filt && KK == 9) {
const u32 w0 = lo >> 6;
const u32 nw = ((hi - 1) >> 6) - w0 + 1;
const u64 wcs = (u64)N / g_Qc + 1;
const u32 FW = g_fbm_W;
const u64 *rows[8];
int nr = 0;
for (int e = 0; e < 9; e++) {
if (e == d) continue;
u32 cell = (u32)((u64)rec[e] / wcs) + 1;
if (cell > g_Qc) cell = g_Qc;
rows[nr++] = s_fbm + ((size_t)(d * 9 + e) * (g_Qc + 1) + cell) * FW + w0;
}
const u64 *r0 = rows[0];
const u64 *r1 = rows[1];
const u64 *r2 = rows[2];
const u64 *r3 = rows[3];
const u64 *r4 = rows[4];
const u64 *r5 = rows[5];
const u64 *r6 = rows[6];
const u64 *r7 = rows[7];
const u32 remh = hi & 63u;
{
u64 vv = r0[0] & r1[0] & r2[0] & r3[0] & r4[0] & r5[0] & r6[0] & r7[0];
vv &= ~0ull << (lo & 63);
if (nw == 1u && remh) vv &= (1ull << remh) - 1;
u32 word = w0;
#if MF_FR_NOCAND
vv = 0;
#endif
while (vv) {
int t = __builtin_ctzll(vv);
vv &= vv - 1;
u32 j = (word << 6) + (u32)t;
const u32 *cp = c0 ? (c0 + (size_t)(j - lo) * g_KS) : (s_pm + (size_t)s_ord[d][j] * STRIDE);
__m256i pv = LDU256(cp);
__m256i pvh = LDU256(cp + 8);
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
ok &= (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, pvh), all8);
add += ok;
}
}
for (u32 w = 1; w + 1 < nw; w++) {
u64 vv = r0[w] & r1[w] & r2[w] & r3[w] & r4[w] & r5[w] & r6[w] & r7[w];
u32 word = w0 + w;
#if MF_FR_NOCAND
vv = 0;
#endif
while (vv) {
int t = __builtin_ctzll(vv);
vv &= vv - 1;
u32 j = (word << 6) + (u32)t;
const u32 *cp = c0 ? (c0 + (size_t)(j - lo) * g_KS) : (s_pm + (size_t)s_ord[d][j] * STRIDE);
__m256i pv = LDU256(cp);
__m256i pvh = LDU256(cp + 8);
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
ok &= (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, pvh), all8);
add += ok;
}
}
if (nw > 1u) {
u32 w = nw - 1u;
u64 vv = r0[w] & r1[w] & r2[w] & r3[w] & r4[w] & r5[w] & r6[w] & r7[w];
if (remh) vv &= (1ull << remh) - 1;
u32 word = w0 + w;
#if MF_FR_NOCAND
vv = 0;
#endif
while (vv) {
int t = __builtin_ctzll(vv);
vv &= vv - 1;
u32 j = (word << 6) + (u32)t;
const u32 *cp = c0 ? (c0 + (size_t)(j - lo) * g_KS) : (s_pm + (size_t)s_ord[d][j] * STRIDE);
__m256i pv = LDU256(cp);
__m256i pvh = LDU256(cp + 8);
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
ok &= (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, pvh), all8);
add += ok;
}
}
out[i] += add;
continue;
}
if (g_use_filt) {
const u32 w0 = lo >> 6;
const u32 nw = ((hi - 1) >> 6) - w0 + 1;
u64 *fb = s_fbuf;
const u64 wcs = (u64)N / g_Qc + 1;
const u32 FW = g_fbm_W;
int first = 1;
#if MF_FR_NOREAD
first = 0;
for (u32 w = 0; w < nw; w++) fb[w] = 0;
#endif
for (int e = 0; e < k; e++) {
if (e == d) continue;
u32 c = (u32)((u64)rec[e] / wcs) + 1;
if (c > g_Qc) c = g_Qc;
const u64 *row = s_fbm + ((size_t)(d * k + e) * (g_Qc + 1) + c) * FW + w0;
if (first) { for (u32 w = 0; w < nw; w++) fb[w] = row[w]; first = 0; }
else { for (u32 w = 0; w < nw; w++) fb[w] &= row[w]; }
}
fb[0] &= ~0ull << (lo & 63);
u32 r2 = hi & 63u;
if (r2) fb[nw - 1] &= (1ull << r2) - 1;
for (u32 w = 0; w < nw; w++) {
u64 vv = fb[w];
#if MF_FR_NOCAND
vv = 0;
#endif
while (vv) {
int t = __builtin_ctzll(vv);
vv &= vv - 1;
u32 j = ((w0 + w) << 6) + (u32)t;
const u32 *cp = c0 ? (c0 + (size_t)(j - lo) * g_KS) : (s_pm + (size_t)s_ord[d][j] * STRIDE);
__m256i pv = LDU256(cp);
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
if (k > 8) {
__m256i pvh = LDU256((cp + 8));
ok &= (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, pvh), all8);
}
add += ok;
}
}
out[i] += add;
continue;
}
if (g_sig_on && (hi - lo) >= 2) {
// ---- coarse byte-signature scan, exact fallback only on ties ----
// (no qtv store: the broadcast signatures are built in the vector domain)
__m256i qsb[16];
// Lane d needs NO test at all: the band is [FPOS(d,bd_d), gt_d(i)) in dim-d
// order, and gt_d(i) is the START of i's tie group, so every candidate in the
// band has x_d[c] < x_d[i] = qT[d] by construction. Testing it anyway made
// nearly every candidate ambiguous -- band members sit within a bucket of the
// query in dim d, so with a 512-wide cell they share q's signature block -- and
// the exact fallback then ate the whole win. Neutralising the lane is EXACT.
{
const __m256i zero8 = _mm256_setzero_si256();
const __m256i shv = _mm256_set1_epi32((int)g_sigsh);
// [f5/setup-hoist] sv depends on the half (e<8) only, not on e itself.
/* [ONEACC] qsb is built from sig-1 so that one OR chain can carry the
three states (0 = strictly less, 1 = tie, >=2 = strictly greater). */
const __m256i bias8 = _mm256_set1_epi8((char)0x80);
const __m256i sv_lo = _mm256_srlv_epi32(qT, shv);
const __m128i u16=_mm_packus_epi32(_mm256_castsi256_si128(sv_lo),_mm256_extracti128_si256(sv_lo,1));
const __m128i u8s=_mm_packus_epi16(u16,u16);
const __m256i packed=_mm256_xor_si256(_mm256_broadcastsi128_si256(u8s),bias8);
for (int e = 0; e < k; e++) {
if (e == (int)d) { qsb[e] = _mm256_set1_epi8((char)0xFF); continue; }
qsb[e] = _mm256_shuffle_epi8(packed,_mm256_set1_epi8((char)e));
}
}
// [f5/nocmp] lane d is provably true for every candidate of this band (the
// [nolane] argument), so the loop below simply skips it -- the branch is
// data-independent and perfectly predicted. The former pre-pass that copied
// the k-1 live planes and their broadcasts into two stack arrays is gone: it
// cost 2*(k-1) stores plus the reload of every ymm per (query,dim), and the
// measured cost of that form on the sibling rows is large (1015a +2.42%,
// 1015b +4.30% for ADDING it -- see #103367 / #103361).
u32 aj = lo, aacc = 0, aexact = 0;
for (; aj + 32 <= hi; aj += 32) {
_mm_prefetch((const char *)(odd + aj + 64), _MM_HINT_T0);
/* [ONEACC] one accumulator. Byte 0 / 1 / >=2 = strictly-less / tie /
strictly-greater, and an OR cannot turn one of those into another.
decm == the old (ltm & ~amb) and amb == the old amb, bit for bit. */
__m256i ac = _mm256_set1_epi8((char)0x80);
for (int e = 0; e < k; e++) {
if (e == (int)d) continue;
__m256i cv = LDU256((sbase + (size_t)e * MF_SPL + aj));
ac = _mm256_max_epi8(ac, _mm256_subs_epi8(cv, qsb[e]));
}
u32 decm = (u32)_mm256_movemask_epi8(ac);
u32 amb = (u32)_mm256_movemask_epi8(_mm256_cmpeq_epi8(ac, _mm256_setzero_si256()));
aacc += (u32)__builtin_popcount(decm);
while (amb) {
int t = __builtin_ctz(amb); amb &= amb - 1;
const u32 *cp = c0 ? (c0 + (size_t)(aj + (u32)t - lo) * g_KS) : (s_pm + (size_t)odd[aj + (u32)t] * STRIDE);
__m256i pv = LDU256(cp);
u32 okl = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
if (k > 8) {
__m256i pvh = LDU256((cp + 8));
okl &= (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, pvh), all8);
}
aacc += okl;
}
}
// ---- tail: ONE overlapping 32-lane chunk, masked. Instrumented counts
// showed (hi-lo) mod 32 = 10.6 % of all candidates, and pairs with
// hi-lo < 32 a further 12 % of pairs, were falling off the signature
// path into the exact per-candidate loop (~5 cycles each vs ~0.6 for
// the vector path). Re-reading the last 32 lanes (overlapping the
// already-counted ones) and masking the movemask fixes that with no
// extra correctness risk: the mask removes exactly the lanes outside
// [lo, hi), and a lane outside that range can only inflate a count.
{
u32 r = hi - aj;
if (r) {
u32 base, lk;
if (hi >= 32u) { base = hi - 32u; lk = 32u - r; }
else { base = 0u; lk = lo; } // hi < 32 => lo+hi<=32
u32 kmask = ((r >= 32u) ? 0xFFFFFFFFu : ((1u << r) - 1u)) << lk;
/* [ONEACC] tail: same one-accumulator form. */
__m256i ac = _mm256_set1_epi8((char)0x80);
for (int e = 0; e < k; e++) {
if (e == (int)d) continue;
__m256i cv = LDU256((sbase + (size_t)e * MF_SPL + base));
ac = _mm256_max_epi8(ac, _mm256_subs_epi8(cv, qsb[e]));
}
u32 decm = ((u32)_mm256_movemask_epi8(ac)) & kmask;
u32 amb = ((u32)_mm256_movemask_epi8(_mm256_cmpeq_epi8(ac, _mm256_setzero_si256()))) & kmask;
aacc += (u32)__builtin_popcount(decm);
while (amb) {
int t = __builtin_ctz(amb); amb &= amb - 1;
const u32 *cp = c0 ? (c0 + (size_t)(base + (u32)t - lo) * g_KS) : (s_pm + (size_t)odd[base + (u32)t] * STRIDE);
__m256i pv = LDU256(cp);
u32 okl = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
if (k > 8) {
__m256i pvh = LDU256((cp + 8));
okl &= (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, pvh), all8);
}
aacc += okl;
}
}
}
add = aacc;
} else if (c0) {
if (k <= 8) {
const u32 *c = c0;
u32 a0 = 0, a1 = 0, a2 = 0, a3 = 0;
u32 j = lo;
for (; j + 4 <= hi; j += 4) {
__m256i p0 = LDU256((c));
__m256i p1 = LDU256((c + g_KS));
__m256i p2 = LDU256((c + 2 * g_KS));
__m256i p3 = LDU256((c + 3 * g_KS));
a0 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p0), all8);
a1 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p1), all8);
a2 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p2), all8);
a3 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p3), all8);
c += 4 * g_KS;
}
for (; j < hi; j++, c += g_KS) {
__m256i pv = LDU256(c);
a0 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
}
add = a0 + a1 + a2 + a3;
} else {
// ---- k>8 fringe: unroll 4x. The k<=8 path below has always been unrolled
// 4x; the k>8 path was left as one row per iteration with a single serial
// `add +=` chain, even though k=9/10 is exactly where the fringe dominates
// (measured at k=10/n=1.5e5: fringe 332 ms = 57 % of the run vs AND 139 ms
// = 24 %). Four independent accumulators + two loads in flight per row.
const u32 *c = c0;
u32 a0 = 0, a1 = 0, a2 = 0, a3 = 0;
u32 j = lo;
for (; j + 4 <= hi; j += 4) {
__m256i p0 = LDU256((c));
__m256i p1 = LDU256((c + g_KS));
__m256i p2 = LDU256((c + 2 * g_KS));
__m256i p3 = LDU256((c + 3 * g_KS));
__m256i h0 = LDU256((c + 8));
__m256i h1 = LDU256((c + g_KS + 8));
__m256i h2 = LDU256((c + 2 * g_KS + 8));
__m256i h3 = LDU256((c + 3 * g_KS + 8));
a0 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p0), all8) & (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, h0), all8);
a1 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p1), all8) & (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, h1), all8);
a2 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p2), all8) & (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, h2), all8);
a3 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p3), all8) & (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, h3), all8);
c += 4 * g_KS;
}
for (; j < hi; j++, c += g_KS) {
__m256i pv = LDU256(c);
__m256i pvh = LDU256((c + 8));
a0 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8) &
(u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, pvh), all8);
}
add = a0 + a1 + a2 + a3;
}
} else {
// Fallback used when the transposed fringe rows are not allocated. NOTE: this
// branch used to test only lanes 0..7, so for k>8 the dims 8..k-1 were never
// compared and the fringe silently OVERCOUNTED (found on the board: k=9 at n=3e5
// returned WA while k=10 happened to pass). MF_NOSDMP=1 is therefore only safe
// with the high-lane test below; keep MF_NOSDMP=0 by default regardless.
for (u32 j = lo; j < hi; j++) {
const u32 *c = s_pm + (size_t)odd[j] * STRIDE;
__m256i pv = _mm256_load_si256((const __m256i *)c);
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
if (k > 8) {
__m256i pvh = _mm256_load_si256((const __m256i *)(c + 8));
ok &= (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, pvh), all8);
}
add += ok;
}
}
out[i] += add;
}
};
if constexpr(KK>0) fringe_dim(std::integral_constant<int,0>{});
if constexpr(KK>1) fringe_dim(std::integral_constant<int,1>{});
if constexpr(KK>2) fringe_dim(std::integral_constant<int,2>{});
if constexpr(KK>3) fringe_dim(std::integral_constant<int,3>{});
if constexpr(KK>4) fringe_dim(std::integral_constant<int,4>{});
if constexpr(KK>5) fringe_dim(std::integral_constant<int,5>{});
if constexpr(KK>6) fringe_dim(std::integral_constant<int,6>{});
if constexpr(KK>7) fringe_dim(std::integral_constant<int,7>{});
if constexpr(KK>8) fringe_dim(std::integral_constant<int,8>{});
if constexpr(KK>9) fringe_dim(std::integral_constant<int,9>{});
}
__attribute__((target("avx2")))
static void solve_mf(u32 N, const unsigned **x, u32 *out, int k) {
++solve_generation; // [对手 #121252] 入口自增：avN 初值 0 ⇒ 首次调用必建（勿移到末尾）
// W padded to 8 words: every (dim,bucket) array then starts on a 64-byte
// boundary and every 32-byte vector load inside a stream is line-contained.
const u32 W = ((N + 63) / 64 + 7u) & ~7u;
g_W = W;
#ifdef MF_SKIP_AND
g_skip_and = 1;
#endif
#ifdef MF_FILT
g_use_filt = 1;
#endif
#ifdef MF_NOFILT
g_use_filt = 0;
#endif
#ifdef MF_Q
g_Q = MF_Q; g_B = (u32)((N + (MF_Q) - 1) / (MF_Q));
#endif
#ifdef MF_FILT
g_use_filt = 1;
#endif
#ifdef MF_NOFILT
g_use_filt = 0;
#endif
#ifdef MF_SKIP_FRINGE
g_skip_fringe = 1;
#endif
if (!g_Q) {
// bucket size ~ 0.82*sqrt(n) balances the pool build (proportional to n^2/B) against the
// fringe scan (proportional to n*B); the pool itself is capped by the memory budget.
u64 r = (u64)N, s2 = 0;
while (s2 * s2 < r) s2++; // ceil(sqrt(n)) without libm
// Reserve: the .bss tables, the coarse-filter bitmaps and (for k>=9, where the
// random s_pm fallback is fatal) the transposed fringe rows.
u64 overhead = (u64)(5 * k + 21) * N * 4;
#if !MF_NOFILTB
// STALE-SHAPE RESERVE (the KG_BASE / CT_MAXV class, on the MEMORY BUDGET rather than a
// buffer). The coarse-filter bitmaps are k*k*(Qc+1)*W*8 bytes, approximated here as
// k*k*4*N. But `#if MF_NOFILTB` sets g_use_filt = 0 UNCONDITIONALLY further down, and
// MF_FILTAUTO's own auto-enable runs AFTER this block -- so on a row shipping
// MF_NOFILTB 1 the bitmaps are never allocated on ANY path, and this reserves
// k*k*4*N = 324 MB at n=1e6/k=9 for memory that cannot be used. The cost is not the
// 324 MB: it is that Qmem = budget/perfill then caps q at 1997 instead of the 2440 this
// engine's own coefficient asks for, i.e. a 22 % coarser grid and ~18 % MORE fringe
// candidates on the phase that is 77 % of the row.
overhead += (u64)k * k * 4 * N;
#endif
// The byte-signature planes are k*k*(N+64) bytes and were NOT charged here, so at
// n=1e6/k=10 the pool was sized ~100 MB too large, the allocation failed, and the
// engine returned WRONG ANSWERS on the board (1016-SIG8, sid 98573, WA at 8.929 s)
// instead of erroring -- base8, which has no planes, was AC on the same row. Charge
// them, and refuse the signature path outright if the planes alone would take too
// large a share of the budget.
overhead += (u64)k * k * ((u64)N + 64);
overhead += (u64)N * ((k <= 8) ? 8u : (u32)k) * 4 * k;
u64 budget = ((u64)MF_BUDGETMB << 20);
if (budget > overhead + ((u64)64 << 20)) budget -= overhead; else budget = (u64)64 << 20;
// MF_PLEN sizes each pooled array to the largest R ever read from it, so the
// pool really used is only ~fill of (k-1)*(Q+1)*W words; charge that instead.
#if MF_PLEN
static const u32 kfill[7] = {72, 67, 62, 58, 54, 50, 46}; // per-array fill, k=4..10
u64 perfill = ((u64)(k - 1) * W * 8) * kfill[k - 4] / 100;
#else
u64 perfill = (u64)(k - 1) * W * 8;
#endif
u64 Qmem = budget / (perfill ? perfill : 1);
if (Qmem < 8) Qmem = 8;
static const u32 kscale[7] = {82, 91, 100, 108, 115, 122, 129}; // sqrt(k/6) in percent, k=4..10
u32 q = (u32)((s2 * MF_QCOEF + 99) / 100);
q = (u32)(((u64)q * kscale[k - 4] + 99) / 100);
if (k == 9 && N >= 900000) q = 1400;
if ((u64)q > Qmem) q = (u32)Qmem;
if (q > N) q = N;
// MAXQ is a SILENT CLIFF: s_maxr is [MAXK][MAXK][MAXQ] and is indexed with `b <= Q`, so
// Q > MAXQ-1 walks into s_pofs/s_plen with correct-looking output. Free insurance.
if (q > (u32)(MAXQ - 1)) q = (u32)(MAXQ - 1);
g_Q = q;
g_B = (N + q - 1) / q;
}
const u32 Q = g_Q, B = g_B;
const u64 bmag = ((1ull << 40) + B - 1) / B;
#if MF_PLEN
g_plen_on = 1; // independent of MF_WTRIM: lengths only, stride stays W
#endif
#if MF_WTRIM
u32 Wpool = W; // MF_WTRIM is KNOWN-BROKEN, see the warning above
#else
const u32 Wpool = W;
#endif
#if MF_FILTAUTO
if (!g_use_filt && B >= 400) g_use_filt = 1; // coarse grid: the filter beats the scan
#endif
if (g_use_filt && (u64)k * k * (g_Qc + 1) * W * 8 > ((u64)700 << 20)) g_use_filt = 0;
#if !MF_FILTAUTO
g_use_filt = 0;
#endif
{
int lo8[8], hi8[8];
for (int e = 0; e < 8; e++) lo8[e] = (e < k) ? 0 : 0x7FFFFFFF;
for (int e = 0; e < 8; e++) hi8[e] = (8 + e < k) ? 0 : 0x7FFFFFFF;
khi8v = LDU256(lo8);
khi8hv = LDU256(hi8);
}
const int K1 = k - 1;
// ---------- per-dimension orders, ranks, tie info ----------
for (int d = 0; d < k; d++) {
const unsigned *xd = x[d];
u32 *od = s_ord[d];
// [v4_orders] gt[i] = start[x_d[i]] and bd[] from start[x_d[i]+1]: value-indexed
// lookups, so the per-point work is two sequential sweeps of xd[] with no random
// od[]/xd[] traffic (the old loop walked od[] reading xd[od[j]] at random and then
// scattered gt[]/s_bd[] writes once per tie group).
for (u32 i = 0; i <= N; i++) s_cntv[i] = 0;
/* [b14ac_ HSPF] the counting-sort histogram is the LAST unprefetched
"sequential index (xd[i]) -> random RMW (s_cntv[v]++)" loop in this engine:
every sibling loop of the same shape already carries a prefetch (PFSC at the
gt[] sweep, PFSC2 at the s_pos scatter). xd[] is read sequentially, so the
target line is known 32 points early. Distance 32 = same as MF_PFSC.
Prefetch only => bit-identical. */
for (u32 i = 0; i < N; i++) {
if (i + 32u < N) { u32 vp = xd[i + 32u]; _mm_prefetch((const char *)(s_cntv + (vp < N ? vp : 0u)), _MM_HINT_T0); }
u32 v = xd[i]; s_cntv[v < N ? v : 0]++;
}
{u32 i=0;__m256i carry=_mm256_setzero_si256(),zero=carry;const __m256i last=_mm256_set1_epi32(7);
for(;i+8<=N+1;i+=8){
__m256i original=LDU256(s_cntv+i),v=original;
v=_mm256_add_epi32(v,_mm256_slli_si256(v,4));
v=_mm256_add_epi32(v,_mm256_slli_si256(v,8));
v=_mm256_add_epi32(v,_mm256_permute2x128_si256(zero,_mm256_shuffle_epi32(v,0xff),0x20));
v=_mm256_add_epi32(v,carry);
__m256i start=_mm256_sub_epi32(v,original);
__asm__ volatile("vmovdqu %1,%0":"=m"(*(__m256i*)(s_cntv+i)):"x"(start));
__asm__ volatile("vmovdqu %1,%0":"=m"(*(__m256i*)(s_tmp+i)):"x"(start));
carry=_mm256_permutevar8x32_epi32(v,last);
}
u32 sum=(u32)_mm_cvtsi128_si32(_mm256_castsi256_si128(carry));
for(;i<=N;i++){u32 c=s_cntv[i];s_cntv[i]=sum;s_tmp[i]=sum;sum+=c;}
}
#if MF_FB2
for (u32 i = 0; i < N; i++) {
#if MF_PFSC2 > 0
if (i + MF_PFSC2 < N) { u32 vp = xd[i + MF_PFSC2]; _mm_prefetch((const char *)(s_tmp + (vp < N ? vp : 0u)), _MM_HINT_T0); }
#endif
u32 v = xd[i]; if (v >= N) v = 0; u32 q = s_tmp[v]++; od[q] = i;
s_posp[(size_t)i * MAXK + d] = q;
}
#else
// s_pos is read ONLY by the non-FB3 coarse-filter build, which is compiled out at
// the shipped MF_FB3=1 (the FB3 path uses s_bnde, and FB2 uses s_posp).
// [y4w NIDFUSE] s_pos[d] IS inverse(s_ord[d]) -- the same permutation the group loop
// used to rebuild into s_nid with 9e6 random stores. Fill it unconditionally here so
// the pool-build OR ring can read s_pos[ds] instead.
{
u32 *pp = s_pos[d];
for (u32 i = 0; i < N; i++) {
#if MF_PFSC2 > 0
if (i + MF_PFSC2 < N) { u32 vp = xd[i + MF_PFSC2]; _mm_prefetch((const char *)(s_tmp + (vp < N ? vp : 0u)), _MM_HINT_T0); }
#endif
u32 v = xd[i]; if (v >= N) v = 0; u32 q = s_tmp[v]++; pp[i] = q;
}
for(u32 i=0;i<N;i++){
#if MF_PFSC2 > 0
if(i+MF_PFSC2<N)_mm_prefetch((const char*)(od+pp[i+MF_PFSC2]),_MM_HINT_T0);
#endif
od[pp[i]]=i;
}
}
#endif
{ u32 *gt = s_gt[d];
for (u32 i = 0; i < N; i++) {
#if MF_PFSC > 0
// [PFSC] s_cntv[v] and s_cntv[v+1] are one line, fetched at a random offset
// once per point, on the critical path of the store below. xd[] is sequential
// here, so v is known MF_PFSC points early -- issue the line fetch ahead.
if (i + MF_PFSC < N) { u32 vp = xd[i + MF_PFSC]; _mm_prefetch((const char *)(s_cntv + (vp < N ? vp : 0u)), _MM_HINT_T0); }
#endif
u32 v = xd[i]; if (v >= N) v = 0;
gt[i] = s_cntv[v];
u32 num = s_cntv[v + 1] - 1u; if (num > N) num = N;
u32 bb = (u32)(((u64)num * bmag) >> 40);
u32 bbq = bb > Q - 1 ? Q - 1 : bb;
// [TRANS] point-major store is produced by the blocked transpose after this loop
s_bdT[(size_t)d * E6Z_BDR + i] = bbq;
} }
BVAL(d, 0) = 0; FPOS(d, 0) = 0;
for (u32 b = 1; b < Q; b++) {
u32 pos = b * B < N ? b * B : N - 1;
u32 v = xd[od[pos]];
BVAL(d, b) = v;
u32 gs = pos;
while (gs > 0 && xd[od[gs - 1]] == v) gs--;
FPOS(d, b) = gs;
}
BVAL(d, Q) = 0xFFFFFFFFu; FPOS(d, Q) = 0;
}
// [TRANS] one blocked transpose s_bdT[d][i] -> s_bd[i][d].
// Reads: 9 sequential streams over the dim-major rows. Writes: 64 points x 10 lanes
// = 1280 contiguous bytes per block, so every 64-B line of s_bd is written WHOLE
// (no read-for-ownership, no partial writeback) -- what the 9 strided passes cost.
for (u32 i0 = 0; i0 < N; i0 += 64) {
u32 i1 = i0 + 64; if (i1 > N) i1 = N;
for (u32 i = i0; i < i1; i++) {
u16 *dst = s_bd + (size_t)i * MAXK;
for (int dd = 0; dd < k; dd++) dst[dd] = s_bdT[(size_t)dd * E6Z_BDR + i];
}
}
for (u32 i = 0; i < N; i++) {
u32 *p = s_pm + (size_t)i * STRIDE;
for (int d = 0; d < k; d++) p[d] = x[d][i];
for (int d = k; d < STRIDE; d++) p[d] = 0;
}
// ---------- byte-signature planes for the fringe coarse filter ----------
// s_sig[d][e*N + j] = (u8)(x[e][ od_d[j] ] >> SIGSH) (od_d = dim-d order)
{
u32 nn = N - 1; u32 sh = 0;
while (nn > 255u) { nn >>= 1; sh++; } // smallest sh with (N-1)>>sh <= 255
g_sigsh = sh;
size_t need = (size_t)k * k * MF_SPL;
static u8 *sigpool = 0; static size_t sigcap = 0;
// Refuse the signature path when the planes alone exceed 220 MB: past that the pool
// it competes with is squeezed and the row is better served by the exact path.
if (need > ((size_t)220 << 20) || (size_t)N + 32 > MF_SPL) { sigpool = 0; sigcap = 0; }
else if (need > sigcap) { sigpool = (u8 *)pool_alloc(need); sigcap = sigpool ? need : 0; }
if (sigpool) {
s_sig = sigpool;
// The plane build is DEFERRED and merged into the s_sdmp build pass below when
// s_sdmp is allocated: both walk the same `s_pm + od[j]*STRIDE` rows, so two
// passes pay two rounds of random 64-byte reads for one round of useful work.
// ⚠ SAFETY GATE. The signature path is VERIFIED CORRECT (brute force k=4..10 x 4
// distributions, plus checksum-identical to the base engine) for SMALL bucket sizes,
// but at large B it returns WRONG ANSWERS -- reproduced twice each way, real judge:
// k=6 n=261000 B=326 (QCOEF 800) checksum 1070791438 = base engine CORRECT
// k=6 n=261000 B=428 (QCOEF 610) checksum 1064212397 != base WRONG
// k=6 n=261000 B=652 (QCOEF 400) checksum 1060739010 != base WRONG
// and the board agrees: 1012b/1013b/1014b (n=1e5, B=259) AC; 1013a (n=3e5, B=416)
// and 1016 (n=1e6, B=842) both WA. The threshold sits between B=326 and B=428.
// Root cause NOT yet localised (lane-d neutralisation, the masked tail, and the
// exact-tail variant were each ruled out by checksum -- all give the same wrong
// value, so the defect is in the coarse scan or the planes themselves).
// UNTIL IT IS FOUND, REFUSE THE SIGNATURE PATH ABOVE A MEASURED-SAFE B.
g_sig_on = 1;
g_sig_merged = 0;
}
}
// ---------- coarse superset bitmaps over every dim order (fringe filter) ----------
#if MF_NOFILTB
g_use_filt = 0;
#endif
#if MF_FB3
if (g_use_filt) {
u32 Qc = g_Qc;
u64 wc = (u64)N / Qc + 1;
for (int e = 0; e < k; e++) {
const unsigned *xe = x[e];
const u32 *pe = s_ord[e];
u32 ptr = 0;
u32 *bn = s_bnde + (size_t)e * (MAXQ + 2);
for (u32 c = 0; c <= Qc; c++) {
u64 v = (u64)c * wc;
if (v > 0xFFFFFFFFull) v = 0xFFFFFFFFull;
while (v && ptr < N && (u64)xe[pe[ptr]] < v) ptr++;
bn[c] = ptr;
}
}
}
#endif
if (g_use_filt) {
u32 Qc = g_Qc;
u64 wc = (u64)N / Qc + 1;
size_t need2 = (size_t)k * k * (Qc + 1) * W * sizeof(u64);
static u64 *fpool = 0; static size_t fcap = 0;
if (need2 > fcap) { fpool = (u64 *)pool_alloc(need2 + 4096); fcap = need2; }
if (fpool) {
s_fbm = fpool; g_fbm_W = W;
#if MF_FB2
// Sweep the e-order ONCE per dim e, keeping (k-1) running bitsets (one per
// target dim d), and copy them out at each coarse-cell boundary. The old
// shape re-walked all N points for every one of the k(k-1) (d,e) pairs with
// two L3-random reads each (xe[pe[ptr]] and s_pos[d][pe[ptr]]); here the
// rank record is point-major so one 64B line yields every dim's rank, which
// cuts the random reads by ~k and the whole build by ~2-2.5x at k>=8.
for (int d = 0; d < k; d++)
for (int e = 0; e < k; e++) {
if (e == d) continue;
u64 *b0 = s_fbm + (size_t)(d * k + e) * (Qc + 1) * W;
for (u32 w = 0; w < W; w++) b0[w] = 0;
}
for (int e = 0; e < k; e++) {
const unsigned *xe = x[e];
const u32 *pe = s_ord[e];
int dmap[MAXK], km1 = 0;
for (int d = 0; d < k; d++) if (d != e) dmap[km1++] = d;
for (int i = 0; i < km1; i++) { u64 *a = s_facc + (size_t)i * W; for (u32 w = 0; w < W; w++) a[w] = 0; }
u32 ptr = 0;
for (u32 c = 1; c <= Qc; c++) {
u64 v = (u64)c * wc;
if (v > 0xFFFFFFFFull) v = 0xFFFFFFFFull;
while (ptr < N && (u64)xe[pe[ptr]] < v) {
const u32 *pv = s_posp + (size_t)pe[ptr] * MAXK;
for (int i = 0; i < km1; i++) {
u32 q = pv[dmap[i]];
s_facc[(size_t)i * W + (q >> 6)] |= 1ull << (q & 63);
}
ptr++;
}
for (int i = 0; i < km1; i++) {
int d = dmap[i];
u64 *dst = s_fbm + ((size_t)(d * k + e) * (Qc + 1) + c) * W;
const u64 *src = s_facc + (size_t)i * W;
#if MF_NT
{ u32 w = 0;
for (; w + 4 <= W; w += 4) _mm256_stream_si256((__m256i *)(dst + w), _mm256_load_si256((const __m256i *)(src + w)));
for (; w < W; w++) dst[w] = src[w]; }
#else
for (u32 w = 0; w < W; w++) dst[w] = src[w];
#endif
}
}
}
#else
for (int d = 0; d < k; d++) {
for (int e = 0; e < k; e++) {
if (e == d) continue;
const unsigned *xe = x[e];
const u32 *pe = s_ord[e];
const u32 *pd = s_pos[d];
u64 *base = s_fbm + (size_t)(d * k + e) * (Qc + 1) * W;
for (u32 w = 0; w < W; w++) base[w] = 0;
u64 *cur = s_acc;
for (u32 w = 0; w < W; w++) cur[w] = 0;
u32 ptr = 0;
for (u32 c = 1; c <= Qc; c++) {
#if MF_FB3
u32 pend = s_bnde[(size_t)e * (MAXQ + 2) + c];
#else
u64 v = (u64)c * wc;
if (v > 0xFFFFFFFFull) v = 0xFFFFFFFFull;
u32 pend = ptr;
{ const unsigned *xe_ = xe; const u32 *pe_ = pe;
while (pend < N && (u64)xe_[pe_[pend]] < v) pend++; }
#endif
while (ptr < pend) { u32 q = pd[pe[ptr]]; cur[q >> 6] |= 1ull << (q & 63); ptr++; }
u64 *dst = base + (size_t)c * W;
#if MF_NT
{ u32 w = 0;
for (; w + 4 <= W; w += 4) _mm256_stream_si256((__m256i *)(dst + w), _mm256_load_si256((const __m256i *)(cur + w)));
for (; w < W; w++) dst[w] = cur[w]; }
#else
for (u32 w = 0; w < W; w++) dst[w] = cur[w];
#endif
}
}
}
#endif
} else { g_use_filt = 0; }
_mm_sfence();
}
// ---------- fold dimension + bucket vector per query ----------
{
size_t mrn = (size_t)MAXK * MAXK * MAXQ;
for (size_t z = 0; z < mrn; z++) s_maxr[z] = 0;
}
// [FOLDBLK] the argmin pass and the maxr-reduction pass are split and blocked: the
// reduction's table is only 252 KB (7 ds x 7 d x 1512 b) but the argmin streams 28 MB of
// s_gt through L2 right next to it, so every one of the 6e6 conditional stores paid an
// L3/DRAM round trip. Blocking keeps the landing zone resident; the fold result is
// bit-identical (same max reduction, same values, same s_g).
{
static u32 y2_dsb[1024], y2_bst[1024];
for (u32 i0 = 0; i0 < N; i0 += 1024) {
u32 i1 = i0 + 1024; if (i1 > N) i1 = N;
for (u32 i = i0; i < i1; i++) {
u32 best = 0xFFFFFFFFu; int ds = 0;
for (int d = 0; d < k; d++) {
u32 g = s_gt[d][i];
if (g < best) { best = g; ds = d; }
}
y2_dsb[i - i0] = (u32)ds;
y2_bst[i - i0] = best;
s_g[i] = (u32)ds;
}
if (g_plen_on) {
// Largest R that will ever be read out of each (fold dim, dim, bucket) array:
// the pooled array (ds,d,b) is only ever scanned over [0, maxR] words, so the
// per-array length can be far below the group maximum (0.38n vs 0.93n at k=10).
for (u32 i = i0; i < i1; i++) {
u32 ds = y2_dsb[i - i0];
u32 bb = y2_bst[i - i0];
const u16 *bdv = s_bd + (size_t)i * MAXK;
u32 *mr = s_maxr + ((size_t)ds * MAXK) * MAXQ;
for (int d = 0; d < k; d++) {
if (d == ds) continue;
u32 b = bdv[d];
if (bb > mr[(size_t)d * MAXQ + b]) mr[(size_t)d * MAXQ + b] = bb;
}
}
}
}
}
for (u32 i = 0; i < N; i++) s_qord[i] = i;
// group by ds
{
for (u32 v = 0; v <= (u32)k; v++) s_cntv[v] = 0;
for (u32 i = 0; i < N; i++) s_cntv[s_g[i] + 1]++;
{ u32 ac = 0; for (u32 v = 0; v <= (u32)k; v++) { u32 c = s_cntv[v]; s_cntv[v] = ac; ac += c; } }
for (u32 i = 0; i < N; i++) { u32 id = s_qord[i]; s_tmp[s_cntv[s_g[id] + 1]++] = id; }
for (u32 i = 0; i < N; i++) s_qord[i] = s_tmp[i];
}
u32 gstart[MAXK + 2];
{ u32 c = 0; for (int d = 0; d <= k; d++) { gstart[d] = c; while (c < N && (int)s_g[s_qord[c]] == d) c++; } gstart[k + 1] = c; }
// [FRORD] Reuse each global coordinate order, partitioning once by fold group.
// The preexisting s_bdT holds each point's exact bucket in a compact column.
for (int d = 0; d < k; d++) {
u32 pos[MAXK];
for (int ds = 0; ds < k; ds++) pos[ds] = gstart[ds];
u32 bcap_ = (N - 1) / B; if (bcap_ > Q - 1) bcap_ = Q - 1;
u32 bb_ = 0;
for (u32 r = 0; r < N; r++) {
while (bb_ < bcap_ && r >= FPOS(d, bb_ + 1u)) bb_++;
u32 id = s_ord[d][r];
u32 dst = pos[s_g[id]]++;
s_frord[d][dst] = id | (bb_ << 20);
}
}
// ---------- transposed coordinate rows (sequential fringe) ----------
#if MF_NOSDMP
g_nosdmp = 1;
#endif
if (!g_nosdmp) {
u32 KS = k;
#if MF_KSPAD
if (k <= 8) KS = 8; // 32-byte aligned candidate rows for k<=8
#endif
size_t per = (size_t)N * KS * 4;
size_t lim = (size_t)150 << 20;
if (k >= 9) lim = (size_t)470 << 20; // k=9/10 need the rows: the random s_pm fallback is fatal
if (per * k <= lim) {
static u32 *pool = 0; static size_t cap = 0;
if (per * k > cap) { pool = (u32 *)pool_alloc(per * k + 256); cap = per * k; }
if (pool) {
g_KS = KS;
for (int d = 0; d < k; d++) {
s_sdmp[d] = pool + (size_t)d * N * g_KS;
const u32 *od = s_ord[d];
u32 *dst = s_sdmp[d];
const u32 KSx = g_KS;
for (u32 j = 0; j < N; j++) {
#if MF_PFB > 0
if (j + MF_PFB < N) _mm_prefetch((const char *)(s_pm + (size_t)od[j + MF_PFB] * STRIDE), _MM_HINT_T0);
#endif
const u32 *row = s_pm + (size_t)od[j] * STRIDE;
u32 *dp = dst + (size_t)j * KSx;
for (u32 e = 0; e < KSx; e++) dp[e] = (e < (u32)k) ? row[e] : 0u;
if (s_sig) {
u8 *sb = s_sig + (size_t)d * k * MF_SPL;
for (int e = 0; e < k; e++) { u32 z_ = row[e] >> g_sigsh; sb[(size_t)e * MF_SPL + j] = (u8)(z_ ^ 0x80u); }
}
}
if (s_sig) g_sig_merged = 1;
}
}
}
}
// ---------- signature planes, standalone only if the s_sdmp pass did not run ----
if (s_sig && !g_sig_merged && k==8) {
static u8 cached_signature[(size_t)MAXN*8] __attribute__((aligned(64)));
for(u32 i=0;i<N;i++)for(int e=0;e<8;e++){u32 v=x[e][i]>>g_sigsh;cached_signature[(size_t)i*8+e]=(u8)(v ^ 0x80u);}
for(int d=0;d<k;d++) {
const u32 *od=s_ord[d];
u8 *base=s_sig+(size_t)d*k*MF_SPL;
u32 j=0;
for(;j+8<=N;j+=8) {
if(j+64<N)_mm_prefetch((const char *)(cached_signature+(size_t)od[j+64]*8),_MM_HINT_T0);
__m128i r0=_mm_loadl_epi64((const __m128i *)(cached_signature+(size_t)od[j+0]*8));
__m128i r1=_mm_loadl_epi64((const __m128i *)(cached_signature+(size_t)od[j+1]*8));
__m128i r2=_mm_loadl_epi64((const __m128i *)(cached_signature+(size_t)od[j+2]*8));
__m128i r3=_mm_loadl_epi64((const __m128i *)(cached_signature+(size_t)od[j+3]*8));
__m128i r4=_mm_loadl_epi64((const __m128i *)(cached_signature+(size_t)od[j+4]*8));
__m128i r5=_mm_loadl_epi64((const __m128i *)(cached_signature+(size_t)od[j+5]*8));
__m128i r6=_mm_loadl_epi64((const __m128i *)(cached_signature+(size_t)od[j+6]*8));
__m128i r7=_mm_loadl_epi64((const __m128i *)(cached_signature+(size_t)od[j+7]*8));
__m128i t0=_mm_unpacklo_epi8(r0,r1);
__m128i t1=_mm_unpacklo_epi8(r2,r3);
__m128i t2=_mm_unpacklo_epi8(r4,r5);
__m128i t3=_mm_unpacklo_epi8(r6,r7);
__m128i u0=_mm_unpacklo_epi16(t0,t1);
__m128i u1=_mm_unpackhi_epi16(t0,t1);
__m128i u2=_mm_unpacklo_epi16(t2,t3);
__m128i u3=_mm_unpackhi_epi16(t2,t3);
__m128i v0=_mm_unpacklo_epi32(u0,u2);
__m128i v1=_mm_unpackhi_epi32(u0,u2);
__m128i v2=_mm_unpacklo_epi32(u1,u3);
__m128i v3=_mm_unpackhi_epi32(u1,u3);
__m128i h0=_mm_unpackhi_epi8(r0,r1);
__m128i h1=_mm_unpackhi_epi8(r2,r3);
__m128i h2=_mm_unpackhi_epi8(r4,r5);
__m128i h3=_mm_unpackhi_epi8(r6,r7);
__m128i hu0=_mm_unpacklo_epi16(h0,h1),hu1=_mm_unpacklo_epi16(h2,h3);
__m128i v4=_mm_unpacklo_epi32(hu0,hu1);
_mm_storel_epi64((__m128i *)(base+(size_t)0*MF_SPL+j),v0);
_mm_storel_epi64((__m128i *)(base+(size_t)1*MF_SPL+j),_mm_srli_si128(v0,8));
_mm_storel_epi64((__m128i *)(base+(size_t)2*MF_SPL+j),v1);
_mm_storel_epi64((__m128i *)(base+(size_t)3*MF_SPL+j),_mm_srli_si128(v1,8));
_mm_storel_epi64((__m128i *)(base+(size_t)4*MF_SPL+j),v2);
_mm_storel_epi64((__m128i *)(base+(size_t)5*MF_SPL+j),_mm_srli_si128(v2,8));
_mm_storel_epi64((__m128i *)(base+(size_t)6*MF_SPL+j),v3);
_mm_storel_epi64((__m128i *)(base+(size_t)7*MF_SPL+j),_mm_srli_si128(v3,8));
}
for(;j<N;j++) {
const u8 *row=cached_signature+(size_t)od[j]*8;
for(int e=0;e<k;e++)base[(size_t)e*MF_SPL+j]=row[e];
}
}
g_sig_merged=1;
}
if (s_sig && !g_sig_merged) {
for (int d = 0; d < k; d++) {
const u32 *od = s_ord[d];
u8 *base = s_sig + (size_t)d * k * MF_SPL;
for (u32 j = 0; j < N; j++) {
#if MF_PFB > 0
if (j + MF_PFB < N) _mm_prefetch((const char *)(s_pm + (size_t)od[j + MF_PFB] * STRIDE), _MM_HINT_T0);
#endif
const u32 *row = s_pm + (size_t)od[j] * STRIDE;
for (int e = 0; e < k; e++) { u32 z_ = row[e] >> g_sigsh; base[(size_t)e * MF_SPL + j] = (u8)(z_ ^ 0x80u); }
}
}
}
// ---------- pool ----------
u64 poolwords = (u64)K1 * (Q + 1) * W;
#if MF_PLEN
if (g_plen_on) {
u64 best = 0;
for (int dsx = 0; dsx < k; dsx++) {
u64 tot = 0;
for (int e = 0; e < K1; e++) {
int d = (e < dsx) ? e : e + 1;
const u32 *mr = s_maxr + ((size_t)dsx * MAXK + d) * MAXQ;
for (u32 b = 0; b <= Q; b++) {
u32 RR = mr[b];
u32 len = ((RR >> 6) + 8u) & ~7u;
if (len > W) len = W;
tot += len;
}
}
if (tot > best) best = tot;
}
if (best && best < poolwords) poolwords = best;
}
#endif
size_t need = (size_t)poolwords * sizeof(u64);
static u64 *pool = 0; static size_t cap2 = 0;
if (need > cap2) { pool = (u64 *)pool_alloc(need + 4096); cap2 = need; }
s_bs = pool;
#if MF_INCA
/* [INCA-S] 定扎车道顺序流：每群一条、共 k 条（k-1 条共享 d1=0 的走查序）。
★ 在本 block **之外**先算好 budget/Q（见上），这里只分配，不参与任何 Qmem/B 计算。 */
{
size_t needho = (size_t)N * sizeof(u32) + 4096;
if (needho > s_ho_cap) { s_ho = (u32 *)pool_alloc(needho); s_ho_cap = s_ho ? needho : 0; }
g_inca = (s_ho && (u64)N <= (u64)AS_WORDS * 64ull) ? 1 : 0;
}
#endif
// ---------- groups ----------
for (int ds = 0; ds < k; ds++) {
u32 q0 = gstart[ds], q1 = gstart[ds + 1];
if (q0 >= q1) continue;
#if MF_WTRIM
{
u32 mx = 1;
for (u32 qi = q0; qi < q1; qi++) { u32 rr = s_gt[ds][s_qord[qi]]; if (rr > mx) mx = rr; }
u32 wp = ((mx >> 6) + 8u) & ~7u;
Wpool = (wp < W) ? wp : W;
}
#endif
#if MF_PLEN
// Per-(dim,bucket) array lengths inside the group.
if (g_plen_on) {
u64 tot = 0;
for (int e = 0; e < K1; e++) {
int d = (e < ds) ? e : e + 1;
const u32 *mr = s_maxr + ((size_t)ds * MAXK + d) * MAXQ;
u32 *po = s_pofs + (size_t)e * MAXQ;
u32 *pl = s_plen + (size_t)e * MAXQ;
for (u32 b = 0; b <= Q; b++) {
// NOTE: bucket 0 is the EMPTY prefix set (all-zero array), but a query whose
// bd[d]==0 still scans [0,R) words of it, so the array must be long enough --
// sizing it to the fixed 8-word minimum reads past the zeroed region into the
// next array. Use the real per-bucket max R here, not 0.
u32 RR = mr[b];
u32 len = ((RR >> 6) + 8u) & ~7u;
if (len > Wpool) len = Wpool;
po[b] = (u32)tot; pl[b] = len; tot += len;
}
}
if (tot > (u64)K1 * (Q + 1) * W) { g_plen_on = 0; } // never; safety
}
#endif
// [y4w NIDFUSE] bit numbering = rank in dim ds. s_pos[ds] is exactly that inverse
// permutation (filled once per dim in the order phase); the per-group N-random-store
// rebuild that used to happen here is redundant (judge price of the same knife on the
// 1014a/1015a siblings: 22.34 Mc ~= 5.3 ms there; here k*N = 9e6 stores).
const u32 *const spp = s_pos[ds];
for (int e = 0; e < K1; e++) {
int d = (e < ds) ? e : e + 1;
const unsigned *xd = x[d];
const u32 *od = s_ord[d];
#if MF_INCA
/* [INCA-S] 定扎车道（d == d1）：该 fine 平面的**唯一**消费者是 pass A 的 ASCR 整面拷贝
（pass B 只读 s_fbm/s_sdmp/s_pm/s_gt/s_bd/avpool；`s_bs` 的读点全在 query_group 的
pass A 与 PF_DIST 预取里），故这里改为：**不落盘**，把这条走查的取数（spp[od[j]]，
本来就要做）按同一顺序写进顺序流。第 j 个值 ≡ 原走查第 j 次 OR 进 cur 的那个 q。 */
if (g_inca && d == ((ds == 0) ? 1 : 0)) {
u32 *dstho = s_ho;
const u32 *hp = spp;
for (u32 j = 0; j < N; j++) dstho[j] = hp[od[j]];
continue;
}
#endif
u64 *base = g_plen_on ? s_bs : (s_bs + (size_t)e * (Q + 1) * Wpool);
u64 *cur = s_acc;
for (u32 w = 0; w < Wpool; w++) cur[w] = 0;
if (g_plen_on) {
// bucket 0 is the empty prefix set; bd[] can be 0 so it must be materialised as zeros
u64 *d0 = s_bs + s_pofs[(size_t)e * MAXQ];
u32 l0 = s_plen[(size_t)e * MAXQ];
for (u32 w = 0; w < l0; w++) d0[w] = 0;
}
u32 ptr = 0;
#if MF_BUILD_NOPOOL
while (ptr < N) ptr++;
#else
for (u32 b = 1; b <= Q; b++) {
// {q : x_d[q] < BVAL(d,b)} is EXACTLY the prefix [0,FPOS(d,b)) of the dim-d order
// (FPOS is the tie-group start containing rank b*B), so the per-point value compare
// -- one random xd read per point per (ds,d) pair, k(k-1)N of them -- is redundant.
// b==Q means "every point" and FPOS(d,Q) is the 0 sentinel, hence N.
// Credited to agent a7f799ceb7e63b0cd (worth 4-5% at k=4/5 on the board).
u32 pend = (b < Q) ? FPOS(d, b) : (u32)N;
while (ptr < pend) {
/* [b14ac_ ORPF] the loop chain is ptr -> od[ptr] -> spp[od[ptr]] (a random
4 MB read) -> RMW into cur. The index stream od[] is sequential, so the
value load can be issued K iterations early; prefetch only, bit-identical. */
u32 nx = ptr + 32u; if (nx >= N) nx = ptr;
_mm_prefetch((const char *)&spp[od[nx]], _MM_HINT_T0);
u32 q = spp[od[ptr]]; cur[q >> 6] |= 1ull << (q & 63); ptr++; }
u64 *dst = g_plen_on ? (base + s_pofs[(size_t)e * MAXQ + b])
: (base + (size_t)b * Wpool);
u32 wlen = g_plen_on ? s_plen[(size_t)e * MAXQ + b] : Wpool;
#if MF_NT
// The pool is written once and read 89 GB later, so a plain copy pays a
// read-for-ownership DRAM read per line for nothing. NT stores remove it
// (measured: this loop was 4.58 GB / ~1.7 s, i.e. 2.7 GB/s, vs 12.5 GB/s
// for a plain memset).
{
u32 w = 0;
for (; w + 4 <= wlen; w += 4)
_mm256_stream_si256((__m256i *)(dst + w), _mm256_load_si256((const __m256i *)(cur + w)));
for (; w < wlen; w++) dst[w] = cur[w];
}
#else
for (u32 w = 0; w < wlen; w++) dst[w] = cur[w];
#endif
}
_mm_sfence();
#endif
}
query_group<8>(N, out, ds, q0, q1, Q, Wpool);
}
}
void count_8d(int n, const unsigned *x[8], unsigned *out) { solve_mf((u32)n, (const unsigned **)x, out, 8); }
#ifdef LOCAL_TEST
static void brute_nd(int n, const u32 **x, u32 *out, int k) {
for (int i = 0; i < n; i++) {
u32 c = 0;
for (int j = 0; j < n; j++) {
int ok = 1;
for (int d = 0; d < k; d++) if (!(x[d][j] < x[d][i])) { ok = 0; break; }
c += ok;
}
out[i] = c;
}
}
int main(int argc, char **argv) {
int k = (argc > 1) ? atoi(argv[1]) : 6;
int n = (argc > 2) ? atoi(argv[2]) : 200;
int seed = (argc > 3) ? atoi(argv[3]) : 1;
int mode = (argc > 4) ? atoi(argv[4]) : 0;
int qq = (argc > 5 && atoi(argv[5]) > 0) ? atoi(argv[5]) : 0;
g_Q = qq ? (u32)qq : (u32)(n / 250 + 1);
g_B = (u32)((n + g_Q - 1) / g_Q);
if (argc > 6) g_nosort = atoi(argv[6]);
if (argc > 7) g_nosdmp = atoi(argv[7]);
if (argc > 8) g_skip_and = atoi(argv[8]);
if (argc > 9) g_skip_fringe = atoi(argv[9]);
if (argc > 10) g_use_filt = atoi(argv[10]);
if (argc > 11) g_lexsort = atoi(argv[11]);
const int dm = (mode >= 10) ? mode - 10 : mode;
srand(seed);
static u32 *xs[10];
u32 *out = (u32 *)malloc(sizeof(u32) * n);
u32 *ref = (u32 *)malloc(sizeof(u32) * n);
for (int d = 0; d < k; d++) {
xs[d] = (u32 *)malloc(sizeof(u32) * n);
for (int i = 0; i < n; i++) {
if (dm == 0) xs[d][i] = (u32)(rand() % n);
else if (dm == 1) xs[d][i] = (u32)(rand() % 3);
else if (dm == 2) xs[d][i] = 0;
else if (dm == 3) xs[d][i] = (u32)(n - 1 - (rand() % n));
else if (dm == 4) xs[d][i] = (u32)(i);
else xs[d][i] = (u32)(rand() % n);
}
}
if (mode >= 10) {
struct timespec t0, t1;
clock_gettime(CLOCK_MONOTONIC, &t0);
switch (k) {
case 4: count_4d(n, (const unsigned **)xs, out); break;
case 5: count_5d(n, (const unsigned **)xs, out); break;
case 6: count_6d(n, (const unsigned **)xs, out); break;
case 7: count_7d(n, (const unsigned **)xs, out); break;
case 8: count_8d(n, (const unsigned **)xs, out); break;
case 9: count_9d(n, (const unsigned **)xs, out); break;
default: count_10d(n, (const unsigned **)xs, out); break;
}
clock_gettime(CLOCK_MONOTONIC, &t1);
double ms = (t1.tv_sec - t0.tv_sec) * 1e3 + (t1.tv_nsec - t0.tv_nsec) / 1e6;
u64 s = 0; for (int i = 0; i < n; i++) s += out[i];
printf("k=%d n=%d Q=%u TIME %.1f ms checksum %llu\n", k, n, g_Q, ms, s);
return 0;
}
switch (k) {
case 4: count_4d(n, (const unsigned **)xs, out); break;
case 5: count_5d(n, (const unsigned **)xs, out); break;
case 6: count_6d(n, (const unsigned **)xs, out); break;
case 7: count_7d(n, (const unsigned **)xs, out); break;
case 8: count_8d(n, (const unsigned **)xs, out); break;
case 9: count_9d(n, (const unsigned **)xs, out); break;
default: count_10d(n, (const unsigned **)xs, out); break;
}
brute_nd(n, (const u32 **)xs, ref, k);
int bad = 0;
for (int i = 0; i < n; i++) if (out[i] != ref[i]) { if (bad < 5) printf("MISMATCH i=%d got=%u ref=%u\n", i, out[i], ref[i]); bad++; }
printf("k=%d n=%d mode=%d Q=%u %s (%d mismatches)\n", k, n, mode, g_Q, bad ? "FAIL" : "OK", bad);
return bad != 0;
}
#endif
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 4.809 s | 728 MB + 848 KB | Accepted | Score: 100 | 显示更多 |