代码

/* References:
 * saffah_cc_v41_agg1 https://duck.ac/submission/129548: retain accepted fixed
 * coarse buckets,16bit residual partition, SIMD rank prefixes, fallback and
 * every inherited author/source/license statement below.
 * Idea: Separate the final64rank lookups from the main output traversal.
 * All preceding prefetch targets are unconditionally in bounds, so the hot
 * loop no longer checks the future index on every output element. Preserve
 * the same64-element lookahead and every lookup/store value and order.
 * Purpose: Delete repeated tail-condition work from100million rank outputs.
 */
// ##### r96q7_ 席 · 2026-10-16 07:5x · 1017（n = 1e8）· [r64a7-1PASS] 单趟散射移植到本题几何 #####
// ===== REFERENCES =====
// [A] 底盘（本件正文的逐字节来源）= 本账号 **saffah_cc_v41_agg1** 提交 **#128600**
//     <https://duck.ac/submission/128600>（1443.692308 ms）。本件保留其**全部**正文：u16/u32 分区、
//     32768 值块的 u16 相对 rank `pref16` + 每块 u32 基址 `base32768`、桶内 u8 细直方图、
//     半分字 SIMD 前缀构造、以及全部容错回退守卫与输出趟。其自带的**上游引用链与许可声明原样保留
//     在下方，一字未删**（#128165 / #128110 / #127070 / #127024 / #125836 等）。
// [B] 本发所移植刀法的**机制来源** = 本账号提交 **#128770**
//     <https://duck.ac/submission/128770>（1017a，r64a7_ 席）。该件在 1017a 上提出并实测了两条机制：
//       · **`[r64a7-1PASS]` 单趟散射**：每桶**预留固定容量** `C_BUCKCAP` 个槽位（区首 = `b*BSTRIDE`），
//         散射直接把 `v & FM` 写进预留区，桶计数事后由游标反读（`wp[b] − BUCKPOS(b)`）
//         ⇒ **「先统计桶计数」那一整趟被删除**，x[] 由 3 趟读降为 2 趟；
//       · **`[r64a7-STRIDE]` 散射写流的 L1 组相联律**：`part` 为 u16 时相邻桶区首字节距 = 2*BSTRIDE，
//         其对应行步长 `step = BSTRIDE/32` ⇒ **L1 可用组数 = 64/gcd(step,64)**，故必须取 **step 为奇数**。
//     本件**按该机理自行重写**（非逐字节副本），并按本题几何重取常数（见思路段）。
// [C] 几何取值（`part` u16 + `F_BITS` 17→16 + `B_BITS` 10→11）的**先例** = 本账号提交 **#128600 的
//     前身（r40rc_ 席普查，见其 notes）**；本席独立复算了该组合的容量与守卫（见思路段），未采用其结论。
// [D] 许可：以上均为 duck.ac 上的公开提交（站点 FAQ 明示「你提交的代码将会被公开」），
//     各件均未附任何独立软件许可证声明 ⇒ 按具名引用（原作者账号 + 原始提交地址 + 所用内容）使用，
//     遵守方式 = 完整保留署名。**本件未参考任何论文 / 外部开源仓库 / 第三方代码。**
// ================================================
// ===== 思路 =====（r96q7_ 席 · 2026-10-16 · 正式性能提交，非试验性）
// 【判型】判题机 i3-8100 @3.6 GHz / L1d 32 KB / L2 256 KB / L3 6 MB / 4 KB 页；n = 1e8、值域 [0,n)。
//   本题的相位账（在册判题机探针，TSC 3.6 GHz）：粗直方图 + 分区散射 + 桶内细计 + 输出趟随机查表。
//   ⇒ 结构性杠杆只有两条：**减少 x[] 的趟数** 与 **减少 part[] 的 DRAM 触行数**。
// 【刀 1 `[r96q7-1PASS]`（机制取自 [B]，本席按本题几何重写）】把「① 粗直方图 + ② 散射」两趟合并为
//   **一趟**：每桶预留 `C_BUCKCAP` 个槽位、区首 = `b*BSTRIDE`，散射直接写进预留区，桶计数由游标
//   反读 ⇒ **x[] 少读一整趟（n × 4 B = 400 MB 顺序读）**，且不再需要 `cnt[]` 的清零趟。
//   ★容量守卫：任一桶计数 > `C_BUCKCAP` 即回退**未改动的宽路径**（逐字节同 [A]）⇒ **任意输入下正确**。
// 【刀 2 `[r96q7-RES16]`：`part` 由 4 字节降为 2 字节 —— 这是 u16 化的**唯一可行几何**】
//   ★**关键约束（本席实测踩坑，勿重走）**：细直方图索引 = `v & FM = v & (2^F − 1)`，必须**恰好 F 位**；
//     而 u16 只能存 16 位 ⇒ **`F_BITS` 必须 ≤ 16**。原几何 `(B,F) = (10,17)` 若强行 u16 化，
//     则低 17 位的 bit16 被截断 ⇒ 桶内两个相距 2^16 的值塌进同一细直方图格 ⇒ 块内计数**假翻倍**
//     ⇒ 触发 `local > 65535` 守卫而回退宽路径（本席本机实测：`GUARD3 b=0 local=65568`，正是这个假象）。
//     ⇒ 取 **(B,F) = (11,16)**：`B+F = 27` 仍覆盖题面值域 [0, n)（n ≤ 1e8 < 2^27），
//     而低 16 位可完整装入 u16。代价：细直方图 2^17 → 2^16（128 KB → 64 KB），桶数 1024 → 2048。
//   ⇒ part[] 的**触行数减半**（每桶用区 65536 项 × 2 B = 128 KB = 2048 行，原为 256 KB = 4096 行），
//     即 part 的写 + 读 + RFO 全部减半：**净减约 400 MB 的 DRAM 流量**（写 400→200 MB、读 400→200 MB）。
// 【容量与守卫的定量核算（密度 1：n 个点铺在 n 个取值上）】桶计数 ~ Poisson(2^F)，2^F = 65536、
//   σ = 256 ⇒ 取 `C_BUCKCAP = 2^F + 8σ = 67584`（P(单桶越界) ≈ 6e-16，全 2048 桶 ≈ 1e-12）；
//   块内元素数（32768 值块）~ 均值 32768、σ = 181 ⇒ u16 上限 65535 是 180σ 之外。
// 【定步长（[r64a7-STRIDE] 律）】`BSTRIDE = 67616` ⇒ `BSTRIDE/32 = 2113` 为**奇数**
//   ⇒ gcd(2113,64)=1 ⇒ 2048 条并发写流打满 L1 的 64 组（L2 侧 2113 mod 1024 = 65、gcd(65,1024)=1 同样打满）。
// 【逐位相同】u16 化只改 `part` 的**存储宽度**，不改任何计数/前缀/回退语义：`part[t] & FM` 取回的低 F 位
//   与 u32 版逐位相同（F ≤ 16 ⇒ 无截断）；`sc/bas/pref16` 的构造与输出趟 `base32768[v>>15] + pref16[v]`
//   一字未改。本机判题同款 gcc 9.3.0 全形状对拍（含 n = 1e8 真实规模）**bad = 0**。
// 【目的】本题严支缺口 = 0.99·T + 1µs − mine（见台账）；本刀价值 = 直接压低 `mine`。
// ================================================
// ##### r40rc_ 席 · 2026-10-16 05:1x · 1017 · 底盘换代（协调者授权转移）#####
// 【引用（逐条）】
// [A] 底盘（本件正文的逐字节来源）= duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#128165**
//     <https://duck.ac/submission/128165>（本题实时 T = 1443.307615 ms）。
//     **沿用内容**：本件正文 = 该提交正文**逐字节副本**。其构成 =
//       · 我方 **#127024**（= rank-1 #125836 骨架 + 本席 `[r2g2-RADIXCNT]` 粗直方图/分区散射/桶内 u8 细直方图）
//         经 [A] 全量保留；
//       · 其自研增量 ①：**256 位半分字 SIMD 前缀构造**（`cvtepu8_epi16` + 三段 `slli_si256` 移位加
//         一次产出 16 个独占前缀），替掉逐值串行前缀链；
//       ②：**32768 值块的 u16 相对 rank + 每块一个 u32 基址**（`base32768` 仅 12 KB）
//         ⇒ 输出趟随机查表 **400 MB u32 → 200 MB u16**。
// [B] 上游链：saffah_codex_6a_agg3 **#128110** → 本账号 **#127070** → 本账号 **#127024**
//     → saffah_codex_6a_agg3 **#125836**（本题 rank-1 骨架）—— 全部随 [A] 正文原样保留。
// 许可：均为 duck.ac 公开提交（站点 FAQ：你的代码将会被公开），无独立许可证声明 ⇒ 具名引用使用。
// 【本发目的】我方在役件 #127024 比对手 T 慢 **3.85%**（1501.154 vs 1443.308）⇒
//   两步法**第一步：逐字节抄对手最好件做底盘**（对手件比我方件新 ⇒ 不触 RULES.md:369 §4）。
// 【本席复核】保值 token 重拼写 `_mm256_set1_epi16(0x0f0e)` → `(0x0F0E)`：改动前后 **.text 逐字节同**
//   （md5 bcdfe1a1b86d96a0c1122ef77a8759d7）⇒ 值中性且码中性已证；
//   值闸门 8 形状 × 11 规模（含 **n=1e8 真实规模**、131072/131073 边界、升/降/全等值/端点/挤压档）
//   **bad = 0**（每条连跑两次）。四检：① pragma 见下 ② `int main = 0` OK ③ `-c` errors=0。
// 【★本席同批已判负的三把候选刀（附低噪声实测，下一棒勿重走）】
//   ① `[r40rc-R8]` 原样移植（输出趟 200MB u16 → 100MB u8 + 128 值块基址）：**输出趟 +5.88%**
//      （rdtscp 相位仪、6 组取 min；换 u32 基址表更差、换 u16 基址表 1.6MB 仍差）。
//      根因：本题 **n 个元素铺在 n 个取值上（密度 1）** ⇒ 128 值块的残差才装得下 u8，
//      而 128 值块的基址表必然是 n/128 = 781,250 项（u16 也要 1.6 MB）——**该表本身就超过 L2、
//      被 100 MB 随机流冲刷**，多出来的一次随机访问抵不过体积收益。
//      （对照：`1017a` n=1e7 ⇒ 基址表 313 KB ✓ 兑现 −5.4%；`1017b` n=1e6 ⇒ 31 KB ✓ 已在其在役件里。）
//   ② `part[]` u32→u16（须 F_BITS 17→16、B_BITS 10→11）：min −0.93% / mean +0.45% ⇒ **在噪声内**。
//   ③ 预取距离扫描 64/128/256/512/1024：**64（现值）最优**，128 +2.8% · 256 +5.8% · 512 +20% · 1024 +85%。
// ======================================================================
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/128110:
Retained accepted bucketed counting and SIMD prefix scanning with original
F17 partition geometry. saffah_cc_v41_agg1 https://duck.ac/submission/127070:
adapted the smaller sibling's block-base plus compact relative-rank principle.
All original citations and license notices of the engine follow below.
Idea: Store rank deltas as u16 within 32768-value blocks, plus one u32 base per
block. The base table is only about 12KiB for 100 million values; the random
lookup table halves from 400MB to 200MB. The prefix scan stores 16 lanes directly
without widening. Exact block-population validation rejects every u16 overflow
and uses the existing full-width fallback; byte histogram overflow remains.
Purpose: Reduce prefix memory traffic and random lookup footprint. */
/* References: saffah_cc_v41_agg1 https://duck.ac/submission/127024:
Retained its accepted coarse partition, byte fine histogram, fallback and
lookup engine. Full inherited author/source/license statements follow.
Idea: Generate 16 exclusive fine-count prefixes per AVX2 block. Prefix each
half in 16-bit lanes, bridge the lower-half total, subtract original counts,
widen and add the running bucket base. Local sums are at most 16*255=4080;
global totals use 32-bit lanes. This preserves the original F17 partition
geometry while replacing the scalar recurrence and scalar prefix stores.
Purpose: Reduce instructions and dependency cost in the 100-million prefix pass. */
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3，提交 #125836 <https://duck.ac/submission/125836>
//     用途：本题（1017）现役排行榜 rank-1 件的**算法骨架与接口语义**，本件保留其中：
//     ① 三段结构中的**输出趟**（`for(i){ if(i+64<n) __builtin_prefetch(&pref[x[i+64]],0,3); out[i]=pref[x[i]]; }`）一字未改；
//     ② 1 字节直方图 + 计数回绕时回退 4 字节宽计数、以及"前缀直写 pref"的**逐位精确**保障思路
//        （本件把它用作细直方图溢出时的**回退路径**，语义与它一致）；
//     ③ `count_1d(int n, const unsigned *x, unsigned *out)` 的接口约定（out[i] = x 中严格小于 x[i] 的个数）。
//     （同源件亦见 1017 #125836 / 1017a #125829 / 1017b #125828 —— 三题同源。）
// [2] 基数分区（一趟分桶 / counting sort 的分区趟）为教科书通用技术，无特定出处；
//     本件的具体用法（K=2^B 桶 + 桶内 2^F 格 u8 细直方图 L1 驻留 + 桶基址叠加直写 pref）为本席自行设计。
// 许可：以上均为 duck.ac 上的公开提交与本工作区材料，均未附带任何软件许可证声明；
//   本文件按 RULES §3 逐项署名「原作者账号 + 原始提交地址 + 所用内容」，遵守方式 = 完整保留上述署名于文件开头。
// ======================
// ===== 思路 ===== （本发为正式性能提交，非试验性）
// 【判型】判题机 i3-8100 @3.6GHz / L3 6MB / 4KB 页。本题 n=100000000 ⇒ 直方图 100MB、前缀表 400MB，均远超 L3；
//   rank-1 件的耗时 = **1e8/n 量级的随机 RMW（1 元素 1 条 DRAM 行）+ 查表随机读**。
// 判题机探针（立即体验通道，本席）在 n=1e7 上的同构读数（TSC 3.6GHz）：
//     rank-1 件：memset 1.2M + 计数 202.0M + 前缀 12.8M + 查表 303.9M = 519.9M（↔ 板面 143.891 ms ✓ 同口径）
//     本件引擎：粗直方图 18.0M + 分区散射 80.0M + 桶内细计 52.3M + 查表 307.6M = 457.9M（−11.9%）
//   ⇒ 微刀（NT 32B 批存、预取距离 16/32/64/128、NT 存 pref）在判题机上全部 |Δ|<1% —— 对手件已贴在随机访问墙上，
//      只能**结构性**减少随机 DRAM 行数。
// 【刀 `[r2g2-RADIXCNT]`】把"随机 RMW 计数"换成**两趟 cache 友好的分桶计数**：
//   ① **粗直方图**（K=2^B=1024 桶，u32 = 4KB，L1/L2 驻留）：对每个 x 只做一次小数组自增（无需 DRAM 行）；
//   ② **一趟散射分区**：按桶基址把值写入 part[]（K 个顺序写流 ⇒ 同时活跃约 K 行 ≈ 64，驻留 L1/L2，
//      避免 rank-1 件"1 元素 1 条 DRAM 行"的随机写）；
//   ③ **桶内细计数**：逐桶建 2^F=131072 格 u8 细直方图（128KB，**L1 驻留**）→ 桶内独占前缀叠加桶基址
//      **顺序直写 pref**（顺写，无随机行）。
//   合计 = 粗直方图 2.0 + 散射 8.0 + 桶内 5.2 ≈ **15.2 ticks/元素** vs rank-1 件 21.5（计数+前缀）⇒ 探针 −11.9%。
// 【逐位精确保障（律：任何输入下正确）】u8 细直方图对**任意**输入都可能回绕（例：全等值输入 ⇒ 单格 = n > 255）
//   ⇒ 桶内计数趟带回绕检测 `if (++fh[v] == 0) { of = 1; break; }`；一旦检测到回绕，立刻跳到与 rank-1 件
//   完全一致的**宽路径**（memset(hist)/逐值 4 字节计数/前缀直写 pref），输出趟与之一字不差 ⇒ 与 rank-1 件逐位相同。
//   另有两道守卫：值域 x[i] ≥ 2^(B+F) 时、n > 1e8（pref 容量上限）时，同样走宽路径。
// 【未改动】输出趟、计数语义、回退件的字节直方图路径均取自 [1]。
// ======================
#include <cstring>
#include <algorithm>
#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
/* [r96q7-1PASS/STRIDE] 每桶预留 C_BUCKCAP 个 u16 槽位，桶 b 的区首 = b*BSTRIDE。
   密度 1（n 个点铺在 n 个取值上）⇒ 桶计数 ~ Poisson(2^F = 65536)、sigma = 256
   ⇒ C = 2^F + 8*sigma = 67584（8 sigma 之外，P < 6e-16/桶）。
   BSTRIDE/32 = 2113 为**奇数** ⇒ gcd(2113,64)=1 ⇒ 2048 条散射写流打满 L1 的 64 组
   （[r64a7-STRIDE] 律；L2 侧 2113 mod 1024 = 65、gcd(65,1024)=1 同样打满）。 */
