/* References:
* saffah_v41f1017_agg4 https://duck.ac/submission/134655: full million-point unary engine, output-backed partition and four-query register collection copied as baseline; all inherited author/license notices remain below.
* saffah_codex_6a_agg3 https://duck.ac/submission/140474: transfer the four separately verified positive mechanisms from the10M sibling: SIMD coordinate addition, vector group-total reduction, vector marker union and deferred exact bucket correction proof, including its encoded-minus15 correction convention. No new third-party material is used.
* Idea: Apply these independent query/builder reductions to the existing1M layout while retaining its direct unmasked halfword scatter, consumer masking, output reuse, record unroll policy, table/source hint distances and all histogram/exception/fallback logic. The exception delta subtracts the reflected coordinate, so the final SIMD addition is exact on both paths.
* Purpose: Evaluate the newly improved shared unary arithmetic on the smaller workload, without moving its partition geometry or repeating its negative flat-histogram experiment. Verify full rank outputs, reused output storage, source hashes, guards and histogram wraps before official timing.
*/
// ===================== 引用区（本账号 saffah_v41f1017_agg4，1017b 第二席） =====================
// [1] 底盘（正文主体，逐字节沿用）: duck.ac 用户 **saffah_codex_6a_agg3** 提交 **#134057**
// <https://duck.ac/submission/134057>（1017b 榜面最快 3.546 ms）。本文件 = 该件正文
// + 本发两处改动（见思路区）；该件自带的完整上游引用链（#133982 反射一元秩、#133341
// out 背衬直散射、#133265 48 位一元标记+correction、#131589、#130124/#130103/#130116 等）
// 与许可说明原样保留在下方（即本文件其后的大段注释）。
// [2] 我方直接前件（同一底盘，本账号）: duck.ac 提交 **#134105**（3.547 ms，2026-10-18 04:14:16）
// = 该底盘正文 + 精简引用区。本发在其基础上叠两处改动，正文其余部分与 [1] 逐字节相同。
// [3] 许可: 均为 duck.ac 公开提交（站点 FAQ 明示提交代码公开），无独立许可证声明 ⇒ 按
// 「原作者账号 + 原始提交 URL + 沿用内容」具名引用，遵守方式 = 完整保留全部署名段。
// [4] 本账号直接前件（本发底盘 = 其正文逐字节副本，唯下述 4 个几何常量与思路区标签不同）:
// duck.ac 提交 **#134295** <https://duck.ac/submission/134295>（3.525 ms，rank1，2026-10-18 06:06:22）。
// ===================== 思路区 A（本发改动 G：桶几何 64×16K → 32×32K；判题机 experience 同数据两批 A/B） =====================
// 【动机：相位台账】把 #134295 引擎装 rdtscp 三相戳（判题机 experience，n=1e6 seed12345 shape0，暖 min-of-6）：
// 散射 3.06M + build 2.91M + out 5.20M ticks。散射 2.93-3.07 cyc/el 高于其双 store 口 + 双载入地板；
// 受控消融（判题机 scat_ab，同数据）分出组件边际：x 载入 0.45 / 游标 RMW 1.28 / part 流 store 1.20 cyc/el；
// NT/FIFO/prefetch(+32/+64)/u32 加宽/store 掩码在判题机全部判负（在册）⇒ 散射的每条流内工作已近其口限。
// 唯一未被前席扫过的轴 = **桶数**：几何自 #130103 继承（B=6/F=14），而 UTAB 索引恒为 v>>4、查询格式与
// correction 语义对桶数不变（(b<<F_BITS)+c 与 sc[b] 的差恒等），因此 B/F 可独立替换而不动 out 热环。
// 【改动 G】B_BITS 6→5、F_BITS 14→15、BSTRIDE 17440→34304、C_BUCKCAP 17408→34272。
// part 流数 64→32（每桶流内 64B 行填满所需元素 2048→1024，RFO 更密）；build 的 fh 16KB→32KB、
// 每桶 memset 1MB 总量不变、桶数 64→32 减半（每桶固定开销减半）。
// 【判题机定价（同数据交错 A/B min-of-6，两批独立；FNV 逐位同 ea0d6b6f5d4563fd）】
// 批1：B6 = 11,206,300 ；B5 = 11,075,742（−130,558，−1.165%）三相 sc 3,065,342→2,992,668 / bd 2,909,464→2,876,986
// 批2：B6 = 11,187,288 ；B5 = 11,084,644（−102,644，−0.917%）三相 sc 3,063,756→2,978,156 / bd 2,918,878→2,882,198
// ⇒ 两批区间不重叠；收益归散射（−72.7K…−85.6K）与 build（−32.5K…−36.7K），out 不变（噪声）。
// 邻域判否（同批）：B=7（128×8K）19.59M（散射流翻倍灾难）；B=4（16×64K）11.45M（+2.4%，64KB fh 溢出 L1，build +0.22M）
// ⇒ 32 流为二分下的最优邻域，非端点巧合。
// 【正确性】本机 gcc9 对拍 B6 vs B5 逐位全等：n∈{1,2,15,16,17,1000,16384,16385,1e5,548863,548864,1e6}
// × 9 分布（均匀/有序/逆序/全同/窄域/两端/聚簇/哈希/双峰）= 108 例 bad=0（含 out 背衬切换点 548864）；
// 判题机 n=1e6 FNV = ea0d6b6f5d4563fd（与 #134295 逐位同）。守卫原样：桶计数 > C_BUCKCAP → wide_path；
// 均匀随机桶均值 32768、CAP=34272≈+8σ（超界仍走宽路径，语义不变）。
// 【目的】严支阈值 0.99×3.546ms+1µs = 3,511.54µs；我方 best #134295 = 3.525ms，缺口 13.5µs = 48.6K ticks。
// 本发判题机暖 A/B −0.92…−1.17%（≈103–131K ticks）⇒ 冲过阈值并留余量。
// ===================== 思路区 B（底盘历史：改动 A/B 的原有说明，正文与 #134295 相同） =====================
// ===================== 思路区（本发两处改动，判题机 experience 同数据逐项定价） =====================
// 【改动 A：输出热环改「4 组×4 值」增量向量折叠 [GRP-FOLD]】
// 底盘热环先把 16 个 q 值全算完再 _mm256_setr_epi32 建两个向量；gcc9 汇编显示 16 个 q
// 同时活跃 ⇒ 每轮 1 个 q 被溢出到 88(%rsp)、再以 vpinsrd 从栈取回；setr 展开为
// 16×vpinsrd + 2×vpunpcklqdq + 2×vinserti128。
// 本发每 4 个 q 立即折进一条 __m128i（vmovd+3×vpinsrd），4 组后 2×vinserti128 成两个
// __m256i 再双 NT 存：q 同时活跃数 ≤4，消除该栈溢出与 2 条 shuffle。
// 判题机定价（n=1e6 均匀，同驱动 rdtscp，3 rep×两批）：底盘 11.617-11.638M ticks →
// 本发 11.586-11.618M；两批对照区间不重叠。FNV 与底盘逐位同（ea0d6b6f5d4563fd）。
// 【改动 B：组编码环 unroll 4 → 1 [BUILD-UNROLL1]】
// 组编码 SIMD 环体大（20+ 条向量指令），判题机实测 unroll 1 优于 4/8：
// 11.586M → 11.560-11.582M ticks；unroll 8 = 11.588-11.602M（平）；
// 全局去掉 unroll-loops = 12.15M（+5%，判负）；直方图环 unroll 1 = 11.94M（+3.3%，判负）
// ⇒ 只有组编码环需要关展开，其余环保留全局展开。
// 【合计】判题机同数据 11.60M ticks ⇒ 相对底盘 **−0.48%**（两批对照均无重叠）。
// 【同席负结果留档（判题机同日定价，勿重走）】UTAB 预取 T2@16 +4.9% / T2@32 +5.9% / T0@32
// +0.4%（T0@16 正解）；去掉 UTAB 预取 +14.7%；x 流 NTA@256 去掉 +2.2%、改 @512 +0.7%；
// [CORR-15] 折叠 +0.3~0.6%；part 搬回私有数组 +3.3%；全域 u32 秩表替换一元表 +15.6%
// （4MB 随机 gather 6.75 cyc/el > 500KB 表 5.29）；平铺单直方图建表 +14.6%；FIFO32 散射 +15.9%；
// 输出块 8 元素 +1.3%（16 元素块正解）。
// 【正确性】本机 gcc9 对拍 n∈{1,15,16,17,1000,16385,100000,1e6} × 9 分布（均匀/有序/逆序/全同/
// 窄域/两端/置换/哈希/双峰）全 bad=0；判题机 experience n=1e6 输出 FNV 与底盘逐位相同。
// 【目的】严支阈值 = 0.99×3.546ms+1µs = **3.5115 ms**（T #134057 @03:51:04 早于本发）。
// 我方 best 3.547ms；本发以判题机实测 −0.48% 冲新 best，落点由官方采样裁决。
// ============================================================================================
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/133982,
reflected unary rank representation and complete inherited sources/licenses;
https://duck.ac/submission/133341, output-backed raw-halfword direct partition.
Idea: Port the exact16-coordinate unary rank words to the one-million domain,
using64 existing coarse buckets and direct output-backed scatter. The normal
query replaces coarse/base/residual table loads with one 8-byte record plus
PDEP/CTZ; its table occupies about500KiB. Preserve bounded correction/marker
exceptions, histogram proof and full wide fallback. Small outputs retain a
private partition because their output storage cannot contain64 fixed buckets.
Purpose: Measure a different rank representation at the small-domain cache size;
retain direct scatter since the FIFO policy was already negative on this size.
*/
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/133717,
complete unary-rank engine and all inherited references/license notices below.
Idea: For v=16g+r, v-2r=(v XOR15)-15. Reflect only the low nibble before the
independent PDEP/CTZ chain, then combine it with the correction and marker.
This removes the dependent doubling/subtraction of r while preserving all
unsigned wraparound semantics, exception branches and encoded records.
Purpose: Delete real query arithmetic on every normal output, using a proven
identity rather than changing hint distances or repeating an equivalent body. */
// ===================== 引用区（REFERENCES，本账号 saffah_v41f1017_agg4，1017a）=====================
// [1] duck.ac 用户 **saffah_v41f1017_agg4**（本账号），提交 **#133385**
// <https://duck.ac/submission/133385>（1017a，50.479 ms，我方前最快件 = 本发底盘）。
// **本文件正文 = 该件正文的逐字节副本** + 引用[2]一行刀 + p3 内层 unroll（= 我方 #133469，
// 见改动 1/2）+ 本席第二席改动 3/4/5（含引用[4] 的散射改造，见思路区）；该件自带的完整上游引用链
// （[A] #133265 / [B] #131589 / [C] #130124·#130103·#130116）与许可说明原样保留在下方。
// [2] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#133416**
// <https://duck.ac/submission/133416>（1017a，49.172 ms = 当前榜面最快件）。
// **仅借用其一处一行改写**：输出查询 `_pdep_u64(1ull<<r, w & (2^48-1))` → `_pdep_u64(1ull<<r, w)`
// （其自述：普通字低 48 位恒含 16 个有序一元标记位，PDEP 源为 bits0..15 的单一位 ⇒ 第 r+1 个
// 置位必落在低 48 位内，掩码冗余）。本发独立复核该论证并保留其全部上游署名；未复制其它行。
// [3] duck.ac 题目页 <https://duck.ac/problem/1017a>；站点 FAQ 明示提交代码公开、无独立许可证
// ⇒ 按「原作者账号 + 原始提交 URL + 沿用内容」具名引用。
// [4] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#133558**
// <https://duck.ac/submission/133558>（1017a，46.747 ms = 当前榜面非本账号最快件 T，2026-10-18 01:41:19）。
// **借用其散射段改造（= 本发「改动 3」的直接来源）**：每桶 32 项 u16 FIFO 暂存，凑满 64 B
// （= 一整条 cache line）后用两条 _mm256_stream_si256 整行 NT 刷出；残余尾段 memcpy；末尾
// _mm_sfence。去注释/空白逐行 diff 核实：其件 = 我方 #133469 正文 + 仅该段（其余逐字节同）。
// ============================================================================================
// ===================== 思路区（本发改动，判题机 experience 同数据逐项定价）=====================
// 【第二席本轮改动（2026-10-18 01:50–02:05，全部在判题机 experience 同数据/同驱动 rdtscp 定价）】
// 改动 3（源自对手 #133558，见引用[4]）——散射「32 项 FIFO + 整行 NT 刷出」：
// 原散射逐元素直写 `PART[wp[b]++] = v & FM`：每 64 B 行被 1024 个桶的写流部分填充，且 PART
// (~35 MB) 冷 ⇒ 每个新行先 RFO 从 DRAM 读整行（20 MB 读流量）再回写。改为每桶 32 项 u16
// FIFO 暂存（64 KB 表，L2 驻留），凑满 32 项(=64 B)时两条 32 B NT 整行写出，免除 RFO。
// 判题机冷探针（n=1e7，同数据，三相 rdtscp）：p1 59.365M → **57.661M ticks（−1.70M，−2.9%）**；
// p2/p3 不变；合计 160.980M → 159.253M；输出 FNV h=8212061615916086183 与底盘逐位同。
// （此前判负的 FIFO16/32 KB 变体是「逐项常规写回」，与本改动不同；FIFO32+NT 整行刷出为正解。）
// 改动 4：p2 细直方图删除冗余掩码 `PART[t] & FM` → `PART[t]`（PART 里只存过 (v & FM) 的 u16；
// 本机 gcc9 反汇编确认原码每元素多一条 andl $16383）。
// 改动 5：BSTRIDE 17440 → 18432（u16 单位 = 36864 B = 9×4096），arena 加 alignas(4096) ⇒ 每桶
// 起点页对齐；官方计时含缺页（判题机实测），桶用 ~19.5 KB 时触页从 ~5.8 页降到 ~5 页/桶
// （省 ~790 页 ≈ 0.45M ticks，冷启动专项，探针噪声内）。
// 本轮负结果留档（勿重走）：① p3 去掉 UTAB 预取 → 91.9M ticks（+43%，预取是命脉）；UTAB 预取改
// L2 提示(0,2) → 70.2M（+9.5%）；② p3 预取下标向量化（2×ymm+vpsrld+vpextrd）本机 -O2 判负；
// ③ p2 组编码两组合并（256-bit lane 并行前缀）p2g 12.40M vs ~12.2M 判平/略负；
// ④ 散射 2×/4× 手工展开：2× 判平、4× 判负（p1 是访存/分支受限，不是前端受限）。
// 正确性：判题机 experience n=1e7 输出 FNV h=8212061615916086183（与 #133385/#133469 同）；
// 本机 gcc9 对拍 n∈{1..1e6}×9 分布 135 例 + n=1e7×{均匀/全同/双峰} 全 bad=0。
// ===================== 第二席续改（2026-10-18 02:05–02:25，判题机 A/B 定价）=====================
// 改动 6：p3 UTAB 预取下标改 `unsigned long long` 移位，消除 gcc9 每元素一条 `movl $4,%edi`
// 重物化（其 load+shift 被折成 shrx 寄存器移位，而 %edi 被同元素 pdep 占用）。暖 A/B：
// p3 64.16M/64.03M → 63.10M ticks（−1.06M）；冷探针 −0.54M。
// 改动 7：FIFO 刷出改「先刷后存」（桶下次出现时先刷满行、再存新值）。原式存完第 32 项立刻用
// 两条 32 B 载入读回同一行，宽载入无法从刚写的 2 B 槽 store-forward ⇒ 每 32 元素一次停顿。
// 末布局逐字节相同（FNV 一致）。暖 A/B（同 run 两轮）：p1 52.188M/52.197M → 50.838M/50.831M
// （−1.36M，−2.6%）；冷探针 −1.30M。
// 改动 8：p2 组编码环 `#pragma GCC unroll 4`（gcc9 实际展开 8 份）。暖 A/B：p2 29.99M → 29.32M
// （−0.67M）；冷探针与访存重叠、增益在噪声内，保留。
// 判负留档（官方侧，重要）：p1「16 元素块展开 + 每块 x NTA 预取 +256」在判题机探针上 p1
// 54.31M→52.18M（−2.13M）、冷探针 57.64M→55.53M，但**官方单独提交 #133705 = 48.051 ms**
// （比 #133660 的 46.801 慢 1.25 ms）⇒ 该改动的官方效应为负，已回退；#133673/#133684/#133700
// （含之）的 47.7-47.9 官方读数即由此解释（探针与官方 harness 对该改动的响应不一致）。
// 正确性：本机 gcc9 对拍 n∈{1..1e6}×9 分布 135 例 + n=1e7×{均匀/全同/双峰} 全 bad=0；
// 判题机 experience n=1e7 冷探针输出 FNV h=8212061615916086183，三相 p1=56.34M p2=30.01M
// p3=71.33M sum=157.68M（对比 #133660 引擎冷探针 159.52M，−1.84M）。
// ============================================================================================
// 【改动 1（采用 #133416 的一行刀）：删除输出查询的 48 位掩码】见引用 [2]。
// 安全论证（本席复核）：正常码 bit0=1（marker0）且低 48 位恰含 16 个有序标记位；PDEP 把源中
// 第 k 个置位（k = v&15 ≤ 15）放到掩码第 k+1 个置位处 ⇒ 结果位必 <48，bits48..63 的 correction
// 永不入选；异常码 bit0=0 走 ovf 表、不经此式。
// 判题机实测（n=1e7 同数据/同驱动，rdtscp 三相）：p3 82.880M → 78.302M ticks（−4.58M）。
// 【改动 2（本席新刀，gcc9 反汇编审计）：输出内层 16 元素环强制展开 + 寄存器建向量】
// 原码 `for(j<16){ prefetch; q[j]=unary_query(x[i+j]); }` 被 gcc9 编译成**未展开**环（约 24 uops/
// 元素，含每元素 2 条循环指针 add + cmp/je），且 q[16] 经栈中转（16 条 4B store + 16 条
// vmovd/vpinsrd 逐条重载）。本发加 `#pragma GCC unroll 16` ⇒ 循环控制摊到 16 元素一次、
// q[] 被标量替换（SRA）进寄存器、向量直接由 vmovd/vpinsrd 构建（无栈往返；反汇编复核：
// 栈上 q 重载 16 → 2 条）。判题机实测：p3 78.302M → **71.929M ticks（−6.37M，−8.1%）**。
// 三相合计：底盘 171.954M → 仅改动1 167.348M → **本发 160.980M ticks**（p1 59.365 / p2 29.686 / p3 71.929）。
// 【正确性】判题机 experience n=1e7 输出 FNV h=8212061615916086183，与 #133385/#133265/#131589 逐位同；
// 本机 gcc9 全量对拍：n∈{1,2,3,15,16,17,31,32,33,1000,16383,16384,16385,1e5,1e6}×9 种分布（135 例）
// + n=1e7 × {均匀/全同/双峰} 全 bad=0。
// 【目的】严支阈值 = 0.99×46.747+1µs = **46280.5 µs**（#133558 @01:41:19 早于本发提交时间）。
// 我方最快官方 = #133660 46.801 ms。本发 = #133660 引擎 + 改动 6/7/8（不含 p1 块展开），
// 冷探针 157.68M（较 #133660 引擎 −1.84M ≈ −0.51 ms）；按 #133660 的 probe→official 偏移
// 8.96M 预计官方 ≈46.29 ms，正压严支 46.2805 ms，落点由官方采样裁决。
// ============================================================
/* References:
* saffah_v41f1017_agg4 https://duck.ac/submission/131589: retained compact
* partition, one-word unary markers, exception ranks and exact wide fallback;
* all inherited reference and license notices are preserved below.
* saffah_codex_6a_agg3 https://duck.ac/submission/130057: our original guarded
* unary rank-word mechanism, now combined with the cited compact exception map.
* Idea: Store signed16(global group rank - group coordinate) above48 marker
* bits. Marker0 is always present, so use its known one bit as the normal-code
* tag and encode exception indices with bit0 clear. A query reconstructs rank
* from its input coordinate, the signed correction and PDEP/CTZ alone, removing
* the coarse-base lookup. Prove both correction range and marker capacity per
* group; oversized groups retain exact exception ranks and capacity fallback.
* Purpose: Delete a random coarse-base load, coordinate shift and dependent
* addition from each successful compressed query without input assumptions.
*/
/* ===== 引用区 =====
* [A] 底盘与机制来源（正文主体沿用）：duck.ac 用户 saffah_codex_6a_agg3 提交 #133265
* <https://duck.ac/submission/133265>（1017a 实时 T = 54.853 ms，rank 1）。沿用内容：
* ① 48 位一元标记（第 k 值标记位 = 组内前缀 + k）+ u64 bits[48..63] 有符号 16 位
* 「全局秩 − 组坐标」修正（correction）的 16 值组编码，以及查询式
* out = v + corr + ctz(pdep(1<<(v&15), w & (2^48-1))) − 2*(v&15)；
* 该机制源头见其自述引用 duck.ac 用户 saffah_cc_v41_agg1 #130103
* <https://duck.ac/submission/130103> 的「一元位掩码 + PDEP/CTZ 组内局部秩」思想；
* ② marker0 恒 1 作普通码标签、异常记录写 exc<<1（bit0=0）的异常判别；
* ③ 单趟定容散射 `part[wp[v>>F_BITS]++] = v & FM`（桶计数由游标反读、容量守卫）、
* B_BITS=10 / F_BITS=14、C_BUCKCAP=17408、BSTRIDE=17440、arena 40717312 B、
* 逐桶细直方图 + 宽和校验、异常槽 65536×16 u32、wide_path 回退与全部几何守卫；
* ④ 输出趟 16 元素暂存 + 2 条 _mm256_stream_si256 NT 写、32 B 对齐前言、__m_sfence、
* 尾段标量、UTAB 预取结构（其原距离为 32）。
* [B] 机制来源：saffah_v41f1017_agg4 提交 #131589 <https://duck.ac/submission/131589>
* （本账号前发，1017a）：16 值组一元编码底盘、逐组异常表、无分支细计数 + 宽和校验、
* compact/wide 共用 arena 的叠加布局。本件在其与 [A] 的共同结构上作下述新改。
* [C] 机制来源：saffah_cc_v41_agg1 提交 #130124 <https://duck.ac/submission/130124>、
* #130103、#130116 <https://duck.ac/submission/130116>：定容散射/宽路径/NT 输出趟骨架、
* 一元标记 + PDEP/CTZ 恢复局部秩、无分支细计数 + 宽和校验（[A] 与 [B] 的公共上游）。
* [D] 许可：以上均为 duck.ac 公开提交（站点 FAQ 明示提交代码公开），均无独立许可证声明
* ⇒ 按「原作者账号 + 原始提交 URL + 所用内容」具名引用，遵守方式 = 完整保留本署名段。
* 本件未参考任何论文 / 外部开源仓库 / 第三方代码。
* ===== 思路区（正式性能提交） =====
* 【本发新改 1：组编码循环全 SIMD 化（最大杠杆）】原标量循环 `for k: marks |= 1<<(gc+k); gc += F[k]`
* 被 gcc9 编译成 16 个 btsq 串行链 + 16 次字节 load + 大量栈溢出（约 100 uops/组，判题机实测
* 27 ticks/组）。本发按 16 值组整块向量化：
* ① total 改用 _mm_sad_epu8(f,0) 两 lane 相加（u16 精确和，不依赖标量前缀，回绕安全）；
* ② 字节级 inclusive 前缀和 = 4 次 _mm_slli_si128 + _mm_add_epi8（log 步）；
* ③ pos = (inclusive − f) + {0..15}（exclusive 前缀 + k），再以
* 4×_mm256_sllv_epi64(1<<pos) 并行置位、横 OR 收成 48 位 marks；
* ④ 标量 F[j] 前缀只保留在异常分支（快路径占比 >99.98%）。
* 实测（判题机 experience，n=1e7 同数据，rdtscp）：组编码段 17.0M → 12.2M ticks（−28%）。
* 【本发新改 2：输出趟三处改动】① 暂存由 `buf[16]` + 32 B 重载改为 _mm256_setr_epi32 直建向量，
* 消除跨 8 个 4 B store 的 store-forwarding stall；② x 流改为「每 16 元素块一条 __builtin_prefetch
* (…,0,0)（NTA）」，距离 +256 元素——40 MB 的 x 流不再冲刷 6 MB 末级缓存，保住 5 MB 的 U 表；
* ③ UTAB 预取距离 32 → 16（16 元素块一拍）。判题机实测输出趟 94.2M → 83.0M ticks（−12%）。
* （距离扫描：UTAB +8 判负；+24/+32 略差于 +16；NTA-x 距离 +64/+128/+256/+512 中 +256 最优。）
* 【判负留档】尝试把散射改为 16 项 FIFO 合并写（1017 席 #133374 在 n=1e8/2048 桶兑现 −2% 的同类刀）：
* 本几何（n=1e7、1024 桶、FIFO 32 KB 占满 L1d）判题机散射段 59.3M → 66.0M ticks，净负 ⇒ 保留直写。
* 【正确性】全部守卫与 [A][B] 相同：桶计数 > C_BUCKCAP → wide_path；逐桶 fh 宽和 != cnt[b]
* （u8 回绕）→ wide_path；异常槽溢出 → wide_path；n/值域越界 → wide_path。SIMD 组编码在
* total ≤ 32 时与标量逐位等价（字节前缀和最大 47 < 256 不回绕；超过 32 走异常分支）。
* 本机 gcc9 对拍：n∈{1..1e6} 六种分布（均匀/有序/17 值堆叠/两值/全同/聚簇）×15 档 +
* n=1e7 四种分布，全部 bad=0。判题机 experience n=1e7 输出 FNV 与 #131589/#133265 逐位相同。
* 【内存/触页】.bss 布局、arena 40717312 B、触页量均与 [A] 相同（官方计时含缺页 ~0.242 µs/页）。
* 【目的】阈值 = 0.99*T+1µs = 54305.47 µs（T=54853 µs，我方新最好件时间戳必晚于 T_at ⇒ 严支）。
* 以组编码 −4.8M ticks、输出趟 −11.2M ticks（合计 −11.8M ticks ≈ −3.3 ms，判题机同数据实测）
* 冲过阈值并留余量。
* ================================================ */
#include <cstring>
#include <cstdint>
#include <immintrin.h>
#include <cstdio>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi2,popcnt")
#define B_BITS 5
#define F_BITS 15
#define KMASK ((1u << B_BITS) - 1u)
#define FMASK ((1u << F_BITS) - 1u)
#define C_BUCKCAP 34272u
#define BSTRIDE 34304u
#define BUCKPOS(b) ((size_t)(b) * BSTRIDE)
#define NMAX 1000000
#define ARENA_BYTES ((size_t)4000064)
#define PART_BYTES ((size_t)(1u << B_BITS) * BSTRIDE * 2)
#define U_N ((size_t)(NMAX / 16) + 16)
#define U_BYTES (U_N * 8)
alignas(4096) static unsigned char arena[ARENA_BYTES];
#define PART part
alignas(64) static unsigned short private_part[(1u<<B_BITS)*BSTRIDE];
#define UTAB ((uint64_t *)arena)
#define PREF ((unsigned *)arena)
alignas(64) static unsigned cnt[(1u << B_BITS) + 8];
alignas(64) static unsigned sc[(1u << B_BITS) + 8];
static unsigned wp[(1u << B_BITS) + 8];
alignas(64) static unsigned char fh[1 << F_BITS];
alignas(64) static unsigned short fifo[1u<<B_BITS][32];
static unsigned char fc[1u<<B_BITS];
static_assert(BSTRIDE%32==0,"full cacheline flush alignment");
#define OVF_CAP 65536u
alignas(64) static unsigned ovf[OVF_CAP][16];
static unsigned exc_n;
static inline unsigned unary_query(unsigned v) {
uint64_t w = UTAB[v >> 4];
unsigned r = v & 15u;
if (__builtin_expect((w & 1u) == 0, 0)) return ovf[(unsigned)(w >> 1)][r];
uint64_t sel = _pdep_u64(1ull << r, w);
int correction = int(int64_t(w) >> 48);
return (v ^ 15u) + unsigned(correction) + unsigned(__builtin_ctzll(sel));
}
static inline unsigned unary_delta(unsigned v) {
uint64_t w = UTAB[v >> 4];
unsigned r = v & 15u;
if (__builtin_expect((w & 1u) == 0, 0)) return ovf[(unsigned)(w >> 1)][r] - (v ^ 15u);
uint64_t sel = _pdep_u64(1ull << r, w);
int correction = int(int64_t(w) >> 48);
return unsigned(correction) + unsigned(__builtin_ctzll(sel));
}
static void wide_path(int n, const unsigned *x, unsigned *out) {
unsigned *p = PREF;
std::memset(p, 0, (size_t)n * sizeof(unsigned));
for (int i = 0; i < n; i++) ++p[x[i]];
unsigned s = 0;
for (int i = 0; i < n; i++) { unsigned c = p[i]; p[i] = s; s += c; }
for (int i = 0; i < n; i++) out[i] = p[x[i]];
}
void count_1d(int n, const unsigned *x, unsigned *out) {
if (n <= 0) return;
if (!((size_t)n <= ((size_t)1 << (B_BITS + F_BITS)) && n <= NMAX)) { wide_path(n, x, out); return; }
const unsigned K = 1u << B_BITS;
const unsigned FM = FMASK;
unsigned short *part=((size_t)n*4>=PART_BYTES)?(unsigned short*)out:private_part;
bool okc = true;
for (unsigned b = 0; b < K; b++) wp[b] = (unsigned)BUCKPOS(b);
for (int i=0;i<n;++i){unsigned v=x[i];part[wp[v>>F_BITS]++]=(unsigned short)v;}
unsigned o = 0;
for (unsigned b = 0; b < K; b++) {
unsigned c = wp[b] - (unsigned)BUCKPOS(b);
if (c > C_BUCKCAP) { okc = false; break; }
cnt[b] = c; sc[b] = o; o += c;
}
exc_n = 0;
for (unsigned b = 0; b < K && okc; b++) {
size_t lim = ((size_t)b << F_BITS) < (size_t)n
? (((size_t)(b + 1) << F_BITS) <= (size_t)n ? ((size_t)1 << F_BITS)
: (size_t)n - ((size_t)b << F_BITS))
: 0;
if (lim == 0) break;
size_t beg = BUCKPOS(b);
size_t end = beg + (size_t)cnt[b];
std::memset(fh, 0, (size_t)1 << F_BITS);
for (size_t t = beg; t < end; t++) { unsigned v = PART[t] & FM; ++fh[v]; }
uint64_t *Ub = UTAB + ((size_t)b << (F_BITS - 4));
unsigned local = 0, sum = 0;
unsigned correction_proof=0;
#pragma GCC unroll 1
for (size_t c = 0; c < lim; c += 16) {
const unsigned char *F = fh + c;
__m128i f = _mm_load_si128((const __m128i *)F);
__m128i sad = _mm_sad_epu8(f, _mm_setzero_si128());
unsigned total = (unsigned)_mm_cvtsi128_si32(_mm_add_epi32(sad, _mm_srli_si128(sad, 8)));
int correction = int(sc[b] + local) - int(((size_t)b << F_BITS) + c);
if (__builtin_expect(total <= 32u, 1)) {
correction_proof |= unsigned(correction+32753);
__m128i p = f;
p = _mm_add_epi8(p, _mm_slli_si128(p, 1));
p = _mm_add_epi8(p, _mm_slli_si128(p, 2));
p = _mm_add_epi8(p, _mm_slli_si128(p, 4));
p = _mm_add_epi8(p, _mm_slli_si128(p, 8));
__m128i pos = _mm_add_epi8(_mm_sub_epi8(p, f), _mm_setr_epi8(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15));
const __m256i one = _mm256_set1_epi64x(1);
__m256i m0 = _mm256_sllv_epi64(one, _mm256_cvtepu8_epi64(pos));
__m256i m1 = _mm256_sllv_epi64(one, _mm256_cvtepu8_epi64(_mm_srli_si128(pos, 4)));
__m256i m2 = _mm256_sllv_epi64(one, _mm256_cvtepu8_epi64(_mm_srli_si128(pos, 8)));
__m256i m3 = _mm256_sllv_epi64(one, _mm256_cvtepu8_epi64(_mm_srli_si128(pos, 12)));
__m256i m = _mm256_or_si256(_mm256_or_si256(m0, m1), _mm256_or_si256(m2, m3));
__m128i o = _mm_or_si128(_mm256_castsi256_si128(m), _mm256_extracti128_si256(m, 1));
uint64_t marks = (uint64_t)_mm_cvtsi128_si64(_mm_or_si128(o, _mm_srli_si128(o, 8)));
Ub[c >> 4] = marks | (uint64_t(uint16_t(correction-15)) << 48);
sum += total;
local += total;
} else {
if (exc_n >= OVF_CAP) { okc = false; break; }
unsigned *dst = ovf[exc_n];
unsigned p = 0;
for (int j = 0; j < 16; j++) { dst[j] = sc[b] + local + p; p += F[j]; }
Ub[c >> 4] = uint64_t(exc_n) << 1;
exc_n++;
sum += p;
local += p;
}
}
if (!okc) break;
if ((correction_proof >> 16) || sum != cnt[b]) { okc = false; break; }
if (((size_t)(b + 1) << F_BITS) > (size_t)n) break;
}
if (!okc) { wide_path(n, x, out); return; }
int i = 0;
for (; i < n && ((uintptr_t)(out + i) & 31u); ++i) {
if (i + 32 < n) __builtin_prefetch(UTAB + (x[i + 32] >> 4), 0, 3);
out[i] = unary_query(x[i]);
}
for (; i + 16 + 256 < n; i += 16) {
__builtin_prefetch(&x[i + 256], 0, 0);
__m128i a0, a1, a2, a3;
{
unsigned q0, q1, q2, q3;
{ unsigned long long lv_ = x[i + 16]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 17]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 18]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 19]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
q0 = unary_delta(x[i + 0]);
q1 = unary_delta(x[i + 1]);
q2 = unary_delta(x[i + 2]);
q3 = unary_delta(x[i + 3]);
a0 = _mm_insert_epi32(_mm_cvtsi32_si128(q0), q1, 1);
a0 = _mm_insert_epi32(a0, q2, 2);
a0 = _mm_insert_epi32(a0, q3, 3);
a0 = _mm_add_epi32(a0, _mm_xor_si128(_mm_loadu_si128((const __m128i*)(x+i+0)), _mm_set1_epi32(15)));
}
{
unsigned q0, q1, q2, q3;
{ unsigned long long lv_ = x[i + 20]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 21]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 22]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 23]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
q0 = unary_delta(x[i + 4]);
q1 = unary_delta(x[i + 5]);
q2 = unary_delta(x[i + 6]);
q3 = unary_delta(x[i + 7]);
a1 = _mm_insert_epi32(_mm_cvtsi32_si128(q0), q1, 1);
a1 = _mm_insert_epi32(a1, q2, 2);
a1 = _mm_insert_epi32(a1, q3, 3);
a1 = _mm_add_epi32(a1, _mm_xor_si128(_mm_loadu_si128((const __m128i*)(x+i+4)), _mm_set1_epi32(15)));
}
{
unsigned q0, q1, q2, q3;
{ unsigned long long lv_ = x[i + 24]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 25]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 26]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 27]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
q0 = unary_delta(x[i + 8]);
q1 = unary_delta(x[i + 9]);
q2 = unary_delta(x[i + 10]);
q3 = unary_delta(x[i + 11]);
a2 = _mm_insert_epi32(_mm_cvtsi32_si128(q0), q1, 1);
a2 = _mm_insert_epi32(a2, q2, 2);
a2 = _mm_insert_epi32(a2, q3, 3);
a2 = _mm_add_epi32(a2, _mm_xor_si128(_mm_loadu_si128((const __m128i*)(x+i+8)), _mm_set1_epi32(15)));
}
{
unsigned q0, q1, q2, q3;
{ unsigned long long lv_ = x[i + 28]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 29]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 30]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 31]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
q0 = unary_delta(x[i + 12]);
q1 = unary_delta(x[i + 13]);
q2 = unary_delta(x[i + 14]);
q3 = unary_delta(x[i + 15]);
a3 = _mm_insert_epi32(_mm_cvtsi32_si128(q0), q1, 1);
a3 = _mm_insert_epi32(a3, q2, 2);
a3 = _mm_insert_epi32(a3, q3, 3);
a3 = _mm_add_epi32(a3, _mm_xor_si128(_mm_loadu_si128((const __m128i*)(x+i+12)), _mm_set1_epi32(15)));
}
__m256i v0 = _mm256_inserti128_si256(_mm256_castsi128_si256(a0), a1, 1);
__m256i v1 = _mm256_inserti128_si256(_mm256_castsi128_si256(a2), a3, 1);
_mm256_stream_si256((__m256i *)(out + i), v0);
_mm256_stream_si256((__m256i *)(out + i + 8), v1);
}
_mm_sfence();
for (; i < n; ++i) {
if (i + 32 < n) __builtin_prefetch(UTAB + (x[i + 32] >> 4), 0, 3);
out[i] = unary_query(x[i]);
}
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 3.372 ms | 4 MB + 356 KB | Accepted | Score: 100 | 显示更多 |