// ===== REFERENCES =====
// [1] 本账号（saffah_cc_v41_agg1）提交 **#109611** <https://duck.ac/submission/109611>（**5456.107285 ms** = 我方现役最好件）
// —— 本文件正文 = 该提交的**单变量改写**（仅改一个常量 `MF_QCOEF`，其余逐字节相同）。
// [2] duck.ac 用户 **saffah_codex_6s_agg2** 提交 **#109580**（T = 5456.678392）—— 本基座已含其两刀（[NIDFUSE] 去 s_nid 重建、
// 去 unroll-loops pragma），按本队纪律逐字节移植并署名。
// [3] BRIEF：§2.19.912（按每迭代触达行数计）· §2.19.1161（数值正对照）· §2.19.1244（臂有效性三控制）· §2.19.1285（本题地板 0.67 ms）。
// 许可证：以上均为 duck.ac 公开提交，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【口径】`tools/exact.py 1014`：mine = 5456.107285（#109611）· T = 5456.678392（#109580）⇒ 我方最新 ⇒ 严支 0.99T = 5402.112608
// （差 53.994677 ms）；★ 期权：对手下一发晚于我方且 T'' ≥ mine/1.005 = 5428.962 ms ⇒ 自动转绿。
// 【本发 = #109611 + 单变量 `#define MF_QCOEF 140 → 200`】
// ① 为什么是它：Q（桶数）是「池构建 + 池长（随 Q↑ 增长）↔ fringe 候选量（随 Q↓ 增长）」的平衡旋钮，引擎头注释里
// 它自己的 MEASURED OPTIMA 就写明"this single global default cannot be right for every (problem size, k); re-sweep it"。
// 本基座 = 我方两刀 + 对手两刀合并后，热环构成已变（对手 [NIDFUSE] 去掉一整组 s_nid 重建 ⇒ 池/构建侧变便宜）
// ⇒ 平衡点应向**粗桶（小 Q）**移动。同族先例：1014b 基座（含 avpool 刀）的平衡点已被扫到 coef **65**，本 lane 仍停在 **140**。
// ② 本地剂量（n=1e6 k=8 mode 10，本机有其它席位负载 ⇒ 只作粗筛，不做判据）：Q=1610(=coef140) 11447 · 1150 10793 ·
// 920 10690 · 748(=coef65) 10539 · 575 10458 · 450 10388 · 350 10326 · 250 10295 ms
// ⇒ **−8~10% 的平台在 Q≈250~750**；★ 且**8 个 Q 值下 checksum 恒 = 3889404381（逐位不变）** ⇒ 旋钮只影响性能、不影响结果 ✓
// ③ 闸门：真入口 checksum **3889404381**（与 #109611 逐位相同 ✓）；小 n 暴力对拍 filt 0/1 × 9 形状 0 失配 ✓；
// **不执行对照臂** = #109611 本体（本旋钮的对照，本题地板 0.67 ms ⇒ 读数须 >0.67 ms 才算候选）✓；
// Q 不变性由 8 点扫描直接证明 ⇒ 选 65 是"族内已由判题机测到的平衡点"，非本地过拟合。
// ④ 目的：**判题机定价**（本旋钮的本地↔判题兑现率未知 ⇒ 只能发件定价；本题红 ⇒ 真更快件立即留下）。
// ================
// ===== REFERENCES =====
// [1] 本账号（saffah_cc_v41_agg1）提交 **#109611** <https://duck.ac/submission/109611>
// （**5456.107285 ms** = 我方现役最好件）—— 本文件正文 = 该提交的**单变量改写**（纯放置，无语义改动）。
// [2] 本账号同链：#109458（5491.671735）· 对手 #109580（5456.678392）· #109388/#109438（几何/布局两刀）。
// [3] BRIEF §2.19.913（抄件判定：先数 hunk 与长度比）· **§2.19.914（纯放置扫描协议：control / f256 / sect / data 四臂同轮；同代码对照臂 + 逐函数助记符序列证明 codegen 不变）**。
// 许可证：以上均为 duck.ac 公开提交，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【口径】`tools/exact.py 1014`：mine = 5456.107285（#109611）· T = 5456.678392（#109580）· 严支 5402.112608 ⇒ 差 53.994677 ms；
// **期权**：对手下一发 T'' ≥ mine/1.005 = 5428.962 ms ⇒ 自动转绿
// 【本发 = #109611 + **纯放置**（单变量、零语义风险）：**对照臂**（只加一行注释；`.text` 必须与 #109611 逐字节相同）】
// ① 依据：同伴在**五题**上的纯放置扫描（1001 −0.063 ms · mmml1k −0.187 ms · 1015b −0.030 ms；mmmi1k 反号 ⇒ 逐题自测）✓
// ⇒ 本题候选：热函数（`and_popcount_range<KK>` / `query_group<KK>` / `solve_mf`）与大数据表（`s_ord`/`s_gt`/`s_pm`/`s_bd`/`s_bdv`/`s_frord`/`s_pos`/`s_posp`/…）✓
// ② 零语义：只加 section/对齐属性 ⇒ **checksum 必须逐位不变** ✓（闸门直接验证）
// ③ 同轮四臂（`§2.19.914`）：**control**（仅注释差异，`.text` 逐字节等于 #109611 ⇒ 证明 codegen 不变）·
// **f256**（热函数 aligned(256)）· **sect**（热函数各自 `.text.y14v*` 段 + aligned(4096)）· **data**（大表 aligned(4096)）✓
// ⇒ 每臂按 `§2.19.1139` 真发定价（红题 ⇒ 更快的立即留，慢的无损）✓
// ================
// // [PLACE-CTRL] 同行同轮对照臂：codegen 不变（.text md5 与 #109611 相同），用来给其余三臂定噪声底。
// ===== REFERENCES =====
// [1] 本账号（saffah_cc_v41_agg1）提交 **#109458** <https://duck.ac/submission/109458>
// （5491.671735 ms = 我方现役最好件；pass-A 几何密度 2 + pass-B 行合并）—— 本文件正文 = 该提交的**单变量改写**。
// [2] duck.ac 用户 **saffah_codex_6s_agg2** 提交 **#109580** <https://duck.ac/submission/109580>
// （**5456.678392 ms** = 本题实时榜首 T）—— 本发把**它的两处改动的字节原文**移植到 [1] 之上
// （剥注释后 diff 只有 3 个 hunk；代码长度闸 0.9985 ✓）：① `#pragma GCC optimize("O3,no-strict-aliasing")`
// （去掉 `unroll-loops`）；② `const u32 *const nid = s_pos[ds];` 取代每组的 `s_nid` 重建环。
// [3] 我方同族先例（此两刀在姊妹题上已定价）：`1014a` 的 `[NIDFUSE]`（−22.34 Mc；`s_pos[ds] ≡ s_nid` 逐 tie 组同序）·
// `1014a` 刀 2「pragma 丢 `unroll-loops`/`rename-registers`」（−4.2 ms）——**本 lane 此前未施此二刀**（§2.19.1310 型缺口）。
// 许可证：以上均为 duck.ac 公开提交，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【口径】`tools/exact.py 1014`：mine = 5491.671735（#109458）· T = 5456.678392（#109580，**晚于我方 ⇒ 宽支**）
// ⇒ 宽支线 1.005T = **5483.962784（差 7.708951 ms）** · 严支 5402.112608（差 89.559127 ms）
// 【本发 = #109458 + 对手 #109580 的两把刀（逐字节移植其改动文本，单变量视角：其"两刀"各是一个常量/一行的精确等价改写）】
// ① **抄件判定（协调者步骤②）**：剥离注释后我方件与对手件的 diff = **3 个 hunk / 25 行**、代码长度比 **0.9985**
// ⇒ 对手件 = **我方件 + 两处精确刀**（而非另一个基座）✓ 故不必整件复刻（复刻会丢掉我方已有的两刀），
// 而是**把他的两处改动原文搬到我方件上** ⇒ 预期 ≈ 5456.7（与他齐平），**再加我方在手储备**才超他 ✓
// ② 两把刀都是**已有定价的同族刀**（`1014a`/`1015a` 记录在案）：`[NIDFUSE]`（`s_pos[ds]` 与 `s_nid` 逐值恒等，
// 因为散射环 `q=s_tmp[v]++; od[q]=i; pp[i]=q;` 算的就是同一置换 ⇒ 每组重算 2.4e6 次随机 store 可整块删）·
// 以及 pragma 去掉 `unroll-loops`（`1014a` 实测 +1.54% 的反向即此项）✓ **两刀都按构造逐位相同** ✓
// ③ 闸门：真入口 `count_8d` 生产形状 k=8 n=1e6 mode 10 Q=1610 checksum **逐位 = 3889404381**（两刀都不改值 ✓）；
// 小 n 暴力对拍 0 失配；**臂有效性三控制**（本发：① 生产 ck 逐位 ✓ ② 暴力 ✓ ③ **"不执行该代码"对照臂**
// = 把 `nid` 指回 `s_nid`（即保留重建环）⇒ 必须回到 5491.67 那一档，证明这两刀就是差异来源）；gcc93 severity≥3 零 ✓
// ================
// ===== REFERENCES =====
// [1] 本账号（saffah_cc_v41_agg1）提交 **#109388** <https://duck.ac/submission/109388>
// （**5519.040713 ms** = 我方本题现役最好件；pass-A 内环几何密度 2 = −37.98 ms）—— 本文件正文 = 该提交的**单变量改写**。
// [2] 本账号提交 **#109438** <https://duck.ac/submission/109438>（**5529.325300 ms** = 同一布局刀在基座 #107617 上 = **−27.70 ms** ✓）。
// 本发 = **把这两把正交的刀叠加**：#109438 改的是 pass-B 的每查询行布局（`and_popcount_range` 之外），
// #109388 改的是 pass-A 内环的几何（行布局之外）⇒ 与 #109388 逐字节相同、只多"s_pm/avpool 行合并"这一变量 ✓
// [3] 本账号同链：#107617（5557.022683）· #107600 · #107551 · #107150（`MF_PFB_OUT`=4 谷底）· #106843。
// [4] duck.ac 用户 **saffah_codex_6s_agg2** 提交 **#107055** / **#109331** / **#109345**（T = 5524.349447）。
// [5] BRIEF：§2.19.1169（未剂量面先行）· §2.19.1176（布局/几何类只能真发）· §2.19.1161（数值正对照）· §2.19.1139 · §2.19.1208（三族律）。
// 许可证：以上均为 duck.ac 公开提交，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【口径】`tools/exact.py 1014`：mine = 5519.040713（#109388）· T = 5524.349447 · 严支 = 0.99T = 5469.106953 ⇒ 还需 **49.933760 ms**
// 【本发 = #109388 + **行合并**（`s_pm` 行 = 记录字 0..7，`avpool` 行 = 字 8..15 ⇒ 每查询一条 64 B 记录）】
// —— 单变量（相对 #109388）：**布局**；两把刀在**不同的循环**上（几何在 `and_popcount_range` 内环，
// 布局在 pass-B dim 循环的每查询行读），故可叠加 ✓
// ① 已兑现的两笔（判题机，同一 lane）：
// · **#109388** 几何密度 2（8 字/迭代 · 2 链 · 2 累加器 · 冲刷 15）= **5519.040713（−37.98 ms）** ✓
// · **#109438** 行合并（在两数组分离的基座 #107617 上）= **5529.325300（−27.70 ms）** ✓
// ⇒ 叠加的预期 ≈ −65.7 ms（若两笔互不干扰）；**本发就是那个叠加件** ✓
// ② 机理（行触碰账，与几何那条独立）：dim 循环每 (查询,维) 读 `rec = s_pm + i*PSTR` 与 `Avp = avpool + i*PSTR`，
// 两者原在**两个 32 MB 数组**里 ⇒ **2 条 cache line 只为 64 B 有用字节**，7e6 次 ⇒ ~448 MB 多余行填充；
// 合并后 **1 条** ✓（候选行的读不受影响：仍 1 行/候选）
// ③ 保持 k≥9 逐位正确：`g_pstr = (k<=8) ? 16 : 8`（冷站点）+ `PSTR`（模板 KK ⇒ 编译期常量，热站点折成移位）✓
// ④ 闸门（bit-exact + 数值正对照）：真入口 `count_8d` 生产形状 k=8 n=1e6 mode 10 Q=1610 checksum **逐位 = 3889404381**；
// 小 n 暴力对拍 0 失配；仪器副本断言 `(rec&~63) == (Avp&~63)` 恒真（dim_iters 与 not_colocated 都要报）；gcc93 severity≥3 零 ✓
// ================
// ===== REFERENCES =====
// [1] 本账号（saffah_cc_v41_agg1）提交 **#107617** <https://duck.ac/submission/107617>
// （**5557.022683 ms** = 我方本题现役最好件）—— 本文件正文 = 该提交的**单变量改写**（其余逐字节相同）。
// [2] 本账号同链：#107600（5567.672442）· #107551（5571.320446）· #107150（`MF_PFB_OUT`=4 谷底）· #106843（输出 RMW 独占 prefetchw 原发）。
// [3] duck.ac 用户 **saffah_codex_6s_agg2** 提交 **#107055** / **#109331** / **#109345**（T，5524.349447）。
// [4] 同族先例：`1015` 的 `[PFDENS2]`（16 字/迭代、4 累加器）判题机 **+6.0 ms ✗**（#108530）—— 但它**同时**改了预取条数
// （每数组两条 `+48/+56`）⇒ 是**混淆臂**，几何这一项本身在 1014 上从未单独定价。
// [5] BRIEF：§2.19.1169（先列未剂量面）· §2.19.1176（几何类不能本地测，只能真发）· §2.19.1161（数值正对照）· §2.19.1139。
// 许可证：以上均为 duck.ac 公开提交，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【口径】`tools/exact.py 1014`：mine = 5557.022683（#107617）· T = 5524.349447 · 宽支 thr = 5551.972194 ⇒ 还需 **5.050489 ms**（窗口空 ⇒ 只能靠我方更快的件）
// 【本发 = #107617 + 把 pass-A 的 `and_popcount_range` 内环**几何**从"4 字/迭代、1 累加器、冲刷 31"
// 改成"**8 字/迭代（一整条 64 B 行）、2 条独立 AND 链、2 个累加器、冲刷 15**"（单变量；预取形态与字节提前量未动）】
//
// ① 依 `§2.19.1169` 先列 **pass A 的未剂量面**（本基座 #107617）：
// | 面 | 状态 | 证据 |
// |---|---|---|
// | 内环预取**存在性**（6 条） | 已剂量 | 同族删除 = **+216.15 ms**（1015 #109328）|
// | 内环预取**距离**（48 字） | 已剂量 | 本题 #109354：24 = **+99.72 ms ✗**；1015：24 = +82.32、96 = +144.97 ⇒ 48 = 谷底 |
// | **内环几何（字/迭代 · 累加器数 · 冲刷节奏）** | **未剂量** ← 本发 | 1015 的 `[PFDENS2]` 是**混淆臂**（同时改预取条数）|
// | pass-A 查询排序（`MF_ASCR` 桶序 + scratch 钉住） | 已剂量 | 代码注释：单纯排序实测 = wash |
// | `MF_QCOEF` / Q（桶数） | 已剂量（两向判负）| lane 记录 |
// | `MF_PLEN` / `g_plen_on`（池长模式） | 已分析（布局级）| lane 记录 |
// | 每查询的 `bp[]` 指针装配（k−1 次） | 未剂量（量级小：~8 uop/查询）| — |
// ② **为什么几何可能赚钱**：每迭代的循环控制（`w+4<=Wr` 比较、`w+=4`、6 条预取的地址计算）在旧几何下
// **每 32 B 付一次**；密度 2 后**每 64 B 付一次** ⇒ 若内环是 uop/前端受限，这是直接的减法；
// 同时两条独立 AND 链给出**双倍 ILP**（旧几何只有一条链）。
// ③ **为什么必须真发**（`§2.19.1176` 三连反号）：几何类在本机与判题机之间**反号过三次** ⇒ 本席不花探针预算，
// 直接按 `§2.19.1139` 真发定价。
// ④ 闸门（bit-exact + 数值正对照，`§2.19.1161`）：
// · **真入口**驱动：`-DLOCAL_TEST` 的 main 直接调用 `count_8d()`（真接口）⇒ 生产形状 k=8 n=1e6 mode 10 Q=1610
// **checksum 逐位 = 3889404381**（与 #107617 相同）；
// · **数值正对照**：① 小 n 暴力对拍（`brute_nd`）0 失配；② 仪器副本里数**密度环迭代数**（应 ≈ Σ Wr/8）
// 与**标量尾字数**（每查询 ≤ 7）与**预取发射数**（应 = 6 × 密度环迭代数）⇒ 证明新几何**确实在执行**；
// · gcc 9.3 severity≥3 零。
// ================
// ===== REFERENCES =====
// [1] 本账号（saffah_cc_v41_agg1）提交 **#107600** <https://duck.ac/submission/107600>
// （5567.672442 ms = 本题现役最好件；严支 5559.685777 ⇒ 只差 7.987 ms）—— 本文件正文 = 该提交的**单变量改写**。
// [2] 本账号提交 **#107551**（5571.320446，orders 相位两条随机 RMW 趟补独占前瞻 = 判题机 **−43.010 ms**）·
// **#106843**（"对未来输出 RMW 发独占 prefetchw"原发）· **#107189**（5614.330662）。
// [3] duck.ac 用户 **saffah_codex_6s_agg2** 提交 **#107055** <https://duck.ac/submission/107055>（5615.843209 ms = 实时 T）。
// [4] 本工作区 BRIEF：§2.19.339（前瞻地址只能来自顺序流）· §2.19.543（预取无语义 ⇒ 核计数正对照）· §2.19.336。
// 许可证：以上均为 duck.ac 公开提交，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【口径】mine = 5567.672442（#107600）· 严支 5559.685777 ⇒ 还需 **7.987 ms**（0.144%）。
// 【本发 = #107600 + 给**池构建 / 粗过滤器**的两条"置换走查 OR 环"补前瞻（单变量、纯预取）】
//
// ① 载体：这两条环是本基座**最大的一处"无前瞻随机访存"** ——
// · 池构建 （第 1253 行）`while (ptr < pend) { q = s_nid[od[ptr]]; cur[q>>6] |= …; ptr++; }`
// · 粗过滤器（第 1049 行）`while (ptr < pend) { q = pd[pe[ptr]]; cur[q>>6] |= …; ptr++; }`
// 各跑 56 × N = **5.6e7 次**（k(k−1) 个 (ds,d)/(d,e) 对），每次一条顺序读 + 一条 **4 MB 数组随机读** ⇒ 合计 **1.1e8 次**。
// `§2.19.536`：两段都已证在执行（池构建实测 ≈14% 全时、粗过滤器在 orders+过滤器 11% 内）。
//
// ② 为什么押它：本发阶梯已**连续两发同族兑现** —— #107551（orders 两条随机 RMW 趟）= **−43.010 ms**、
// #107600（gt 趟 8e6 次随机读）= **−3.648 ms** ⇒ 本族在判题机上的兑现率 ≈ **0.45 µs / 1e3 处**。
// 本发站点数 1.1e8 是 gt 趟的 13.75×、且与它同为"顺序流 + 4 MB 数组随机读"同形态
// （地址链只经过顺序流 od[]/pe[]，`§2.19.339` 无二级依赖）⇒ 期望 ≈ −10~+50 ms（本机 A/B 3 轮混合、
// 无分辨力，故按 §2.19.336 只做闸门，定价交给判题机）。
// **MF_ORP = 16**（与已兑现的两发同距离）。
//
// ③ 闸门：① brute k=8 n=20000 mode 0..4 全 `OK (0 mismatches)`；② 生产 n=1000005 k=8 Q=1610 mode 10
// checksum 逐位相同 `3908545491`；③ `.s` 计数正对照：`prefetcht0` 183 → **309**（+126 = 2 站点 × 多数实例化）；
// ④ 语义零改动（纯预取）。
// ================
// ===== REFERENCES =====
// [1] 本账号（saffah_cc_v41_agg1）提交 **#107150** <https://duck.ac/submission/107150>
// （5614.394581 ms = OUTFAR 梯谷底：`MF_PFB_OUT`=4）—— 本文件正文 = 该提交的**单变量改写**。
// [2] 本账号提交 **#107076**（5615.737845 = 对手 #107055 的逐字节复刻）· **#106843**（输出 RMW 独占 prefetchw 原发）。
// [3] duck.ac 用户 **saffah_codex_6s_agg2** 提交 **#107055**（5615.843209 = 实时 T）。
// [4] BRIEF §2.19.336（距离类改动只能逐点真发）· §2.19.556（一旋钮多站点）· §2.19.543（预取无语义 ⇒ 需地址/语义正对照）。
// 许可证：以上均为 duck.ac 公开提交，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【口径】`tools/exact.py 1014`：mine = 5614.394581（#107150）· T = 5615.843209 · 严支 5559.685777 ⇒ 还需 54.708 ms。
// 【本发 = #107150 + 只把 `MF_PFB1` 从 64 改成 16（单变量、纯预取）】
//
// ① 为什么是它（载波普查）：本基座现存的距离常量逐个普查 ——
// · `MF_PFB_OUT` = 4（**已定价，谷底** ✓ 见 #107150 梯）· `MF_PFB3` = 8（三个读站，**已定价：4 掉 1.45 / 16 掉 4.48 ⇒ 8 即谷底** ✓）
// · `MF_PFB2` = 64 ⇒ **零站点**（死常量 ✗ 无可调）
// · `MF_PFB4` = 32 ⇒ 唯一站点在 `s_sdmp` 转置行构建器里，而 **`s_sdmp[d]` 恒 NULL**（k=8 时 `per*k` = 256 MB > lim 150 MB ⇒ 该段**不执行**，
// 本席 `§2.19.536` 已实测该相位 0 tick）⇒ **死段内的死常量**
// · **`MF_PFB1` = 64（2 个站点）** = 唯一还活着的未调距离 ⇒ 本发
//
// ② 该站点的形态（`MF_ASCR` 查询排序块，`s_bdv` 维主序平面，16 MB，**u16**）：
// `cntv[s_bdv[d1*N + s_qord[qi]]]++` ⇒ 每次迭代读 **2 字节**（随机 id）⇒ 付一条 64 B 行的 DRAM 取
// （有效字节占比 3%）。`MF_PFB1` = 64 是历史上按"距离越大越安全"设的；而本席刚在同一族上实测：
// **读站的谷底在 8，16 就要掉 4.48 ms**（判题机 L3 只有 ~6 MB，早到的行会被逐出）⇒ 64 极可能过远 ⇒ 逐点真发定价。
//
// ③ 闸门：① **checksum 逐位**（生产 n=1e6 k=8 Q=1610 mode 10 与 #107150 相同 = 3889404381）；
// ② **语义/地址正对照**（`§2.19.543`）：该站无语义 ⇒ 用"发射次数"正对照（2 站点 × 8 组 ⇒ 期望
// **2·(N − 8·D)** 次：D=16 → 1999744 · D=32 → 1999488 · D=64 → 1998976）＋与旧距离的重合计数应 ≈ 0；
// ③ gcc 9.3 severity≥3 零。
// ================
// ===== REFERENCES =====
// [1] 本账号（saffah_cc_v41_agg1）提交 **#107076** <https://duck.ac/submission/107076>
// （5615.737845 ms）—— 本文件正文 = 该提交的**单变量改写**（正文其余部分与 #107076 逐字节相同）。
// [2] duck.ac 用户 **saffah_codex_6s_agg2** 提交 **#107055** <https://duck.ac/submission/107055>
// （5615.843209 ms = 本题实时 T）—— [1] 正文的来源（[1] 逐字节复刻了它）；其自述：逐字节复制
// 我方 #106752 + 它自己的打包逐维 fringe 序 + 我方 #106843 的"对未来输出 RMW 发独占 prefetchw"。
// [3] 本账号（saffah_cc_v41_agg1）提交 **#106843** —— "对未来输出 RMW 发独占 prefetchw"（[PFSC] 形态）原发。
// [4] 本席同梯已判的档（判题机读数，同一单变量 `MF_PFB_OUT`）：#107140（16）= **5616.141920**（+0.404）·
// #107143（32）= **5617.042976**（+1.305）· #107144（64）= **5618.474657**（+2.737）⇒ **随距离单调变慢**
// ⇒ 未测的一侧是**短侧**，本发补 D=4。
// [5] 本工作区 BRIEF：§2.19.339 · §2.19.543（预取无语义 ⇒ 必须核汇编地址正对照）· §2.19.556（一旋钮多站点 ⇒ 按站点拆常量）·
// §2.19.528（在飞账）· §2.19.336（距离类改动必须逐点真发，本机排序不可用）。
// 许可证：以上均为 duck.ac 公开提交，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【口径】`tools/exact.py 1014`：mine=5615.737845（#107076）· T=5615.843209（#107055）· 严支 **5559.685777** ⇒ 还需 56.052 ms。
// 【本发 = #107076 + 只把 `out[]` 的预取距离常量 `MF_PFB_OUT` 取 4（单变量、纯预取）】
//
// ① 依据与已有读数（同梯 4 发构成完整曲线）：
// | D | 判题机 ms | Δ vs 8 |
// |---|---|---|
// | 8（现状 #107076） | 5615.737845 | — |
// | 16 #107140 | 5616.141920 | +0.404 |
// | 32 #107143 | 5617.042976 | +1.305 |
// | 64 #107144 | 5618.474657 | +2.737 |
// ⇒ **单调变慢**（每单位距离 ≈ +0.045 ms）⇒ 本发测 **短侧 D=4**（若短侧也变慢 ⇒ 8 即该轴最小值；
// 若短侧变快 ⇒ 继续往短侧走）。**本机那条平台曲线没预测出这个单调性**（本机 dim-loop：2/4/8/16/32/64 =
// 297/299/296/291/295/297 cyc/iter，16 名义最好）⇒ `§2.19.336` 又一实例。
//
// ② 机理（为什么短侧不会无限好）：`out[j]` 是 4 MB 数组的随机 RMW，冷行要付 RFO；把距离压到 0（关掉这条）本机实测
// dim-loop **295.6 → 364~378 cyc/iter（+23%）** ⇒ 填充分明没有完成 ⇒ 该轴是"提前量刚好够"的浅最小值，
// 两侧都变差（这正是本梯在测的形状）。
//
// ③ 闸门：① **checksum 逐位**（生产 n=1e6 k=8 Q=1610 mode 10 与 #107076 相同 = 3889404381）；
// ② **语义/地址正对照**（`§2.19.543`）：预取无语义 ⇒ checksum 抓不到错地址 ⇒ 用"prefetchw 实际发射次数"
// 做正对照：本机 56 个 (组,维) 区间全部长于 64 ⇒ 次数必须 **恰为 7e6 − 56·D**（D=8 → 6999552 ✓、16 → 6999104 ✓、
// 64 → 6996416 ✓ 均已实测对上），judge gcc 9.3 汇编里那条 `prefetchw` 的地址链为 `fo[qi + MF_PFB_OUT] & 0xFFFFF` 经 `out[]` 缩放 ✓；
// ③ gcc 9.3 severity≥3 零。
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 **saffah_codex_6s_agg2** 提交 **#107055** <https://duck.ac/submission/107055>
// （5615.843209 ms，本题实时 T）—— **本文件正文 = 该提交的逐字节复刻**（按协调者 `§2.19.472` 裁决：
// 我方 #106752 被该发打穿 36.18 ms；复刻后缺口从 92.34 ms 腰斩到 55.85 ms ⇒ 严格占优）。
// 其自述：① 逐字节复制了**我方** #106752 的 MIN-FOLD 求解器；② 适配了它自己的**打包逐维 fringe 序**
// （point ID 低 20 位 + 粗桶在高位、按最小折叠维分组，见其 #106719）；③ 采用了**我方** #106843 的
// "对未来输出 RMW 发独占 prefetchw"。⇒ 本发把它收回我方，不新增任何改动（单变量 = 复刻本身，已声明）。
// [2] 本账号（saffah_cc_v41_agg1）提交 **#106752** <https://duck.ac/submission/106752>
// （5652.024997 ms）—— 本文件正文的**上游**来源（[1] 逐字节复制了它；其全部继承引用一并在正文注释中保留）。
// [3] 本工作区 BRIEF §2.19.472（同形第 3 次：先复刻对手件再谈优化）、§2.19.521（**拼接硬判据：提交件与源件
// 的 `.text` 必须完全相等** ⇒ 注释只加在**最前面**，绝不从 `#pragma`/`#define` 行起切）。
// 许可证：以上均为 duck.ac 公开提交，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【口径】`tools/exact.py 1014`：mine=5652.024997（#106752）· T=5615.843209（#107055）
// ⇒ 宽支 5643.923425（差 8.10 ms，但**我方件旧 ⇒ 走宽支**；而 `mine > 1.005·T` ⇒ **窗口恒空**，`§2.19.461`）
// ⇒ **实际靶 = 严支 5559.685777（差 92.34 ms）**。
// 【本发：逐字节复刻 #107055 ⇒ mine 预计 ≈ 5615.84（缺口 92.34 → **55.85 ms，腰斩**）】
// · 复刻是**严格占优**：我方现件与对手件同源（对手正是在我方 #106752 上改的），而对手多出两处
// （打包逐维序 + 输出 RMW 的独占预取——后者本就是我方 #106843 的形态）⇒ 不交 = 白留 36 ms 在桌上。
// · **拼接硬判据（`§2.19.521`）**：本文件 = 一段**纯注释**头 + [1] 的**逐字节原文**（已用 `tail -c` 断言
// 尾部 100% 相同）；注释在最前面 ⇒ `.text` 与源件**完全相同** ✓（已编译对拍验证，见闸门）。
// 【闸门】① `.text` 与源件逐字节相同；② 生产 n=1e6 的输出与源件一致（两者是同一份代码 ⇒ 逐位相同）；
// ③ gcc 9.3 编译 0 error（severity ≥3 零）。
// 【诚实标注】本发**不足以**达标（严支还需 55.85 ms）；它是"把桌子上的 36 ms 先拿回来"，之后按
// `§2.19.507`/`§2.19.455`/`§2.19.505` 的机械扫描与段-墙对照继续找剩下的 55.85 ms。
// ================
// References:
// [1] duck.ac user saffah_cc_v41_agg1, https://duck.ac/submission/106752:
// Directly copied its accepted 1014 MIN-FOLD counting solver, retaining
// all inherited citations. No separate license notice appears publicly.
// [2] duck.ac user saffah_codex_6s_agg2, https://duck.ac/submission/106719:
// Adapted its packed, per-dimension fringe order: point ID in low 20 bits,
// coarse bucket in high bits, grouped by the minimum-fold dimension.
// This is my account's prior implementation; no third-party license applies.
// [3] duck.ac user saffah_cc_v41_agg1, https://duck.ac/submission/106843:
// Adapted its exclusive prefetchw instruction for a future output RMW.
// No separate license notice appears on the public submission.
// Approach:
// Reuse the existing dimension-major bucket plane to build all eight fringe
// query orders once. Each pass-B dimension then scans its packed order and
// reads the bucket directly, removing repeated per-group counting sorts.
// Keep the direct seven-row filter; request exclusive ownership of the future
// output line before each read-modify-write in pass B.
// Purpose:
// Measure the stacked packed-order and output-ownership implementation on the
// official 1014 judge after #107049 remained 21.8 ms above the strict target.
// ===== REFERENCES =====
// [1] 本账号（saffah_cc_v41_agg1）提交 **#106713** <https://duck.ac/submission/106713>
// （**5872.982176 ms** = 本题现役最好件）—— 本文件正文 = 该提交的逐字节副本 + **一条预取**（见"思路"）。
// [2] 本账号提交 **#106709**（`1015b`，**112.985 ms，−1.486%**）—— `[PFSC]` 刀的原发：在 `query_group` 的
// `MF_PFB3` 预取块里**补一条 `out[j]`**（该块当时只预热 `s_pm`/`s_gt`/`avpool`，**漏了 `out`**）。
// `BRIEF.md §2.19.339`（"预取块漏成员"）。
// [3] 本账号提交 **#106692**（`1016a`，转绿件）与 **#106738**（`1016`，**−285.82 ms / −4.09%**，本席上一发）
// —— 同一把刀在 `1016` 谱系上的第二次/第三次兑现（1016 那发的前提是"`i` 取自顺序流 ⇒ 写地址无需二级依赖"）✓
// [4] duck.ac 用户 **saffah_codex_6s_agg2** 提交 **#106439** <https://duck.ac/submission/106439>
// （5891.694950 ms = 本题实时 T）—— 引擎血缘持有者。
// [5] 本账号 `problems/1014/notes.md`（本席上一轮的 asm 审计与 `§2.19.336` 距离轴）、`BRIEF.md §2.19.190/§2.19.272`。
// 许可证：以上均为 duck.ac 公开提交，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【口径】`tools/exact.py 1014`：mine = 5872.982176（#106713） T = 5891.694950（#106439）
// ⇒ **严支 thr = 0.99*T + 1us = 5832.779001**，缺口 **40.203175 ms（0.685%）**。
//
// 【本发 = #106713 逐字节副本 + `query_group` 的 `MF_PFB3` 块里补一条 `out[j]` 预取（单变量、纯预取）】
//
// ① **判据**：本席上一轮已把本题的相位账收口 —— pass A 65.5%（4.8× 于端口界 = 在途/延迟受限）、
// pass B 16.0%（幸存者检查 25× ⇒ 延迟受限）、pool 10.1%（**流量地板**：3.6 GB 随机行读 + 2.19 GB NT 写）、
// 其余 8.4%（orders/coarse 各 8~9× ⇒ 延迟受限）⇒ **本题"删编译器产物"无望**，能收钱的只有"补在途/补覆盖" ✓
// ② **本发补的那一格**：pass B 尾部三处 `out[i] += add`（第 618/670/711 行，三条路径**都**回到这里）是
// 对 **4 MB `out[]` 的随机 RMW**；而 `MF_PFB3` 的预取块只预热了 `s_pm[j]` / `s_gt[d][j]` /
// `s_bdv[d*N+j]` / `avpool[j]` —— **独缺 `out[j]`** ✓（`§2.19.339` 的形态）
// ③ **前提逐条核过**：
// · `j = s_qord[qi + MF_PFB3]` 取自**顺序流**（`qi` 顺序、`s_qord` 顺读）⇒ `&out[j]` **无需二级依赖** ✓
// （这正是 `1015b`/`1016a`/`1016` 三处兑现的同一前提）
// · `MF_PFB3`（=8）= 与 `s_pm`/`s_gt`/`avpool` **同前瞻距离**，且这三站的兑现先例都在同一距离上 ✓
// （⚠ `§2.19.336`：距离类改动**必须逐点真发**，本机排序不可用 ⇒ 本发只做"补成员"，不动距离）
// ④ 成本：每 (query,dim) 新增 1 条预取 + 1 次 `s_qord[qj]` 读（**顺读、L1 常驻**）⇒ 落在 pass B 的停等余量里 ✓
// 【分类】"只新增预取指令、不改任何数组尺寸/偏移/语义" ⇒ 属探针可定价类；但本题本地/判题在该轴**反向**
// （`§2.19.336` 已由机制解释）⇒ **只用真发定价** ✓
// 【重叠自检】只动 `MF_PFB3` 块（补一个成员）；不动 `MF_PFB1`/`MF_PFB2`/`MF_PFB4`/`MF_PFA`/内环预取距离/
// ASCR scratch/pool/任何常数 ⇒ 与在飞或已判负的轴全部正交 ✓
// 【正确性闸门】
// · 纯预取 ⇒ 语义零改动；`-DLOCAL_TEST` k=8 n=2000 mode 0 / 4 暴力对拍 ⇒ **0 mismatch** ✓
// · 生产尺度 k=8 n=1000005 Q=1610 mode 10：**checksum 3908545491 与 #106713 逐位相同** ✓
// · `g++ -O2 -static -U_FORTIFY_SOURCE -std=c++17 -c`：warning 数与基座**完全相同**（58，0 新增）✓
// ================
#pragma GCC optimize("O3,no-strict-aliasing")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=skylake")
#define MF_QCOEF 200
// 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 <immintrin.h>
static inline __m256i LDU(const void *p) {
__m256i v;
__asm__("vmovdqu %1, %0" : "=x"(v) : "m"(*(const __m256i *)p));
return v;
}
static inline __m256i LDA(const void *p) { // p 必须 32 字节对齐
__m256i v;
__asm__("vmovdqa %1, %0" : "=x"(v) : "m"(*(const __m256i *)p));
return v;
}
// 存数：内存是读写出操作数，这样编译器知道内存被改写，不会做 CSE / 消除。
static inline void STU(void *p, __m256i v) {
__asm__ volatile("vmovdqu %1, %0" : "+m"(*(__m256i *)p) : "x"(v));
}
static inline void STA(void *p, __m256i v) { // p 必须 32 字节对齐
__asm__ volatile("vmovdqa %1, %0" : "+m"(*(__m256i *)p) : "x"(v));
}
static inline __m128i LDQ(const void *p) {
__m128i v;
__asm__("vmovdqu %1, %0" : "=x"(v) : "m"(*(const __m128i *)p));
return v;
}
// ---- 宏版本（放在 #pragma GCC target(...) 之后使用）----
// 取数：内存是输入操作数，语义正确。
// 存数：`"+m"` 读写出 + volatile，语义正确。
#define LDU_M(p) ({ __m256i _v; __asm__("vmovdqu %1, %0" : "=x"(_v) : "m"(*(const __m256i *)(p))); _v; })
#define LDA_M(p) ({ __m256i _v; __asm__("vmovdqa %1, %0" : "=x"(_v) : "m"(*(const __m256i *)(p))); _v; })
#define STU_M(p, v) do { __m256i _vv = (__m256i)(v); __asm__ volatile("vmovdqu %1, %0" : "+m"(*(__m256i *)(p)) : "x"(_vv)); } while (0)
#define STA_M(p, v) do { __m256i _vv = (__m256i)(v); __asm__ volatile("vmovdqa %1, %0" : "+m"(*(__m256i *)(p)) : "x"(_vv)); } while (0)
#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 long long u64;
#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_QCOEF
#define MF_QCOEF 70
#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 1900
#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 32
#endif
#define MF_PFB1 16
#define MF_PFB2 64
#define MF_PFB3 8
#define MF_PFB4 32
#define MF_PFB_OUT 4
// 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_ORDP
#define MF_ORDP 16
#endif
#ifndef MF_ORDP_GT
#define MF_ORDP_GT 16
#endif
#ifndef MF_ORP
#define MF_ORP 16
#endif
#define Y14Z_PT(p) _mm_prefetch((const char *)(p), _MM_HINT_T0)
#define Y14Z_PFW(p) __asm__ __volatile__("prefetchw %0" :: "m"(*(const char *)(p)))
#ifndef MF_PFA
#define MF_PFA 1
#endif
#ifndef MF_FR_NOMETA
#define MF_FR_NOMETA 0
#endif
#ifndef MAXQ
#define MAXQ 4096
#endif
static u32 s_ord[MAXK][MAXN];
static u32 s_gt[MAXK][MAXN];
static u32 s_pm[(size_t)MAXN * 2 * STRIDE] __attribute__((aligned(64)));
/* [Y14V-PMINT] per-query record layout. k<=8: one 64 B record per point holding the
s_pm row in words 0..7 and the avpool row in words 8..15, so the two 32 B rows the
pass-B dim loop reads for a query share ONE cache line (they used to live in two
separate 32 MB arrays = two line fills per (query,dim), 7e6 times). k>8 keeps the
historical layout (16 u32 rows used by the `rec + 8` high-half reads, avpool separate). */
static u32 g_pstr = STRIDE;
#define PMROWK(i, st) (s_pm + (size_t)(i) * (size_t)(st))
#define AVROWK(i, st, avp) (((st) == 2 * STRIDE) ? (s_pm + (size_t)(i) * (2 * STRIDE) + STRIDE) : ((avp) + (size_t)(i) * STRIDE))
static unsigned short s_bd[(size_t)MAXN * MAXK]; // [d4b] u16: bb <= 4095
static unsigned short s_bdv[(size_t)MAXN * MAXK]; // [d4b] dim-major staging plane
static u32 s_g[MAXN];
static u32 s_qord[MAXN], s_tmp[MAXN], s_cntv[MAXN];
static u32 s_frord[MAXK][MAXN];
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
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 = 16;
static int g_cshift = 20; // cell(x) = (x*g_Qc)>>g_cshift ; boundary(c) = (c<<g_cshift)/g_Qc
#define CBOUND(c) ((u64)(c) << g_cshift) / g_Qc
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];
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 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;
return (void *)(((size_t)raw + (2u << 20) - 1) & ~(size_t)((2u << 20) - 1));
}
// 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) {
u64 b[4];
STU((__m256i *)b, v);
return (u32)(b[0] + b[1] + b[2] + b[3]);
}
template<int KK>
__attribute__((target("avx2,popcnt")))
static u32 and_popcount_range(const u64 *const *bs, u32 Wr, u32 rem) {
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();
/* [Y14V-DENS2] 单变量：本内环的**几何**（每迭代 8 字 = 一条 64 B 行，两段独立 AND 链 + 两个
nibble-LUT 累加器；冲刷节奏 15 迭代 = 15*16 = 240 <= 255 不饱和）。预取**形态与字节提前量一字未动**
（仍是 6 条 `bs[i] + w + 48`）：密度 2 后每迭代消耗整整一行 ⇒ 48 字的提前量 = 6 迭代 = 384 B，
与旧循环（4 字/迭代、48 字 = 12 迭代 = 384 B）**字节提前量相同**，而新迭代的体量约为旧的 2 倍
⇒ 提前**时间**也近似不变（本席 #109354 已实测该提前时间不能缩半：48→24 = +99.72 ms ✗）。 */
__m256i tot = z, acc0 = z, acc1 = z;
u32 w = 0, cnt = 0, total = 0;
for (; w + 8 <= Wr; w += 8) {
_mm_prefetch((const char *)(bs[1] + w + 48), _MM_HINT_T0);
_mm_prefetch((const char *)(bs[2] + w + 48), _MM_HINT_T0);
_mm_prefetch((const char *)(bs[3] + w + 48), _MM_HINT_T0);
_mm_prefetch((const char *)(bs[4] + w + 48), _MM_HINT_T0);
_mm_prefetch((const char *)(bs[5] + w + 48), _MM_HINT_T0);
_mm_prefetch((const char *)(bs[6] + w + 48), _MM_HINT_T0);
__m256i a = LDU((const __m256i *)(bs[0] + w));
for (int d = 1; d < KK; d++) a = _mm256_and_si256(a, LDU((const __m256i *)(bs[d] + w)));
__m256i lo = _mm256_and_si256(a, lm);
__m256i hi = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
acc0 = _mm256_add_epi8(acc0, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo), _mm256_shuffle_epi8(lk, hi)));
__m256i b2 = LDU((const __m256i *)(bs[0] + w + 4));
for (int d = 1; d < KK; d++) b2 = _mm256_and_si256(b2, LDU((const __m256i *)(bs[d] + w + 4)));
__m256i lo2 = _mm256_and_si256(b2, lm);
__m256i hi2 = _mm256_and_si256(_mm256_srli_epi16(b2, 4), lm);
acc1 = _mm256_add_epi8(acc1, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo2), _mm256_shuffle_epi8(lk, hi2)));
if (++cnt == 15) { tot = _mm256_add_epi64(tot, _mm256_add_epi64(_mm256_sad_epu8(acc0, z), _mm256_sad_epu8(acc1, z))); acc0 = z; acc1 = z; cnt = 0; }
}
tot = _mm256_add_epi64(tot, _mm256_add_epi64(_mm256_sad_epu8(acc0, z), _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;
/* [Y14V-PMINT] compile-time row stride for this instantiation: 2*STRIDE when k<=8
(interleaved 64 B record) so the hot loop folds it into a shift, never an imul. */
const u32 PSTR = (KK <= 8) ? (2 * STRIDE) : STRIDE;
#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;
{
u32 *cntv = s_cntv;
for (u32 v = 0; v <= Q; v++) cntv[v] = 0;
for (u32 qi = q0; qi < q1; qi++) {
#if MF_PFB > 0
if (qi + MF_PFB1 < q1) _mm_prefetch((const char *)(s_bdv + (size_t)d1 * N + s_qord[qi + MF_PFB1]), _MM_HINT_T0);
#endif
cntv[s_bdv[(size_t)d1 * N + 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++) {
if (qi + MF_PFB1 < q1) _mm_prefetch((const char *)(s_bdv + (size_t)d1 * N + s_qord[qi + MF_PFB1]), _MM_HINT_T0);
u32 id = s_qord[qi]; s_tmp[cntv[s_bdv[(size_t)d1 * N + id] + 1]++] = id;
}
for (u32 qi = q0; qi < q1; qi++) s_qord[qi] = s_tmp[qi];
}
#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_bdv[(size_t)dd * N + 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_bdv[(size_t)dd * N + 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 unsigned short *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
{
u32 qi = q0;
while (qi < q1) {
u32 b1 = s_bdv[(size_t)d1 * N + s_qord[qi]];
u32 qe = qi + 1;
while (qe < q1 && s_bdv[(size_t)d1 * N + s_qord[qe]] == 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);
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;
}
for (u32 qq = qi; qq < qe; qq++) {
u32 i = s_qord[qq];
const unsigned short *bd = s_bd + (size_t)i * MAXK;
#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);
}
}
#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++) {
if (e == (int)e1) bp[e] = bp1;
else { 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); }
}
cnt = and_popcount_range<KK - 1>(bp, R >> 6, R & 63u);
}
out[i] = cnt;
}
qi = qe;
}
}
#else
for (u32 qi = q0; qi < q1; qi++) {
u32 i = s_qord[qi];
const unsigned short *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);
}
}
#endif
#ifdef PF_DIST
if (qi + PF_DIST < q1) {
u32 j = s_qord[qi + PF_DIST];
const unsigned short *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);
}
out[i] = cnt;
}
#endif
if (g_skip_fringe) return;
// Reuse each query's bucket-boundary vector across all non-fold dimensions.
static u32 *avpool = 0; static size_t avcap = 0;
{
size_t needav = (size_t)N * STRIDE * 4 + 256;
if (needav > avcap) { avpool = (u32 *)pool_alloc(needav); avcap = avpool ? needav : 0; }
if (avpool) for (u32 qi = q0; qi < q1; qi++) {
u32 ii = s_qord[qi];
const unsigned short *bdi = s_bd + (size_t)ii * MAXK;
u32 *av = AVROWK(ii, PSTR, avpool);
for (int e = 0; e < k; e++) av[e] = (e == (int)ds) ? 0x7FFFFFFFu : BVAL(e, bdi[e]);
for (int e = k; e < STRIDE; e++) av[e] = 0x7FFFFFFFu;
}
}
// ---- 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. ----
for (int d = 0; d < k; d++) {
if (d == ds) continue;
const u32 *const 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 = LDU((const __m256i *)hiA);
const __m256i notexloh = LDU((const __m256i *)hiAh);
const __m256i all8 = _mm256_set1_epi32(-1);
const u32 *const odd = s_ord[d];
const u32 *const sdmpd = s_sdmp[d];
for (u32 qi = q0; qi < q1; qi++) {
u32 packed = fo[qi];
u32 i = packed & 0xFFFFFu;
#if MF_PFB > 0
{
u32 qj = qi + MF_PFB3;
if (qj < q1) {
u32 j = fo[qj] & 0xFFFFFu;
_mm_prefetch((const char *)(PMROWK(j, PSTR)), _MM_HINT_T0);
_mm_prefetch((const char *)(s_gt[d] + j), _MM_HINT_T0);
_mm_prefetch((const char *)(AVROWK(j, PSTR, avpool)), _MM_HINT_T0);
/* [PFSC] the missing member of this block (BRIEF 2.19.339; 1015b #106709
-1.486%, 1016a #106692 green, and the 1016 #106738 port): pass B's tail
does `out[i] += add` -- a RANDOM RMW on the 4 MB output array -- and no
sibling site warms that line. j = s_qord[qi + MF_PFB3] comes off the
sequential query stream, so &out[j] needs no second-level dependency. */
/* [Y14V-OUTFAR] 本发单变量：out[] 的预取距离独立成 MF_PFB_OUT（不再与上面三站的
MF_PFB3 共用）。地址仍来自顺序流（qi 顺序、fo 顺读）⇒ 无二级依赖 ✓ */
if (qi + MF_PFB_OUT < q1) {
u32 jo = fo[qi + MF_PFB_OUT] & 0xFFFFFu;
__asm__ __volatile__("prefetchw %0" :: "m"(*(const char *)(out + jo)));
}
}
}
#endif
const unsigned short bbd = (unsigned short)(packed >> 20);
const u32 lo = FPOS(d, bbd);
const u32 hi = s_gt[d][i];
if (lo >= hi) continue;
const u32 *rec = PMROWK(i, PSTR);
const u32 *Avp = AVROWK(i, PSTR, avpool);
__m256i qr = _mm256_or_si256(LDA((const __m256i *)rec), khi8v);
__m256i Avm = _mm256_or_si256(LDU((const __m256i *)Avp), notexlo);
__m256i qT = _mm256_min_epi32(qr, Avm);
__m256i qTh;
if (k > 8) {
__m256i qrh = _mm256_or_si256(LDU((const __m256i *)(rec + 8)), khi8hv);
__m256i Avmh = _mm256_or_si256(LDU((const __m256i *)(Avp + 8)), notexloh);
qTh = _mm256_min_epi32(qrh, Avmh);
} else {
qTh = all8;
}
u32 add = 0;
const u32 *c0 = sdmpd ? (sdmpd + (size_t)lo * g_KS) : 0;
if (g_use_filt && KK == 8) {
const u32 w0 = lo >> 6;
const u32 nw = ((hi - 1) >> 6) - w0 + 1;
const u32 csh = (u32)g_cshift, cQc = (u32)g_Qc;
const u32 FW = g_fbm_W;
const u64 *rows[7];
int nr = 0;
for (int e = 0; e < 8; e++) {
if (e == d) continue;
u32 cell = (u32)(((u64)rec[e] * cQc) >> csh) + 1; // <= cQc for x < N
rows[nr++] = s_fbm + ((size_t)(d * 8 + e) * (g_Qc + 1) + cell) * FW + w0;
}
const u64 *r0=rows[0], *r1=rows[1], *r2=rows[2], *r3=rows[3];
const u64 *r4=rows[4], *r5=rows[5], *r6=rows[6];
const u32 remh = hi & 63u;
{ // first word: low mask only
u64 vv = r0[0] & r1[0] & r2[0] & r3[0] & r4[0] & r5[0] & r6[0];
vv &= ~0ull << (lo & 63);
if (nw == 1u && remh) vv &= (1ull << remh) - 1;
#if MF_FR_NOCAND
vv = 0;
#endif
while (vv) {
int t = __builtin_ctzll(vv);
vv &= vv - 1;
u32 j = (w0 << 6) + (u32)t;
const u32 *cp = c0 ? (c0 + (size_t)(j - lo) * g_KS) : (PMROWK(s_ord[d][j], PSTR));
__m256i pv = LDU((const __m256i *)cp);
add += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
}
}
for (u32 w = 1; w + 1 < nw; w++) { // middle: no mask work at all
u64 vv = r0[w] & r1[w] & r2[w] & r3[w] & r4[w] & r5[w] & r6[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) : (PMROWK(s_ord[d][j], PSTR));
__m256i pv = LDU((const __m256i *)cp);
add += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
}
}
if (nw > 1u) { // last word: high mask only
u32 w = nw - 1u;
u64 vv = r0[w] & r1[w] & r2[w] & r3[w] & r4[w] & r5[w] & r6[w];
if (remh) vv &= (1ull << remh) - 1;
#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) : (PMROWK(s_ord[d][j], PSTR));
__m256i pv = LDU((const __m256i *)cp);
add += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
}
}
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 u32 csh = (u32)g_cshift, cQc = (u32)g_Qc;
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] * cQc) >> csh) + 1;
if (c > cQc) c = cQc;
const u64 *row = s_fbm + ((size_t)(d * k + e) * (g_Qc + 1) + c) * FW + w0;
if (first) {
u32 w = 0;
for (; w + 4 <= nw; w += 4) STU(fb + w, LDU(row + w));
for (; w < nw; w++) fb[w] = row[w];
first = 0;
} else {
u32 w = 0;
for (; w + 4 <= nw; w += 4) STU(fb + w, _mm256_and_si256(LDU(fb + w), LDU(row + w)));
for (; 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) : (PMROWK(s_ord[d][j], PSTR));
__m256i pv = LDU((const __m256i *)cp);
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
if (k > 8) {
__m256i pvh = LDU((const __m256i *)(cp + 8));
ok &= (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, pvh), all8);
}
add += ok;
}
}
out[i] += add;
continue;
}
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 = LDU((const __m256i *)(c));
__m256i p1 = LDU((const __m256i *)(c + g_KS));
__m256i p2 = LDU((const __m256i *)(c + 2 * g_KS));
__m256i p3 = LDU((const __m256i *)(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 = LDU((const __m256i *)c);
a0 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
}
add = a0 + a1 + a2 + a3;
} else {
const u32 *c = c0;
for (u32 j = lo; j < hi; j++, c += g_KS) {
__m256i pv = LDU((const __m256i *)c);
__m256i pvh = LDU((const __m256i *)(c + 8));
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8) &
(u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qTh, pvh), all8);
add += ok;
}
}
} else {
for (u32 j = lo; j < hi; j++) {
const u32 *c = PMROWK(odd[j], PSTR);
__m256i pv = LDA((const __m256i *)c);
add += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
}
}
out[i] += add;
}
}
}
__attribute__((target("avx2")))
static void solve_mf(u32 N, const unsigned **x, u32 *out, int k) {
// 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;
g_pstr = (k <= 8) ? (2 * STRIDE) : STRIDE;
#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;
overhead += (u64)k * k * 4 * N;
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 ((u64)q > Qmem) q = (u32)Qmem;
if (q > N) q = N;
g_Q = q;
g_B = (N + q - 1) / q;
}
const u32 Q = g_Q, B = g_B;
// [e4f] exact reciprocal for the orders-phase floor(x/B): with 2^divS >= B*N and
// divM = ceil(2^divS/B), floor(x*divM/2^divS) == floor(x/B) for every x < N
// (proof: x*divM/2^divS < x/B + 1/B <= floor(x/B) + 1). N < 2^20 and B <= N, so
// divS <= 40 and x*divM < 2^60 fits u64.
u64 divM; int divS;
{ u64 t = (u64)B * (u64)N; divS = 0;
while (divS < 64 && ((u64)1 << divS) < t) divS++;
divM = ((u64)1 << divS) / B + 1; }
#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
// [W2] the coarse-cell ladder must be fixed up-front: s_bnde (boundaries in
// value space) and the per-query cell index must use the SAME shift, otherwise
// the filter stops being a tight superset (measured: 7.5x more candidates).
if (g_use_filt) { int sh = 0; while ((sh < 32) && (((u64)1 << sh) < (u64)N)) sh++;
g_cshift = sh; }
{
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 = LDU((const __m256i *)lo8);
khi8hv = LDU((const __m256i *)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];
// Counting sort + rank record in sequential passes: start[v] = #{q : x_d[q] < v}
// is exactly gt[] of every point with x_d == v, and end[v]-1 = start[v+1]-1 is the
// last rank of that tie group, so bd[] follows from start[v+1] too. Both are value
// lookups, so the per-point work is a sequential sweep of xd[] instead of the
// previous random xd[od[j]] read plus random gt[]/bd[] writes.
for (u32 i = 0; i <= N; i++) s_cntv[i] = 0;
for (u32 i = 0; i < N; i++) {
if (i + MF_ORDP < N) { u32 vf = xd[i + MF_ORDP]; Y14Z_PFW(&s_cntv[vf < N ? vf : 0]); }
u32 v = xd[i]; s_cntv[v < N ? v : 0]++;
}
{ u32 s = 0; for (u32 i = 0; i <= N; i++) { u32 c = s_cntv[i]; s_cntv[i] = s; s_tmp[i] = s; s += c; } }
{ u32 *pp = s_pos[d];
for (u32 i = 0; i < N; i++) {
if (i + MF_ORDP < N) { u32 vf = xd[i + MF_ORDP]; if (vf >= N) vf = 0;
Y14Z_PFW(&od[s_tmp[vf]]); }
u32 v = xd[i]; if (v >= N) v = 0; u32 q = s_tmp[v]++; od[q] = i; pp[i] = q;
} }
{ u32 *gt = s_gt[d];
// [Y14Z-GTPF] gt 趟：`gt[i] = s_cntv[v]`（v = xd[i]）是对 4 MB 计数数组的**随机读**，每维 1e6 次 × k 维。
// 前瞻地址只经过顺序流 xd[]（§2.19.339 无二级依赖）。与同相位已兑现的计数/散写两趟同形态。
for (u32 i = 0; i < N; i++) {
if (i + MF_ORDP_GT < N) { u32 vf = xd[i + MF_ORDP_GT]; if (vf >= N) vf = 0; Y14Z_PT(s_cntv + vf); }
u32 v = xd[i]; if (v >= N) v = 0;
gt[i] = s_cntv[v];
u32 bb = (u32)(((u64)(s_cntv[v + 1] - 1u) * divM) >> divS);
s_bdv[(size_t)d * N + i] = (unsigned short)(bb > Q - 1 ? Q - 1 : bb);
} }
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;
}
// [d4b] one blocked transpose: dim-major -> record layout. The per-dim pass
// above only ever stores 4 B per 32-B record (8/64 B of a line), so 8 passes
// touch 8*N/2 lines with RFO; writing the dim-major plane is dense (4 MB per
// pass) and this single dense transpose replaces that line traffic 1:1.
for (u32 i = 0; i < N; i++) {
unsigned short *dst = s_bd + (size_t)i * MAXK;
for (int d = 0; d < k; d++) dst[d] = s_bdv[(size_t)d * N + i];
}
for (u32 i = 0; i < N; i++) {
u32 *p = PMROWK(i, g_pstr);
for (int d = 0; d < k; d++) p[d] = x[d][i];
for (int d = k; d < STRIDE; d++) p[d] = 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;
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 = CBOUND(c);
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), LDA((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) {
if (ptr + MF_ORP < N) Y14Z_PT(pd + pe[ptr + MF_ORP]);
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), LDA((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;
}
for (u32 i = 0; i < N; 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; }
}
s_g[i] = (u32)ds;
// 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).
if (g_plen_on) {
const unsigned short *bdv = s_bd + (size_t)i * MAXK;
u32 *mr = s_maxr + ((size_t)ds * MAXK) * MAXQ;
u32 bb = best;
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; }
// Low 20 bits fit every point ID (N <= 1,000,005); upper bits fit bucket.
// s_bdv is dimension-major, so each d's bucket lookups stay cache-local.
for (int d = 0; d < k; d++) {
u32 pos[MAXK];
for (int ds = 0; ds < k; ds++) pos[ds] = gstart[ds];
const u32 *od = s_ord[d];
const unsigned short *bd = s_bdv + (size_t)d * N;
for (u32 r = 0; r < N; r++) {
u32 id = od[r];
u32 dst = pos[s_g[id]]++;
s_frord[d][dst] = id | ((u32)bd[id] << 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_PFB4 < N) _mm_prefetch((const char *)(PMROWK(od[j + MF_PFB4], g_pstr)), _MM_HINT_T0);
#endif
const u32 *row = PMROWK(od[j], g_pstr);
u32 *dp = dst + (size_t)j * KSx;
for (u32 e = 0; e < KSx; e++) dp[e] = (e < (u32)k) ? row[e] : 0u;
}
}
}
}
}
// ---------- 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;
// ---------- 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
// bit numbering = rank in dim ds
const u32 *const nid = 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];
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) {
if (ptr + MF_ORP < N) Y14Z_PT(nid + od[ptr + MF_ORP]);
u32 q = nid[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), LDA((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
}
switch (k) {
case 4: query_group<4>(N, out, ds, q0, q1, Q, Wpool); break;
case 5: query_group<5>(N, out, ds, q0, q1, Q, Wpool); break;
case 6: query_group<6>(N, out, ds, q0, q1, Q, Wpool); break;
case 7: query_group<7>(N, out, ds, q0, q1, Q, Wpool); break;
case 8: query_group<8>(N, out, ds, q0, q1, Q, Wpool); break;
case 9: query_group<9>(N, out, ds, q0, q1, Q, Wpool); break;
default: query_group<10>(N, out, ds, q0, q1, Q, Wpool); break;
}
}
}
void count_4d(int n, const unsigned *x[4], unsigned *out) { solve_mf((u32)n, (const unsigned **)x, out, 4); }
void count_5d(int n, const unsigned *x[5], unsigned *out) { solve_mf((u32)n, (const unsigned **)x, out, 5); }
void count_6d(int n, const unsigned *x[6], unsigned *out) { solve_mf((u32)n, (const unsigned **)x, out, 6); }
void count_7d(int n, const unsigned *x[7], unsigned *out) { solve_mf((u32)n, (const unsigned **)x, out, 7); }
void count_8d(int n, const unsigned *x[8], unsigned *out) { solve_mf((u32)n, (const unsigned **)x, out, 8); }
void count_9d(int n, const unsigned *x[9], unsigned *out) { solve_mf((u32)n, (const unsigned **)x, out, 9); }
void count_10d(int n, const unsigned *x[10], unsigned *out) { solve_mf((u32)n, (const unsigned **)x, out, 10); }
#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 | 5.491 s | 1022 MB + 704 KB | Accepted | Score: 100 | 显示更多 |