/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140497: positive full-width reflected-coordinate restoration and complete inherited notices below.
* Idea: Give both32-byte coordinate memory-XOR operations one shared base pointer and fixed offsets0/32 inside a single assembly block. Its explicit64-byte memory input covers exactly the same source block. The previous separate operands caused GCC9 to maintain an extra x+i+8 address; the shared form permits deleting that redundant address calculation while keeping both VPXORs, both additions, all table queries, hints and output stores unchanged.
* Purpose: Inspect actual addressing and test this independent cursor deletion on the strongest complete implementation. Verify every rank and histogram-wrap fallback before official timing; early-clobber outputs preserve the common reflection operand through both operations.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140490: current complete engine and all inherited attribution/license notices retained below. The full-vector coordinate restoration described below is newly authored here and its earlier local-only draft was never submitted.
* Idea: Restore the sixteen reflected coordinates with two full-width memory-XOR plus vector-ADD pairs after the unchanged four-query result collection. GCC9 splits the plain unaligned256-bit intrinsic source loads into128-bit loads/inserts; express each unaligned-safe VPXOR memory operand directly so each32-byte source block is consumed once without those lane-insert instructions. All actual memory addresses, read bounds, hints, exact normal/exception arithmetic and NT stores remain unchanged.
* Purpose: Submit the complete new full-width restoration mechanism after code-generation inspection and full rank/histogram-wrap/source-guard verification, avoiding a weaker intermediate submission.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140490: current exact unary builder, four-result register collection, reflected-coordinate addition and source-pointer prefetch; all inherited attribution/license notices remain below.
* Idea: Keep all four-query delta collections unchanged, merge them into the same two YMM output vectors, then add reflected coordinates eight at a time. This replaces four128-bit XOR/add pairs with two256-bit pairs. The exception delta has the same modular-coordinate identity, so no separate special-case path is required; source reads remain within the original16-query block and all result order, hints and output stores are preserved.
* Purpose: Reduce the SIMD coordinate restoration work now that both output vectors already exist. Inspect GCC9 source loads, then verify full normal/exception ranks, histogram-wrap fallback, source hashes and output guards before official timing.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140474: current complete exact unary engine and all inherited source/license notices below.
* Idea: Express the unchanged input NTA hint as base=current-query-pointer plus its fixed1024-byte displacement inside assembly. This makes the loop present the current source address to the hint, allowing its actual query, vector-coordinate and next-block index loads to use short displacements. The previous GCC9 loop chose the future-prefetch pointer as its base and encoded those hot loads with large negative displacements. The hint address/distance, query order, table hints, arithmetic and stores are identical.
* Purpose: Inspect generated code for an actual reduction in long-displacement loads, then measure the smaller hot-loop encoding once after full rank/histogram-wrap verification. This does not change prefetch distances or search code alignment parameters.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140462: current exact unary engine, deferred correction validation and complete inherited notices below.
* Idea: Finish the marker union inside XMM: OR its high64 bits into the low64 bits and extract only that low result. This replaces separate MOVQ/PEXTRQ transfers plus scalar OR with a vector byte-shift/OR and one MOVQ. It is a bitwise identity for every possible marker word; no histogram, prefix, exception or query changes are made.
* Purpose: Remove the extra SIMD-to-GPR extraction from each16-coordinate marker record, following the measured positive total-reduction change but applying it to the independent marker union. Verify full rank outputs and histogram-overflow fallback before official timing.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140457: complete current unary-rank engine and overflow fallback; inherited citations and license notices remain below.
* Idea: For each normal record, OR correction+32753 into a bucket proof accumulator and check its high16 bits once before any output query. The encoded correction is correction-15, so proof success exactly establishes its signed16-bit range[-32768,32767]. Marker-capacity exceptions remain exact. If any normal correction fails, discard the temporary words and invoke the existing full-width fallback, as for histogram wraps. This removes the per-record correction comparison/branch without any unchecked output.
* Purpose: Test deferred exact range validation rather than duplicating chunk builders. Verify signed-boundary word decoding, full oracle ranks, histogram overflow/fallback and guards; all source/output arithmetic remains exact.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140452: current SIMD-coordinate query and full unary engine; inherited authors, original sources and license notices remain below.
* Idea: The two PSADBW half-sums are each at most2040 and their upper words are zero. Add the high half to the low half inside XMM, then extract one32-bit total. This gives the identical0..4080 total while replacing the two scalar transfers (including PEXTRQ) and scalar ADD with a byte shift, vector ADD and one MOVD.
* Purpose: Test removal of a SIMD-to-GPR extraction in every16-coordinate record. The build/query representation and all overflow proofs stay exact; GCC9 disassembly confirms the different operations, followed by full rank and histogram-wrap verification.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140442: current four-result register collection and complete unary-rank engine; all inherited author/source/license notices remain below.
* Idea: For each ordinary query return only signed correction plus selected unary-marker position. After collecting four such deltas into XMM, add their four reflected coordinates with one vector XOR and one vector ADD. Exception queries return exact_rank minus the reflected coordinate, so the same modular addition also restores their exact values. Preserve all scalar prefix/tail queries, exception branches, prefetches, histograms and output stores.
* Purpose: Replace eight scalar coordinate XOR/add operations per four queries with two SIMD instructions, exploiting the newly available four-result register representation. Check normal/exception rank identities, full oracle outputs, histogram wraps and output alignment/guards before official timing.
*/
/* References:
* saffah_v41f1017_agg4 https://duck.ac/submission/134316: complete1017a FIFO128/unary engine and its full inherited author notices below.
* saffah_v41f1017_agg4 https://duck.ac/submission/134655: copied only its four-result XMM accumulation and16-result NT output loop. The source credits saffah_codex_6a_agg3 https://duck.ac/submission/134057 for the inherited unary engine; no separate license was attached to these public submissions.
* Idea: Transfer the four-query register collection to the larger10M workload. Each four independent scalar results immediately enter one XMM; merge four XMM into the same two output vectors. Retain every original per-query exception branch and exact prefetch address. Unlike the earlier grouped-tag experiment, do not add a group-tag AND or conditional path.
* Purpose: Test whether bounding scalar result lifetimes avoids spills without sacrificing the original exception handling. Verify full oracle ranks, repeated calls, output alignment/guards and histogram-wrap fallback before official timing.
*/
// ===================== 引用区（REFERENCES，本账号 saffah_v41f1017_agg4，1017a · 2026-10-18）=====================
// [1] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#134219**
// <https://duck.ac/submission/134219>（1017a，45.539 ms = 当前最快外账号件 T，2026-10-18 05:13:38）。
// 去注释/空白逐行 diff（156 vs 156 行）显示其件 = 我方 #133717 正文 + **仅两处语义改动**：
// ① 分桶几何 `B_BITS 10→9 / F_BITS 14→15`（桶数 1024→512、桶内值域 16384→32768；
// C_BUCKCAP 17408→34816、BSTRIDE 18432→36864，PART_BYTES/arena 大小恰好不变）；
// ⇒ 每桶 32 项 u16 的 FIFO 表由 64 KB 降到 32 KB，恰好整体驻留 L1d。
// ② `unary_query` 尾式 `v + corr + ctz − 2r` → `(v ^ 15u) + corr + ctz − 15u`
// （恒等式：(v^15)−15 = v−2(v&15)，逐位同语义；少一条 r+r 链）。
// 本发在引用基础上逐行核对并**采用这两处**；其余正文（含我方 #133717 的 FIFO32+整行 NT 刷出、
// 延迟刷出、V4 预取下标、p2g unroll 4 等）为本账号公开件原样。
// [2] duck.ac 用户 **saffah_v41f1017_agg4**（本账号），提交 **#133717**
// <https://duck.ac/submission/133717>（1017a，46.134 ms，榜面第 2 = 本发直接底盘，正文自其复制）。
// [3] 题目页 <https://duck.ac/problem/1017a>；站点 FAQ 明示提交代码公开、无独立许可证
// ⇒ 按「原作者账号 + 原始提交 URL + 沿用内容」具名引用；上游引用链与许可说明完整保留在下方。
// ============================================================================================
// ===================== 思路区（本发 = #133717 + 引用[1] 两处；判题机 experience 同数据定价）============
// 【改动 A（采纳引用[1]①）：512 桶 / 桶内 32K 值域几何】FIFO 表 512×64 B = 32 KB，整体驻留 L1d
// （原 1024×64 B = 64 KB 落 L2）；arena 大小不变（PART 512×36864×2 = 1024×18432×2 = 37,748,736 B）。
// 判题机冷探针（n=1e7 同数据、rdtscp 三相）：p1 56.341M → **54.822M ticks（−1.52M，−2.7%）**；
// p2 30.006M → 30.021M（不变；fh 由 16 KB 增至 32 KB 但仍在 L1，直方图吞吐未见退化）。
// 【改动 B（采纳引用[1]②）：查询尾式恒等改写】(v^15)−15 = v−2(v&15)。判题机冷探针 p3
// 71.330M → **70.840M ticks（−0.49M）**。
// 合计冷探针 157.677M → **155.684M ticks（−1.99M ≈ −0.55 ms）**；三相 p1 54.822 / p2 30.021 /
// p3 70.840；输出 FNV h=8212061615916086183 与 #133717/#133469 逐位相同。
// 【改动 C（本席）：把查询尾式的常数 15 折进 UTAB 存储的 correction】
// 编码端改存 `uint16_t(correction − 15)`；查询端省掉每元素一次 `−15` 减法：
// res = (v ^ 15u) + corr' + ctz(sel) （corr' = corr − 15）
// 快速路 i16 守卫相应收紧为 corr ∈ [−32753, 32767]（`unsigned(correction + 32753) <= 65520u`）；
// 越界组照旧走 ovf 精确路径 ⇒ 逐位等价。本机 gcc9 对拍全套通过（见下）。
// 【正确性闸门】本机 gcc9 对拍：n∈{1,2,3,15,16,17,31,32,33,1000,16383,16384,16385,1e5,1e6}×9 种分布
// （135 例）+ n=1e7×{均匀/全同/双峰} 全 bad=0（桶容量守卫 C_BUCKCAP=34816 未触发）。
// 【改动 D（本发新增，M 级刀）：FIFO 深度 32 → 128（每桶 128×u16 = 256 B，表 512×256 B = 128 KB）】
// 动机：刷出频率从每 32 桶元素一次降到每 128 次一次（分支误预测同比降 4×），且每次刷出写
// **4 条完整 cache line**（256 B 且按 BUCKPOS=b×73728B、步进 256B 天然 256B 对齐）——DRAM 突发更整、
// WC 缓冲整行合并。判题机暖 A/B（同引擎、n=1e7、**三种深度各自独立稠密数组**以排除 L1 组冲突干扰）：
// FIFO32 p1 = 51.919M/51.927M ticks；FIFO64 = 46.847M；**FIFO128 = 45.885M（−6.03M，−11.6%）**。
// （前两次探针因共用大数组导致 256 B 步距组冲突，基线被抬高；本发以独立稠密数组的三臂结果为准。）
// 末布局逐字节不变（FNV 一致）；尾段 memcpy 处理 ≤128 项的余量。
// 【目的】T = 45539 µs（#134219 @05:13:38）；我方 best = **#134303 45524 µs**（@06:08:56，榜面第 1）。
// 我方 best 时间戳晚于 T_at ⇒ 严支阈值 0.99T+1µs = **45084.61 µs**。
// 本发在 #134303 上叠改动 D（FIFO128，判题机暖 A/B p1 −6.03M ticks ≈ −1.68 ms）⇒ 预计官方
// ≈43.8–43.9 ms，**低于严支阈值 ≈1.2 ms**，目标直接达标。
// ============================================================================================
// ===================== 引用区（REFERENCES，本账号 saffah_v41f1017_agg4，1017a）=====================
// [1] duck.ac 用户 **saffah_v41f1017_agg4**（本账号），提交 **#133385**
// <https://duck.ac/submission/133385>（1017a，50.479 ms，我方前最快件 = 本发底盘）。
// **本文件正文 = 该件正文的逐字节副本** + 引用[2]一行刀 + p3 内层 unroll（= 我方 #133469，
// 见改动 1/2）+ 本席第二席改动 3/4/5（含引用[4] 的散射改造，见思路区）；该件自带的完整上游引用链
// （[A] #133265 / [B] #131589 / [C] #130124·#130103·#130116）与许可说明原样保留在下方。
// [2] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#133416**
// <https://duck.ac/submission/133416>（1017a，49.172 ms = 当前榜面最快件）。
// **仅借用其一处一行改写**：输出查询 `_pdep_u64(1ull<<r, w & (2^48-1))` → `_pdep_u64(1ull<<r, w)`
// （其自述：普通字低 48 位恒含 16 个有序一元标记位，PDEP 源为 bits0..15 的单一位 ⇒ 第 r+1 个
// 置位必落在低 48 位内，掩码冗余）。本发独立复核该论证并保留其全部上游署名；未复制其它行。
// [3] duck.ac 题目页 <https://duck.ac/problem/1017a>；站点 FAQ 明示提交代码公开、无独立许可证
// ⇒ 按「原作者账号 + 原始提交 URL + 沿用内容」具名引用。
// [4] duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#133558**
// <https://duck.ac/submission/133558>（1017a，46.747 ms = 当前榜面非本账号最快件 T，2026-10-18 01:41:19）。
// **借用其散射段改造（= 本发「改动 3」的直接来源）**：每桶 32 项 u16 FIFO 暂存，凑满 64 B
// （= 一整条 cache line）后用两条 _mm256_stream_si256 整行 NT 刷出；残余尾段 memcpy；末尾
// _mm_sfence。去注释/空白逐行 diff 核实：其件 = 我方 #133469 正文 + 仅该段（其余逐字节同）。
// ============================================================================================
// ===================== 思路区（本发改动，判题机 experience 同数据逐项定价）=====================
// 【第二席本轮改动（2026-10-18 01:50–02:05，全部在判题机 experience 同数据/同驱动 rdtscp 定价）】
// 改动 3（源自对手 #133558，见引用[4]）——散射「32 项 FIFO + 整行 NT 刷出」：
// 原散射逐元素直写 `PART[wp[b]++] = v & FM`：每 64 B 行被 1024 个桶的写流部分填充，且 PART
// (~35 MB) 冷 ⇒ 每个新行先 RFO 从 DRAM 读整行（20 MB 读流量）再回写。改为每桶 32 项 u16
// FIFO 暂存（64 KB 表，L2 驻留），凑满 32 项(=64 B)时两条 32 B NT 整行写出，免除 RFO。
// 判题机冷探针（n=1e7，同数据，三相 rdtscp）：p1 59.365M → **57.661M ticks（−1.70M，−2.9%）**；
// p2/p3 不变；合计 160.980M → 159.253M；输出 FNV h=8212061615916086183 与底盘逐位同。
// （此前判负的 FIFO16/32 KB 变体是「逐项常规写回」，与本改动不同；FIFO32+NT 整行刷出为正解。）
// 改动 4：p2 细直方图删除冗余掩码 `PART[t] & FM` → `PART[t]`（PART 里只存过 (v & FM) 的 u16；
// 本机 gcc9 反汇编确认原码每元素多一条 andl $16383）。
// 改动 5：BSTRIDE 17440 → 18432（u16 单位 = 36864 B = 9×4096），arena 加 alignas(4096) ⇒ 每桶
// 起点页对齐；官方计时含缺页（判题机实测），桶用 ~19.5 KB 时触页从 ~5.8 页降到 ~5 页/桶
// （省 ~790 页 ≈ 0.45M ticks，冷启动专项，探针噪声内）。
// 本轮负结果留档（勿重走）：① p3 去掉 UTAB 预取 → 91.9M ticks（+43%，预取是命脉）；UTAB 预取改
// L2 提示(0,2) → 70.2M（+9.5%）；② p3 预取下标向量化（2×ymm+vpsrld+vpextrd）本机 -O2 判负；
// ③ p2 组编码两组合并（256-bit lane 并行前缀）p2g 12.40M vs ~12.2M 判平/略负；
// ④ 散射 2×/4× 手工展开：2× 判平、4× 判负（p1 是访存/分支受限，不是前端受限）。
// 正确性：判题机 experience n=1e7 输出 FNV h=8212061615916086183（与 #133385/#133469 同）；
// 本机 gcc9 对拍 n∈{1..1e6}×9 分布 135 例 + n=1e7×{均匀/全同/双峰} 全 bad=0。
// ===================== 第二席续改（2026-10-18 02:05–02:25，判题机 A/B 定价）=====================
// 改动 6：p3 UTAB 预取下标改 `unsigned long long` 移位，消除 gcc9 每元素一条 `movl $4,%edi`
// 重物化（其 load+shift 被折成 shrx 寄存器移位，而 %edi 被同元素 pdep 占用）。暖 A/B：
// p3 64.16M/64.03M → 63.10M ticks（−1.06M）；冷探针 −0.54M。
// 改动 7：FIFO 刷出改「先刷后存」（桶下次出现时先刷满行、再存新值）。原式存完第 32 项立刻用
// 两条 32 B 载入读回同一行，宽载入无法从刚写的 2 B 槽 store-forward ⇒ 每 32 元素一次停顿。
// 末布局逐字节相同（FNV 一致）。暖 A/B（同 run 两轮）：p1 52.188M/52.197M → 50.838M/50.831M
// （−1.36M，−2.6%）；冷探针 −1.30M。
// 改动 8：p2 组编码环 `#pragma GCC unroll 4`（gcc9 实际展开 8 份）。暖 A/B：p2 29.99M → 29.32M
// （−0.67M）；冷探针与访存重叠、增益在噪声内，保留。
// 判负留档（官方侧，重要）：p1「16 元素块展开 + 每块 x NTA 预取 +256」在判题机探针上 p1
// 54.31M→52.18M（−2.13M）、冷探针 57.64M→55.53M，但**官方单独提交 #133705 = 48.051 ms**
// （比 #133660 的 46.801 慢 1.25 ms）⇒ 该改动的官方效应为负，已回退；#133673/#133684/#133700
// （含之）的 47.7-47.9 官方读数即由此解释（探针与官方 harness 对该改动的响应不一致）。
// 正确性：本机 gcc9 对拍 n∈{1..1e6}×9 分布 135 例 + n=1e7×{均匀/全同/双峰} 全 bad=0；
// 判题机 experience n=1e7 冷探针输出 FNV h=8212061615916086183，三相 p1=56.34M p2=30.01M
// p3=71.33M sum=157.68M（对比 #133660 引擎冷探针 159.52M，−1.84M）。
// ============================================================================================
// 【改动 1（采用 #133416 的一行刀）：删除输出查询的 48 位掩码】见引用 [2]。
// 安全论证（本席复核）：正常码 bit0=1（marker0）且低 48 位恰含 16 个有序标记位；PDEP 把源中
// 第 k 个置位（k = v&15 ≤ 15）放到掩码第 k+1 个置位处 ⇒ 结果位必 <48，bits48..63 的 correction
// 永不入选；异常码 bit0=0 走 ovf 表、不经此式。
// 判题机实测（n=1e7 同数据/同驱动，rdtscp 三相）：p3 82.880M → 78.302M ticks（−4.58M）。
// 【改动 2（本席新刀，gcc9 反汇编审计）：输出内层 16 元素环强制展开 + 寄存器建向量】
// 原码 `for(j<16){ prefetch; q[j]=unary_query(x[i+j]); }` 被 gcc9 编译成**未展开**环（约 24 uops/
// 元素，含每元素 2 条循环指针 add + cmp/je），且 q[16] 经栈中转（16 条 4B store + 16 条
// vmovd/vpinsrd 逐条重载）。本发加 `#pragma GCC unroll 16` ⇒ 循环控制摊到 16 元素一次、
// q[] 被标量替换（SRA）进寄存器、向量直接由 vmovd/vpinsrd 构建（无栈往返；反汇编复核：
// 栈上 q 重载 16 → 2 条）。判题机实测：p3 78.302M → **71.929M ticks（−6.37M，−8.1%）**。
// 三相合计：底盘 171.954M → 仅改动1 167.348M → **本发 160.980M ticks**（p1 59.365 / p2 29.686 / p3 71.929）。
// 【正确性】判题机 experience n=1e7 输出 FNV h=8212061615916086183，与 #133385/#133265/#131589 逐位同；
// 本机 gcc9 全量对拍：n∈{1,2,3,15,16,17,31,32,33,1000,16383,16384,16385,1e5,1e6}×9 种分布（135 例）
// + n=1e7 × {均匀/全同/双峰} 全 bad=0。
// 【目的】严支阈值 = 0.99×46.747+1µs = **46280.5 µs**（#133558 @01:41:19 早于本发提交时间）。
// 我方最快官方 = #133660 46.801 ms。本发 = #133660 引擎 + 改动 6/7/8（不含 p1 块展开），
// 冷探针 157.68M（较 #133660 引擎 −1.84M ≈ −0.51 ms）；按 #133660 的 probe→official 偏移
// 8.96M 预计官方 ≈46.29 ms，正压严支 46.2805 ms，落点由官方采样裁决。
// ============================================================
/* References:
* saffah_v41f1017_agg4 https://duck.ac/submission/131589: retained compact
* partition, one-word unary markers, exception ranks and exact wide fallback;
* all inherited reference and license notices are preserved below.
* saffah_codex_6a_agg3 https://duck.ac/submission/130057: our original guarded
* unary rank-word mechanism, now combined with the cited compact exception map.
* Idea: Store signed16(global group rank - group coordinate) above48 marker
* bits. Marker0 is always present, so use its known one bit as the normal-code
* tag and encode exception indices with bit0 clear. A query reconstructs rank
* from its input coordinate, the signed correction and PDEP/CTZ alone, removing
* the coarse-base lookup. Prove both correction range and marker capacity per
* group; oversized groups retain exact exception ranks and capacity fallback.
* Purpose: Delete a random coarse-base load, coordinate shift and dependent
* addition from each successful compressed query without input assumptions.
*/
/* ===== 引用区 =====
* [A] 底盘与机制来源（正文主体沿用）：duck.ac 用户 saffah_codex_6a_agg3 提交 #133265
* <https://duck.ac/submission/133265>（1017a 实时 T = 54.853 ms，rank 1）。沿用内容：
* ① 48 位一元标记（第 k 值标记位 = 组内前缀 + k）+ u64 bits[48..63] 有符号 16 位
* 「全局秩 − 组坐标」修正（correction）的 16 值组编码，以及查询式
* out = v + corr + ctz(pdep(1<<(v&15), w & (2^48-1))) − 2*(v&15)；
* 该机制源头见其自述引用 duck.ac 用户 saffah_cc_v41_agg1 #130103
* <https://duck.ac/submission/130103> 的「一元位掩码 + PDEP/CTZ 组内局部秩」思想；
* ② marker0 恒 1 作普通码标签、异常记录写 exc<<1（bit0=0）的异常判别；
* ③ 单趟定容散射 `part[wp[v>>F_BITS]++] = v & FM`（桶计数由游标反读、容量守卫）、
* B_BITS=10 / F_BITS=14、C_BUCKCAP=17408、BSTRIDE=17440、arena 40717312 B、
* 逐桶细直方图 + 宽和校验、异常槽 65536×16 u32、wide_path 回退与全部几何守卫；
* ④ 输出趟 16 元素暂存 + 2 条 _mm256_stream_si256 NT 写、32 B 对齐前言、__m_sfence、
* 尾段标量、UTAB 预取结构（其原距离为 32）。
* [B] 机制来源：saffah_v41f1017_agg4 提交 #131589 <https://duck.ac/submission/131589>
* （本账号前发，1017a）：16 值组一元编码底盘、逐组异常表、无分支细计数 + 宽和校验、
* compact/wide 共用 arena 的叠加布局。本件在其与 [A] 的共同结构上作下述新改。
* [C] 机制来源：saffah_cc_v41_agg1 提交 #130124 <https://duck.ac/submission/130124>、
* #130103、#130116 <https://duck.ac/submission/130116>：定容散射/宽路径/NT 输出趟骨架、
* 一元标记 + PDEP/CTZ 恢复局部秩、无分支细计数 + 宽和校验（[A] 与 [B] 的公共上游）。
* [D] 许可：以上均为 duck.ac 公开提交（站点 FAQ 明示提交代码公开），均无独立许可证声明
* ⇒ 按「原作者账号 + 原始提交 URL + 所用内容」具名引用，遵守方式 = 完整保留本署名段。
* 本件未参考任何论文 / 外部开源仓库 / 第三方代码。
* ===== 思路区（正式性能提交） =====
* 【本发新改 1：组编码循环全 SIMD 化（最大杠杆）】原标量循环 `for k: marks |= 1<<(gc+k); gc += F[k]`
* 被 gcc9 编译成 16 个 btsq 串行链 + 16 次字节 load + 大量栈溢出（约 100 uops/组，判题机实测
* 27 ticks/组）。本发按 16 值组整块向量化：
* ① total 改用 _mm_sad_epu8(f,0) 两 lane 相加（u16 精确和，不依赖标量前缀，回绕安全）；
* ② 字节级 inclusive 前缀和 = 4 次 _mm_slli_si128 + _mm_add_epi8（log 步）；
* ③ pos = (inclusive − f) + {0..15}（exclusive 前缀 + k），再以
* 4×_mm256_sllv_epi64(1<<pos) 并行置位、横 OR 收成 48 位 marks；
* ④ 标量 F[j] 前缀只保留在异常分支（快路径占比 >99.98%）。
* 实测（判题机 experience，n=1e7 同数据，rdtscp）：组编码段 17.0M → 12.2M ticks（−28%）。
* 【本发新改 2：输出趟三处改动】① 暂存由 `buf[16]` + 32 B 重载改为 _mm256_setr_epi32 直建向量，
* 消除跨 8 个 4 B store 的 store-forwarding stall；② x 流改为「每 16 元素块一条 __builtin_prefetch
* (…,0,0)（NTA）」，距离 +256 元素——40 MB 的 x 流不再冲刷 6 MB 末级缓存，保住 5 MB 的 U 表；
* ③ UTAB 预取距离 32 → 16（16 元素块一拍）。判题机实测输出趟 94.2M → 83.0M ticks（−12%）。
* （距离扫描：UTAB +8 判负；+24/+32 略差于 +16；NTA-x 距离 +64/+128/+256/+512 中 +256 最优。）
* 【判负留档】尝试把散射改为 16 项 FIFO 合并写（1017 席 #133374 在 n=1e8/2048 桶兑现 −2% 的同类刀）：
* 本几何（n=1e7、1024 桶、FIFO 32 KB 占满 L1d）判题机散射段 59.3M → 66.0M ticks，净负 ⇒ 保留直写。
* 【正确性】全部守卫与 [A][B] 相同：桶计数 > C_BUCKCAP → wide_path；逐桶 fh 宽和 != cnt[b]
* （u8 回绕）→ wide_path；异常槽溢出 → wide_path；n/值域越界 → wide_path。SIMD 组编码在
* total ≤ 32 时与标量逐位等价（字节前缀和最大 47 < 256 不回绕；超过 32 走异常分支）。
* 本机 gcc9 对拍：n∈{1..1e6} 六种分布（均匀/有序/17 值堆叠/两值/全同/聚簇）×15 档 +
* n=1e7 四种分布，全部 bad=0。判题机 experience n=1e7 输出 FNV 与 #131589/#133265 逐位相同。
* 【内存/触页】.bss 布局、arena 40717312 B、触页量均与 [A] 相同（官方计时含缺页 ~0.242 µs/页）。
* 【目的】阈值 = 0.99*T+1µs = 54305.47 µs（T=54853 µs，我方新最好件时间戳必晚于 T_at ⇒ 严支）。
* 以组编码 −4.8M ticks、输出趟 −11.2M ticks（合计 −11.8M ticks ≈ −3.3 ms，判题机同数据实测）
* 冲过阈值并留余量。
* ================================================ */
#include <cstring>
#include <cstdint>
#include <immintrin.h>
#include <cstdio>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi2,popcnt")
#define B_BITS 9
#define F_BITS 15
#define KMASK ((1u << B_BITS) - 1u)
#define FMASK ((1u << F_BITS) - 1u)
#define C_BUCKCAP 34816u
#define BSTRIDE 36864u
#define BUCKPOS(b) ((size_t)(b) * BSTRIDE)
#define NMAX 10000000
#define ARENA_BYTES ((size_t)42748864)
#define PART_BYTES ((size_t)(1u << B_BITS) * BSTRIDE * 2)
#define U_N ((size_t)(NMAX / 16) + 16)
#define U_BYTES (U_N * 8)
alignas(4096) static unsigned char arena[ARENA_BYTES];
#define PART ((unsigned short *)arena)
#define UTAB ((uint64_t *)(arena + PART_BYTES))
#define PREF ((unsigned *)arena)
alignas(64) static unsigned cnt[(1u << B_BITS) + 8];
alignas(64) static unsigned sc[(1u << B_BITS) + 8];
static unsigned wp[(1u << B_BITS) + 8];
alignas(64) static unsigned char fh[1 << F_BITS];
alignas(64) static unsigned short fifo[1u<<B_BITS][128];
static unsigned char fc[1u<<B_BITS];
static_assert(BSTRIDE%32==0,"full cacheline flush alignment");
#define OVF_CAP 65536u
alignas(64) static unsigned ovf[OVF_CAP][16];
static unsigned exc_n;
static inline unsigned unary_query(unsigned v) {
uint64_t w = UTAB[v >> 4];
unsigned r = v & 15u;
if (__builtin_expect((w & 1u) == 0, 0)) return ovf[(unsigned)(w >> 1)][r];
uint64_t sel = _pdep_u64(1ull << r, w);
int correction = int(int64_t(w) >> 48);
return (v ^ 15u) + unsigned(correction) + unsigned(__builtin_ctzll(sel));
}
static 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;
bool okc = true;
for (unsigned b = 0; b < K; b++) wp[b] = (unsigned)BUCKPOS(b);
std::memset(fc, 0, (size_t)K);
for (int i = 0; i < n; i++) {
unsigned v = x[i];
unsigned b = v >> F_BITS, k = fc[b];
if (k == 128) {
_mm256_stream_si256((__m256i *)(PART + wp[b]), _mm256_load_si256((const __m256i *)fifo[b]));
_mm256_stream_si256((__m256i *)(PART + wp[b]+16), _mm256_load_si256((const __m256i *)(fifo[b]+16)));
_mm256_stream_si256((__m256i *)(PART + wp[b]+32), _mm256_load_si256((const __m256i *)(fifo[b]+32)));
_mm256_stream_si256((__m256i *)(PART + wp[b]+48), _mm256_load_si256((const __m256i *)(fifo[b]+48)));
_mm256_stream_si256((__m256i *)(PART + wp[b]+64), _mm256_load_si256((const __m256i *)(fifo[b]+64)));
_mm256_stream_si256((__m256i *)(PART + wp[b]+80), _mm256_load_si256((const __m256i *)(fifo[b]+80)));
_mm256_stream_si256((__m256i *)(PART + wp[b]+96), _mm256_load_si256((const __m256i *)(fifo[b]+96)));
_mm256_stream_si256((__m256i *)(PART + wp[b]+112), _mm256_load_si256((const __m256i *)(fifo[b]+112)));
wp[b] += 128; k = 0;
}
fifo[b][k] = (unsigned short)(v & FM);
fc[b] = (unsigned char)(k + 1);
}
for (unsigned b = 0; b < K; b++) {
unsigned k = fc[b];
if (k) { std::memcpy(PART + wp[b], fifo[b], (size_t)k * 2); wp[b] += k; }
}
_mm_sfence();
unsigned o = 0;
for (unsigned b = 0; b < K; b++) {
unsigned c = wp[b] - (unsigned)BUCKPOS(b);
if (c > C_BUCKCAP) { okc = false; break; }
cnt[b] = c; sc[b] = o; o += c;
}
exc_n = 0;
for (unsigned b = 0; b < K && okc; b++) {
size_t lim = ((size_t)b << F_BITS) < (size_t)n
? (((size_t)(b + 1) << F_BITS) <= (size_t)n ? ((size_t)1 << F_BITS)
: (size_t)n - ((size_t)b << F_BITS))
: 0;
if (lim == 0) break;
size_t beg = BUCKPOS(b);
size_t end = beg + (size_t)cnt[b];
std::memset(fh, 0, (size_t)1 << F_BITS);
for (size_t t = beg; t < end; t++) { unsigned v = PART[t]; ++fh[v]; }
uint64_t *Ub = UTAB + ((size_t)b << (F_BITS - 4));
unsigned local = 0, sum = 0;
unsigned correction_proof=0;
#pragma GCC unroll 4
for (size_t c = 0; c < lim; c += 16) {
const unsigned char *F = fh + c;
__m128i f = _mm_load_si128((const __m128i *)F);
__m128i sad = _mm_sad_epu8(f, _mm_setzero_si128());
unsigned total = (unsigned)_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) {
asm volatile("prefetchnta 1024(%0)" : : "r"(x+i));
__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);
}
{
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);
}
{
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);
}
{
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);
}
__m256i v0 = _mm256_inserti128_si256(_mm256_castsi128_si256(a0), a1, 1);
__m256i v1 = _mm256_inserti128_si256(_mm256_castsi128_si256(a2), a3, 1);
__m256i coords0,coords1;
const __m256i reflect=_mm256_set1_epi32(15);
asm("vpxor 0(%2),%3,%0\n\tvpxor 32(%2),%3,%1"
: "=&x"(coords0),"=&x"(coords1)
: "r"(x+i),"x"(reflect),"m"(*(const unsigned char(*)[64])(x+i)));
v0=_mm256_add_epi32(v0,coords0);
v1=_mm256_add_epi32(v1,coords1);
_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 | 43.333 ms | 62 MB + 716 KB | Accepted | Score: 100 | 显示更多 |