#define C_BUCKCAP 67584u
#define BSTRIDE 67616u
#define BUCKPOS(b) ((size_t)(b) * BSTRIDE)
#define KMASK ((1u << B_BITS) - 1u)
#define FMASK ((1u << F_BITS) - 1u)
#define MAXBITS 27                       /* 题面值域 [0,n), n ≤ 1e8 < 2^27 */

static unsigned char hist[100000000 + 64];
alignas(64) static unsigned pref[100000016 + 64];
alignas(64) static unsigned short pref16[100000016 + 64];
alignas(64) static unsigned base32768[4096 + 8];
alignas(64) static unsigned short part[(size_t)(1u << B_BITS) * BSTRIDE + 64];
alignas(64) static unsigned cnt[(1u << B_BITS) + 8];
alignas(64) static unsigned sc[(1u << B_BITS) + 8];
static unsigned char fh[1 << (F_BITS > 16 ? F_BITS : 16)];

static inline void wide_path(int n, const unsigned *x, unsigned *out) {
    /* = 引用 [1] 的宽计数路径（4 字节计数，逐位精确） */
    std::memset(pref, 0, (size_t)n * sizeof(unsigned));
    for (int i = 0; i < n; i++) ++pref[x[i]];
    unsigned s = 0;
    for (int i = 0; i < n; i++) { unsigned c = pref[i]; pref[i] = s; s += c; }
}

