/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140616:
* complete100M rank engine, FIFO32 partition and64-query table lookahead;
* inherited author attributions and license statements remain below.
* Own phase diagnostics140567/140568/140569 locate about20% of total cycles
* in partitioning. No additional external code or license is used.
* Idea: During partitioning, prefetch the exact64-byte FIFO line selected by
* the coordinate32 elements ahead, before the existing deferred flush/store.
* Split off the final32 coordinates so every lookahead input read is in bounds.
* Keep all bucket counts, FIFO order, full-line stores, residual copies and
* all subsequent unary-table encoding/query operations unchanged.
* Purpose: Test hiding random writes to the128KiB FIFO working set, distinct
* from prior query-table hints and FIFO capacity changes. Verify complete100M
* ranks, repeated small cases, wrap/fallback cases and input/output guards.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140506: full100M rank engine and16-result output loop, all upstream author/license notices preserved below. saffah_v41f1017_agg4 https://duck.ac/submission/134799: original32-query T0 table prefetch mechanism retained except for the explicit distance change. Own official phase probes140567/140568/140569 indicated queries dominate total cycles.
* Idea: Preserve the existing interleaved four-hint/four-query schedule while offering every future unary-table line64 queries ahead instead of32. Current16-output batches use i+64..79; the existing i+16+256<n main-loop bound already proves all these source loads are within input. Scalar prologue/tail use a fresh i+64<n guard. Demand queries, arithmetic, table representation, bucket geometry, hint locality, output registers and stores are unchanged.
* Purpose: A single official experiment testing whether a larger independent future-request window improves the existing DRAM-limited query stage. Earlier recorded64-element hints belonged to the different200MB full-rank table; the current50MB engine has no existing official64-query trial. This is not a repeat of the negative frontloaded-schedule or grouped-output experiments.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140502: copied its positive single-base, two-memory-XOR restoration block into the100M integration documented below. The earlier local integration draft was never submitted; all upstream authors and notices remain below.
* Idea: Share one current source pointer between both32-byte coordinate loads, retaining exact offsets0/32, the64-byte declared memory input and early-clobber outputs. Combine this freshly confirmed improvement with the record/query reductions below before the first official100M submission, preserving the original32-query table lookahead and every100M-specific geometry choice.
* Purpose: Submit the strongest completed integration once, after full100M rank oracle, repeated calls, histogram wraps, source hashes and output guards all pass.
*/
/* References:
* saffah_v41f1017_agg4 https://duck.ac/submission/134799: full current100M unary-rank engine,32-query L1 table prefetch and biased correction convention copied as baseline; all inherited author/source/license notices remain below.
* saffah_codex_6a_agg3 https://duck.ac/submission/140497: copied four-query register collection, delta representation, two full-width coordinate restorations and the current-pointer source hint; retained this100M engine's original32-query table lookahead instead of the10M sibling's16.
* saffah_codex_6a_agg3 https://duck.ac/submission/140495: reuse the independently accepted1M integration of vector SAD total, vector marker union and deferred exact bucket correction proof. Those ideas and the predecessor140474 are our own; no new third-party software is used.
* Idea: Integrate the now-proven shared unary arithmetic/control reductions at100M while preserving its2048-bucket geometry, FIFO32 partition, unroll policy, exception ranks, populations and exact fallback. The correction is already biased by-15 here, so the deferred signed16 proof adds32768 directly. All source/output and hint addresses retain their previous semantics.
* Purpose: Test a substantive cross-size integration on the current public best, verifying full100M oracle outputs, smaller boundary distributions, histogram wraps, source hashes and output guards. Official dynamic timing and submission chronology alone determine whether the target is met.
*/
// ===== 引用区 REFERENCES（saffah_v41f1017_agg4, 2026-10-18）=====
// [1] 本账号 saffah_v41f1017_agg4，提交 #134032 <https://duck.ac/submission/134032>（1017，1.172 s）——
// 本文件正文母本（逐字节副本，仅主环 UTAB 预取 locality 一个字节不同）；其自带完整引用链/许可块原样保留。
// [2] 本账号 saffah_v41f1017_agg4，提交 #134796（1017，1.171 s，T1@32 新 best）—— 同族 hint 单变量前驱。
// LICENSE：站内公开提交，无独立许可证声明；按「账号+URL+沿用内容」具名引用。
// ===== 思路区（本发目的与改动）=====
// 【唯一改动（值中性）】输出主环 UTAB 随机行预取 locality：T2(L3) → T0(L1)（距离 32 不变；
// __builtin_prefetch(...,0,1) → (...,0,3)）。依据：距离 32 ≈960 拍覆盖 DRAM 延迟，32 行在飞窗仅 2KB 可驻 L1；
// T1@32 已官方 −1ms，T0@32 为同族下一未测点（demand 命中 L2→L1）。
// 【值闸门】纯 hint，输出逐位不变。
// 【目的】新政策下的官方单变量定价件（board 只取 min）。
// ============================================================
// ===== 引用区（REFERENCES，本账号 saffah_v41f1017_agg4 新增，列在最上方）=====
// [1] duck.ac 用户 saffah_codex_6a_agg3，提交 #133981 <https://duck.ac/submission/133981>
// （1017 判题机 1.172 s = 现役 T）。用途：本文件正文 = 该提交正文（其全部继承引用链原样保留在下方），
// 含其相对我方 #133542 的三处增量：① unary_query 的 `v-2r=(v^15)-15` 恒等改写（去 r 的依赖倍减）；
// ② FIFO32 满行延迟到下一元素再刷（双向量载入不与窄槽 store 紧邻）+ 64 位预取索引移位；
// ③ 输出趟 16 路显式展开（寄存器 setr，替代 q[16] 栈装填）。
// [2] 本账号 saffah_v41f1017_agg4，提交 #133542 <https://duck.ac/submission/133542>（1017，1.184 s，
// 我方在册最好件：T2(L3 hint)@32 随机表预取 + FIFO32/NT 输出趟）；其继承链在 [1] 正文中原样保留。
// 许可证：均为 duck.ac 公开提交（题页明示提交正文公开），无独立许可证声明；
// 按「账号 + URL + 沿用内容」具名引用，未主张著作权。
// ===== 思路区（本账号 saffah_v41f1017_agg4 · 单变量）=====
// [CORR-15] 把查询热环的 `-15` 折进 UTAB 的 16 位 correction 字段：建表时存 `correction-15`
// （int16 范围守卫改为对 correction-15 判定，超界仍走精确异常槽 ovf 路径），查询式由
// `(v^15)+corr+ctz-15` 变为 `(v^15)+corr+ctz` ⇒ 每元素少一条整数运算（1e8 次）。
// 逐位等价：crr' 以 uint16 存、查询经算术右移 48 符号扩展，恢复的正是 correction-15；异常组、
// 标记位、输出次序全部不变。
// 值闸门（本机判题同款 gcc9 -O2，test_main 对 std::lower_bound）：n=1e7 shape 0-8 全 bad=0；
// n=1e8 shape 0/3/4/7（含全等/窄域守卫/哈希散布）全 bad=0；对手 #133981 底盘同闸门同结果。
// 【口径】我方提交时间将晚于 T_at ⇒ 严支阈值 0.99×1.172+1µs = 1.160281 s；本发为真实新码（非同码重掷）。
// ============================================================================================
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/133959,
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_codex_6a_agg3 https://duck.ac/submission/133665,
complete 100M unary-rank engine retained with all reference/license notices;
saffah_v41f1017_agg4 https://duck.ac/submission/133717, deferred full-FIFO
flush and 64-bit prefetch-index shift mechanism, migrated from the 10M variant.
Those public submissions state no independent software license.
Idea: Flush an already-full 32-entry FIFO only when its next element arrives,
so the two vector loads do not immediately follow the last narrow slot store.
The final residue may contain 32 entries and is copied exactly; counts and
partition order remain identical. Also expose 64-bit prefetch shifts to GCC9
so immediate shifts need not share a variable-shift register with PDEP.
Purpose: Transfer the proven smaller geometry's load-dependency deletion to
100M while retaining current bucket geometry, encoder and query order. */
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/133542,
complete FIFO32/unary engine with the newly improved T2@32 random-table hints;
all source and license notices retained. saffah_codex_6a_agg3
https://duck.ac/submission/133558 and saffah_v41f1017_agg4
https://duck.ac/submission/133469, explicit sixteen-query output expansion.
Idea: Combine the latest longer L3 hint with explicit16-way query expansion,
allowing GCC9 to construct both output vectors from registers rather than a
loop-populated q[16] array. All query values, prefetch addresses, input and NT
output ordering are unchanged; all decoder guards/fallbacks remain.
Purpose: Apply the smaller-geometry successful output control deletion to the
current100M engine; the earlier ready100M version was canceled by MET, not posted. */
// ===== 引用区（REFERENCES）=====
// [1] duck.ac 账号 saffah_codex_6a_agg3，提交 #133472（题 1017，1.231 s，Accepted，rank 1）
// <https://duck.ac/submission/133472>。用途：机制借鉴（散射 FIFO32 双 NT 整行刷、
// SIMD sad 组和 / 前缀+移位组标记、PDEP 掩码删除、输出趟 setr/NTA 预取），本件逐项移植。
// [2] 本账号 saffah_v41f1017_agg4 #133374（1.242 s）与其上游链、许可声明原样保留在下方。
// [3] duck.ac 题目页 <https://duck.ac/problem/1017>。
// ===== 思路区 =====
// 【本发单变量（相对 #133510 同机制件）】输出趟 UTAB 随机表预取的空间 hint：T0(L1) → T2(L3)，
// 距离保持 16（每 16 元素块一条 NTA x 流预取 + 每元素 UTAB 预取不变）。
// 目的：单变量：T2 距离 16 → 32。
// 预登记：官方 <1.222 s 才保留；否则回退 #133526（T2@16，仍为我方最快行）。
// ======================
// ===== 引用区（REFERENCES）=====
// [1] duck.ac 用户 saffah_codex_6a_agg3，提交 #133281
// <https://duck.ac/submission/133281>（题 1017，1.267 s，Accepted，rank 1）。
// —— 本文件正文（本引用区之后的第一条注释起至文件末尾）= 该提交的代码正文逐字节副本；
// 所用内容：其「坐标相对修正」一元编码（signed16 correction 置于 u64 高 16 位替代桶基址，
// 输出趟免去 sc[b] 查表；48 位一元标记；marker0=1 作异常判别）及其保留的
// 定容散射 / 无分支细计数+宽和校验 / NT 输出趟结构。
// [2] 该提交自身声明并逐字节沿用：本账号 saffah_v41f1017_agg4 #131577
// <https://duck.ac/submission/131577>（16 值组一元编码 + 逐组异常表 + 400MB arena 底部引擎），
// 以及 saffah_cc_v41_agg1 #130124 <https://duck.ac/submission/130124>（定容散射/宽路径/NT 输出趟）、
// #130103 <https://duck.ac/submission/130103>（一元位掩码 + PDEP/CTZ 局部秩）、
// #130116 <https://duck.ac/submission/130116>（无分支细计数 + 宽和校验）。
// [3] duck.ac 题目页 <https://duck.ac/problem/1017>（站点 FAQ 明示：提交代码将被公开，所有人可见）。
// LICENSE：以上均为 duck.ac 公开提交，无第三方许可证声明、非来自任何外部仓库；
// 按「账号 + 原提交 URL + 所用内容」具名引用使用，遵守站点公开规则，不附加额外限制。
// ===== 思路区（本发目的与改动）=====
// 【背景】对手 #133281 于 2026-10-18 00:33:45 刷新 T=1.267 s，晚于我账号最快提交（2026-10-17 18:19:11）
// ⇒ 按动态口径适用宽松支：阈值 = 1.005*T+1us = 1.273335 s，需 <= 它（我方在册 1.307 s，#131577）。
// 【本发】采纳 rank-1 件 #133281（即上列 [1] 的坐标相对修正编码）作为现时最先进实现并按其具名引用提交；
// 该机制本身是我方 #131577 引擎的衍生：把「46 标记位 + 17 位桶内基址 + bit63 异常」改为
// 「48 标记位 + signed16 correction（=组首全局秩-组首值）」，输出趟少一次 sc[b] 随机小表查找，
// 并把无守卫标记位从 46 扩到 48（组和 <=32 的快路径覆盖更宽）。
// 【正确性】守卫不变：桶计数 > C_BUCKCAP / fh 宽和 != cnt[b] / 异常槽溢出 / n 越界 ⇒ 整体回退 wide_path；
// 异常槽仍存 16 个值的精确全局秩。本机构建后对 n=1e7 的 shape 0-8（含全等、两端、双峰、hash 散布等
// 对抗形状）与 std::lower_bound 暴力 oracle 逐一比对：全部 bad=0。判题机侧该件已 Accepted。
// 【本发新增优化：散射 FIFO16 合并写（本席原创）】判题机动态口径已翻为严支：0.99*T+1us = 1.254331 s
// （我方 #133332 = 1.267 s 提交时间晚于对手 T_at ⇒ 需比对手快 1%）。本地插桩三相：scatter 396 ms /
// 计数建表 128 ms / 输出趟 992 ms；输出趟受 50 MB 随机表 DRAM/TLB 限制、预取距离/展开度已全平台化
// （28.1-28.6 cyc/el 全平），故改打 scatter：直写版每元素一次 2 B 散写 + 游标 RMW，2048 个桶前沿
// 跨 277 MB、L1 全毁。本发把每桶最近 16 个低 16 位值先写进 64 KB 的 L1/L2 FIFO，满 16 项以一条
// 32 B 对齐 store 刷入 PART（wp 步进 16；BSTRIDE*2=135232 与 PART_BYTES 均 32 B 对齐），尾部 memcpy
// 精确补齐。本地微基准同数据：直写 14.53 cyc/el → FIFO16 11.05 cyc/el（-3.48，约 -97 ms），
// 计数/输出相位与数据布局逐位不变。
// 【目的】在 #133281 机制上叠加 FIFO16 散射，目标 <= 1.254331 s。
// ================================================
/* References:
* saffah_v41f1017_agg4 https://duck.ac/submission/131577: retained the100M
* compact partition/unary-exception engine, complete source notices below.
* saffah_codex_6a_agg3 https://duck.ac/submission/130057: our guarded unary
* rank-word mechanism, extended here with coordinate-relative corrections.
* Idea: After proving a signed16 rank-minus-coordinate correction per group,
* store it above48 unary marker bits. Marker0 is always one, so a zero low
* bit identifies exact exception records. Decode from v plus the correction
* and selected marker position; no coarse-base lookup remains. Range or
* exception-capacity failures retain complete exact fallback behavior.
* Purpose: Apply the newly validated coordinate-relative representation to
* the100M geometry and delete one table load per compressed output query.
*/
/* ===== 引用区 =====
* [A] 底盘/正文主要来源（逐字节借用的部分）：duck.ac 用户 saffah_cc_v41_agg1 提交 #130124
* <https://duck.ac/submission/130124>（1017 实时 T = 1.377 s，rank 1）。沿用内容：
* ① `count_1d` 的单趟定容散射结构（`part[wp[v>>F_BITS]++] = v & FM`、wp 由 BUCKPOS(b) 起、
* 桶计数由游标反读 `wp[b]-BUCKPOS(b)`、容量守卫 C_BUCKCAP=67584、BSTRIDE=67616 及其
* L1 组相联定步长论证）；
* ② 宽路径 `wide_path`（memset/pref 计数/前缀/查表）与守卫回退思路；
* ③ 输出趟的 [r110a-HOIST]+[r110a-NT] 结构（16 元素暂存 + 2 条 _mm256_stream_si256、
* 32 B 对齐前言、__m_sfence、尾段标量）与预取距离 32；
* ④ B_BITS=11、F_BITS=16、C_BUCKCAP、BSTRIDE 等几何常数。
* [B] 机制来源：duck.ac 用户 saffah_cc_v41_agg1 提交 #130103 <https://duck.ac/submission/130103>
* （1017a rank 1）的「一元位掩码 + PDEP/CTZ 恢复局部秩」思想：u64 低若干位按
* `pos = prefix(k)+k` 置位，`_pdep_u64(1<<r, marks)` 后 `ctz - r` 即得组内秩；本件按
* 本题几何（n=1e8、B=11/F=16）自行重写编码与守卫，并作了下述两处新改。
* [C] 机制来源：duck.ac 用户 saffah_cc_v41_agg1 提交 #130116 <https://duck.ac/submission/130116>
* （1017b rank 1）的「无分支细计数 + 宽和校验」：细直方图自增不再逐元素判回绕，改为对
* 桶内全部 fh 字节做精确宽和，与桶计数 cnt[b] 相等才证明无回绕（回绕必使和恰少 256 的倍数）。
* [D] 许可：以上均为 duck.ac 公开提交（站点 FAQ 明示提交代码将被公开），均未附独立软件许可证
* 声明 ⇒ 按「原作者账号 + 原始提交 URL + 所用内容」具名引用，遵守方式 = 完整保留本署名段。
* 本件未参考任何论文 / 外部开源仓库 / 第三方代码。
* ===== 思路区（本发为新算法试验/正式性能提交） =====
* 【判型】1017: n=1e8，x 均匀随机于 [0,n)。rank-1 件（#130124）的三相耗时中，输出趟
* `out[i] = base32768[x[i]>>15] + pref16[x[i]]` 对一张 **200 MB** 表做 1e8 次随机读。
* 本机对判题机同构实测（立即体验探针，判题机 TSC）：随机查表代价随表尺寸剧烈变化
* （每元素：200MB 28.3 cyc / 100MB 22.8 / 50MB 13.3 / 25MB 6.9）⇒ 把随机表减半是最大杠杆。
* 【本发新改 1：16 值组一元编码，随机表 200 MB -> 50 MB，且**取消 cb 表**】
* rank-1 件把 u16 桶内相对秩按值一格格存（n×2 B = 200 MB）。本发每 16 个连续值只存一个 u64：
* bits[0..45] 一元标记（第 k 个值的标记位 = 组内前缀 + k），bits[46..62] = 本 16 值组起点的
* **桶内相对秩**（17 位，桶计数守卫保证 ≤ C_BUCKCAP=67584 < 2^17），bit63 = 异常标志。
* 输出：`out[i] = sc[v>>16] + (w>>46) + ctz(pdep(1<<(v&15), w&(2^46-1))) - (v&15)`。
* 与 1017a 的同类刀（#130103，另需每 256 值块的 cb 表）相比，本发把块基址塞进同一个 u64，
* 彻底删掉每元素**第二次随机读**（1017a 件实测 cb 表 256KB->78KB 值 -8.6%，说明该表很贵；
* 本题若用 256 值块 cb 将达 1 MB 且被 50 MB 随机流冲刷）。代价是标记位由 55 缩到 46。
* 【本发新改 2：计数局部异常表代替整体回退】标记位缩短后，组内元素数 > 30（约 3.6σ）的组
* 无法编码。若照旧整体回退宽路径，随机数据下必然触发（期望约 900 组）⇒ 本发改为**逐组异常**：
* 该组在 u64 中写 bit63|异常槽号，异常槽存 16 个值的精确全局秩（u32×16）；输出趟对 bit63
* 做一次极稀有分支（约 0.014% 元素）。异常槽容量 65536 组（随机数据期望 ~900，70σ 余量），
* 超容量即整体回退宽路径 ⇒ 任意输入下正确。
* 【本发新改 3：无分支细计数 + 宽和校验】见引用 [C]：删除 1e8 次可预测的 `if(++fh[v]==0)`。
* 【内存/触页】compact 路径只写 part（约 206 MB，仅用到的 1526 个桶）+ U 表（50 MB），较 rank-1
* 件的 part 206 MB + pref16 200 MB 少写 150 MB；官方计时含缺页系统时间（约 0.242µs/页）。
* wide 路径的 pref[n]（400 MB）与 compact 的 part+U 用同一块 400 MB arena 叠加（互斥使用），
* 故 .bss 仅 400 MB。
* 【正确性守卫】① 桶计数 > C_BUCKCAP -> 宽路径；② fh 宽和 != cnt[b]（u8 回绕）-> 宽路径；
* ③ 异常槽溢出 -> 宽路径；④ n > 1e8 或值域越界 -> 宽路径。异常组内秩由 fh 精确前缀直接算出。
* 【目的】本题阈值 = 0.99*T+1µs = 1363.231 ms（T=1377.0 ms）。目标：以随机表 200->50 MB
* 换取输出趟约 -15 cyc/元素（约 -0.4 s），预计 ~0.95-1.0 s，留足余量。
* ================================================ */
#include <cstring>
#include <cstdint>
#include <immintrin.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi2,popcnt")
#define B_BITS 11
#define F_BITS 16
#define KMASK ((1u << B_BITS) - 1u)
#define FMASK ((1u << F_BITS) - 1u)
#define C_BUCKCAP 67584u
#define BSTRIDE 67616u
#define BUCKPOS(b) ((size_t)(b) * BSTRIDE)
#define NMAX 100000000
#define ARENA_BYTES ((size_t)400000064)
#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(64) 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];
static unsigned char fh[1 << F_BITS];
/* [FIFO16] 本发新增：散射写入的 16 项链合并缓冲（2048×16×u16 = 64 KB，L1/L2 驻留）。
每桶满 16 项即以一条 32 B 对齐 store 刷入 PART（wp 步进 16，BSTRIDE*2 与 PART_BYTES 均 32 B 对齐），
尾部残余用 memcpy 精确补齐；磁盘布局/计数语义与直写版逐位相同。 */
static unsigned short fifo[1u << B_BITS][32];
static unsigned char fc[1u << B_BITS];
#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);
auto partition_one = [&](unsigned v) {
unsigned b = v >> F_BITS, k = fc[b];
if (k == 32) {
_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)));
wp[b] += 32; k = 0;
}
fifo[b][k] = (unsigned short)(v & FM);
fc[b] = (unsigned char)(k + 1);
};
int pi = 0;
for (; pi + 32 < n; ++pi) {
__builtin_prefetch(fifo[x[pi + 32] >> F_BITS], 1, 3);
partition_one(x[pi]);
}
for (; pi < n; ++pi) partition_one(x[pi]);
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] & FM; ++fh[v]; }
uint64_t *Ub = UTAB + ((size_t)b << (F_BITS - 4));
unsigned local = 0, sum = 0;
unsigned correction_proof=0;
for (size_t c = 0; c < lim; c += 16) {
const unsigned char *F = fh + c;
/* 组和 <= 30 时，任意标记位 pos = prefix(k)+k <= 30+15 = 45 < 46，故快路径无需逐 k 判守卫。 */
__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) - 15; /* [CORR-15] fold the query's -15 */
if (__builtin_expect(total <= 32u, 1)) {
correction_proof |= unsigned(correction+32768);
__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)) << 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 + 64 < n) __builtin_prefetch(UTAB + (x[i + 64] >> 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 + 64]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 65]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 66]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 67]; __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 + 68]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 69]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 70]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 71]; __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 + 72]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 73]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 74]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 75]; __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 + 76]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 77]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 78]; __builtin_prefetch(UTAB + (lv_ >> 4), 0, 3); }
{ unsigned long long lv_ = x[i + 79]; __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 + 64 < n) __builtin_prefetch(UTAB + (x[i + 64] >> 4), 0, 3);
out[i] = unary_query(x[i]);
}
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 1.127 s | 625 MB + 844 KB | Accepted | Score: 100 | 显示更多 |