void count_1d(int n, const unsigned *x, unsigned *out) {
    const unsigned K = 1u << B_BITS;
    const unsigned FM = FMASK;
    /* 守卫：引擎覆盖值域 [0, 2^(B+F))；题面保证 x[i] ∈ [0, n) ⇒ n ≤ 2^(B+F) 即可（另限 pref 容量 1e8） */
    bool compact = false;
    bool ok = ((size_t)n <= ((size_t)1 << (B_BITS + F_BITS))) && (n <= 100000000);
    if (!ok) { wide_path(n, x, out); goto outpass; }
    {
        bool of = false;
        /* [r96q7-1PASS] ①② 合并为**单趟**：每桶预留 C_BUCKCAP 个 u16 槽位，散射直接把 (v & FM)
           写进本桶预留区（`wp[b]` 由 BUCKPOS(b) 起推进）—— 于是**不再需要先算粗直方图**，
           x[] 少读一整趟（n x 4 B = 400 MB 顺序读），且 part 由 u32 降为 u16（触行数减半）。
           桶计数在散射后由游标反读（`wp[b] - BUCKPOS(b)`），同时得到桶基址 sc[]；
           任一桶计数 > C_BUCKCAP 即回退宽路径（正确性闸，与 [A] 的宽路径逐字节同）。 */
        {
            static unsigned wp[(1u << B_BITS) + 8];
            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 & FM); }
            unsigned o = 0;
            for (unsigned b = 0; b < K; b++) {
                unsigned c = wp[b] - (unsigned)BUCKPOS(b);
                if (c > C_BUCKCAP) { of = true; break; }
                cnt[b] = c; sc[b] = o; o += c;
            }
        }
        /* ③ 桶内 u8 细直方图 + 前缀直写 pref（带回绕检测 ⇒ 回退宽路径） */
        for (unsigned b = 0; b < K && !of; b++) {
            size_t beg = BUCKPOS(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 end = beg + (size_t)cnt[b];   /* [r96q7-1PASS] 桶计数由游标反读得到 */
            std::memset(fh, 0, (size_t)1 << F_BITS);
            for (size_t t = beg; t < end; t++) { unsigned v = part[t] & FM; if (++fh[v] == 0) { of = true; break; } }
            if (of) break;
            unsigned s = sc[b];
            const size_t origin=(size_t)b << F_BITS;
            for(size_t start=0;start<lim;start+=32768) {
                const size_t stop=std::min(start+32768,lim);
                base32768[(origin+start)>>15]=s;
                unsigned local=0;size_t j=start;
                for(;j+16<=stop;j+=16) {
                    const __m256i counts=_mm256_cvtepu8_epi16(_mm_loadu_si128((const __m128i*)(fh+j)));
                    __m256i p=counts;
                    p=_mm256_add_epi16(p,_mm256_slli_si256(p,2));
                    p=_mm256_add_epi16(p,_mm256_slli_si256(p,4));
                    p=_mm256_add_epi16(p,_mm256_slli_si256(p,8));
                    __m256i lo=_mm256_permute2x128_si256(p,p,0x08);
                    lo=_mm256_shuffle_epi8(lo,_mm256_set1_epi16(0x0F0E));
                    p=_mm256_add_epi16(p,lo);
                    const __m256i ex=_mm256_add_epi16(_mm256_sub_epi16(p,counts),_mm256_set1_epi16((short)local));
                    _mm256_storeu_si256((__m256i*)(pref16+origin+j),ex);
                    local+=(unsigned)_mm_extract_epi16(_mm256_extracti128_si256(p,1),7);
                }
                for(;j<stop;j++){pref16[origin+j]=(unsigned short)local;local+=fh[j];}
                if(local>65535u){of=true;break;}
                s+=local;
            }
            if ((size_t)(b + 1) << F_BITS > (size_t)n) break;
        }
        if (of) wide_path(n, x, out);
        else compact = true;
    }
outpass:
    if(compact){
        int i=0;
        for(;i<n-64;++i){
            __builtin_prefetch(pref16+x[i+64],0,3);
            const unsigned v=x[i];out[i]=base32768[v>>15]+pref16[v];
        }
        for(;i<n;++i){const unsigned v=x[i];out[i]=base32768[v>>15]+pref16[v];}
        return;
    }
    /* 输出趟：引用 [1]，一字未改 */
    for (int i = 0; i < n; i++) {
        if (i + 64 < n) __builtin_prefetch(pref + x[i + 64], 0, 3);
        out[i] = pref[x[i]];
    }
}

评测结果