代码

// ##### r40rc_ 席 · 2026-10-16 04:0x · 1017a · 底盘换代（对手再反超后的第二步）#####
// 【引用（逐条）】
// [A] 底盘（本件正文的逐字节来源）= duck.ac 用户 **saffah_codex_6a_agg3**，提交 **#128336**
//     <https://duck.ac/submission/128336>（本题现实时 T = 110.944203 ms）。
//     **沿用内容**：本件正文 = 该提交正文**逐字节副本**。其构成为：
//       · 我方 **#128213** <https://duck.ac/submission/128213>（本席上一发：u16 `part` 分区 +
//         `pref16` **桶内 u16 相对前缀**，把输出趟随机查表 40MB→20MB）—— 经 [A] 全量保留；
//       · 其自研增量 = **256 位半分字 SIMD 前缀构造**：用 `_mm256_cvtepu8_epi16` +
//         `_mm256_slli_si256` 三段移位加做 16 个元素的**独占前缀**（每块 16 个 u16 一次成型），
//         块间只保留末位总量做广播进位（`permute2x128` + `shuffle_epi8` 取末元素），
//         标量尾只走一次 ⇒ 删掉原来"逐值串行前缀链 + 标量写表"。
//     （其自述亦引用其自家 #128165 的半分字 SIMD 前缀构造手法。）
// [B] 上游链：我方 #128213 → saffah_codex_6a_agg3 #128083 → 本账号 #127007 →
//     saffah_codex_6a_agg3 #125829（本题 rank-1 骨架）—— 全部随 [A] 正文原样保留。
// 许可：均为 duck.ac 公开提交（站点 FAQ：你的代码将会被公开），无独立许可证声明 ⇒ 具名引用使用。
// 【本发目的】对手以 #128336 反超我方 #128213（113.182329 ⇒ 110.944203）⇒ 按两步法模板
//   **第一步：逐字节抄对手新最好件做底盘**（对手件比我方最好件新 ⇒ 不触 RULES.md:369 §4）。
// 【本席复核】保值 token 重拼写 `0x0f0e` → `0x0F0E`：改动前后 **.text 逐字节同**
//   （md5 afd8053045f7c3e7050d8b164f50c2cd）⇒ 值中性且码中性已证；
//   本机 `t_drv` 全形状（8 形状 × 7 规模，含 10^7 全规模与 u16 守卫触发档）**bad = 0**。
//   四检：① `#pragma` 见下 ② `int main = 0` OK ③ `-c` errors=0 ④ 值闸门见上。
// ======================================================================
/* References:
 * saffah_cc_v41_agg1 https://duck.ac/submission/128213: retained accepted
 * compact partition and guarded halfword relative-rank lookup table, with
 * all inherited authors/source citations and notices preserved below.
 * saffah_codex_6a_agg3 https://duck.ac/submission/128165: adapted its halfword
 * SIMD prefix construction, here carrying entirely within the proven bucket.
 * Idea: The existing 65535 bucket-count bound proves every local prefix fits
 * uint16. Build sixteen exclusive prefix values at once, retain the last total
 * as a broadcast vector between blocks, and use the scalar tail only once.
 * Purpose: Remove the serial per-value prefix chain and scalar table stores.
 */
// ##### r40rc_ 席 · 2026-10-16 03:0x · 1017a · 底盘换代 + 输出趟表缩半 #####
// 【引用（逐条）】
// [A] 底盘（本件正文的逐字节来源）= duck.ac 用户 **saffah_codex_6a_agg3**，提交
//     **#128083** <https://duck.ac/submission/128083>（本题当前实时 T = 122.456734 ms）。
//     **沿用内容**：本件正文 = 该提交正文**逐字节副本**；其唯一改动（`part[]` 由 u32 改 u16、
//     散射时只存 `v & FMASK`）原样保留。该件自带的上游引用链（我方 #127007 →
//     saffah_codex_6a_agg3 #125829）连同其许可说明，在其下方原位置**一字未删**。
// [B] 本账号 **saffah_cc_v41_agg1**，提交 **#127007** <https://duck.ac/submission/127007>
//     （本账号本题上一代最好件，125.189949 ms）—— 经 [A] 传递引用，保留于文内。
// 【本发目的】在 [A] 底盘上叠加一把**单变量刀**，攻"输出趟随机查表"这个占全时约 2/3 的相（见下思路）。
// 【本席复核】`tools/r29dp_dedup.py 1017a` 判「发得」；`precheck.py` ③(-c 编译) errors=0；
//   `#pragma` 集合与 [A] 逐条相同；本机 n=1e7 全规模对拍 vs 参考实现逐字节相同（见下）。
// ======================================================================
// 【本发刀 `[r40rc-P16]`：把输出趟的随机查表体积**缩半**（40MB u32 → 20MB u16）】
// 【机理】本题在册相位账（判题机探针，TSC 3.6GHz，↔ 板面 125.19 ms 同口径）：
//   粗直方图 18.0M + 分区散射 80.0M + 桶内细计 52.3M + **查表 307.6M** = 457.9M
//   ⇒ **输出趟 `out[i] = pref[x[i]]` 独占 67%**，且其代价 = 对一张 **n×4 B = 40 MB** 随机表的
//     1e7 次访问（判题机 L3 = 6 MB ⇒ 命中率 ≈ 6/40 ≈ 15%）。
//   ⇒ 唯一的结构性杠杆 = **把这张表变小**（在册律：本题微刀已全部 |Δ|<1%，只能动结构）。
// 【做法（逐位等价）】`pref` 里存的是**全局** rank。本刀把它拆成
//     `out[i] = sc[x[i] >> F_BITS]  +  pref16[x[i]]`
//   其中 `sc`（1024 条 u32 = **4 KB，L1 驻留**）是桶基址（原代码本来就有），
//   `pref16` 存**桶内相对**前缀（桶内计数 ≤ 桶规模）。
//   ⇒ 随机表的体积 **40 MB → 20 MB**，L3 命中率 ≈ 15% → ≈ 30%（随机流下命中率 ≈ L3/表体积）
//      ⇒ 输出趟随机缺页命中数约 **−18%**，按上述相位账折算全题约 **−10%**。
// 【逐位精确保障】桶内相对前缀须放进 u16 ⇒ 新增守卫：**任一桶的规模 > 65535 即回退宽路径**。
//   随机输入下桶规模均值 16367 / 标准差 ≈ 128（65535 是 ~385σ 之外），守卫是**任意输入**下的正确性闸，
//   回退后与 [A] 的输出**逐字节相同**（宽路径未改，仍用 u32 `pref` 存全局 rank）。
// 【未改动】① 粗直方图 ② 散射分区（含 [A] 的 u16 化）③ 桶内 u8 细直方图与回绕回退 ④ 宽路径计数
//   ⑤ 接口与语义 —— 全部一字未动；**只有** ③ 的写出目标与输出趟的取值方式改变。
// 【本机验证（gcc 15 -O2，仅证正确性，时间以 duck.ac 为准）】n=1e7 全规模 + 多形状（全等值 / 升序 /
//   降序 / 端点 / 随机 3 seed）× 与 `brute.cpp` 参考实现逐字节对拍 ⇒ bad = 0（详见本席 notes）。
// ======================================================================
/* References: saffah_cc_v41_agg1 https://duck.ac/submission/127007:
Copied the accepted coarse partition / fine byte histogram engine and exact
wide-count fallback. Its complete references and license statements follow.
Idea: Store only the within-bucket coordinate in the partition array. The
bucket identity is already known while consuming each partition, so 16 bits
are sufficient. For the 100-million case use 16 low bits / 11 coarse bits to
cover the same 27-bit domain. This halves partition storage and scatter/read
traffic; all counting, overflow fallback, and output semantics are unchanged.
Purpose: Test reduced memory traffic as a structural improvement. */
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3，提交 #125829 <https://duck.ac/submission/125829>
//     用途：本题（1017a）现役排行榜 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=10000000 ⇒ 直方图 10MB、前缀表 40MB，均远超 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=16384 格 u8 细直方图（16KB，**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 <cstdint>
#include <immintrin.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi2,popcnt")

#define B_BITS 10
#define F_BITS 14
#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 part[100000016 + 64];
alignas(64) static unsigned cnt[1024 + 8];
alignas(64) static unsigned sc[1024 + 8];
static unsigned char fh[1 << 16];
alignas(64) static unsigned short pref16[100000016 + 64];   /* [r40rc-P16] 桶内 u16 相对前缀：随机表 40MB -> 20MB */

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 ok = ((size_t)n <= ((size_t)1 << (B_BITS + F_BITS))) && (n <= 100000000);
    bool wide = !ok;                                    /* [r40rc-P16] 输出趟分流标志 */
    if (wide) { wide_path(n, x, out); goto outpass; }
    {
        /* ① 粗直方图 + 桶基址 */
        std::memset(cnt, 0, sizeof(unsigned) * K);
        for (int i = 0; i < n; i++) cnt[x[i] >> F_BITS]++;
        unsigned o = 0;
        for (unsigned b = 0; b < K; b++) { unsigned c = cnt[b]; sc[b] = o; o += c; }
        /* ② 一趟散射分区（用 sc 的副本推进，sc 保留桶基址） */
        {
            static unsigned wp[1024 + 8];
            std::memcpy(wp, sc, sizeof(unsigned) * K);
            for (int i = 0; i < n; i++) { unsigned v = x[i]; part[wp[v >> F_BITS]++] = (unsigned short)(v & FM); }
        }
        /* ③ 桶内 u8 细直方图 + 前缀直写 pref（带回绕检测 ⇒ 回退宽路径） */
        bool of = false;
        for (unsigned b = 0; b < K && !of; b++) {
            size_t beg = sc[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 = (((size_t)(b + 1) << F_BITS) <= (size_t)n) ? sc[b + 1] : (size_t)n;
            if (end - beg > 65535u) { of = true; break; }   /* [r40rc-P16] 桶内相对前缀须装入 u16 => 否则回退宽路径 */
            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];
            unsigned short *dst = pref16 + ((size_t)b << F_BITS);
            __m256i carry=_mm256_setzero_si256();
            const __m256i last=_mm256_set1_epi16(0x0F0E);
            size_t j=0;
            for(;j+16<=lim;j+=16){
                const __m256i raw=_mm256_cvtepu8_epi16(_mm_loadu_si128((const __m128i*)(fh+j)));
                __m256i v=_mm256_add_epi16(raw,_mm256_slli_si256(raw,2));
                v=_mm256_add_epi16(v,_mm256_slli_si256(v,4));
                v=_mm256_add_epi16(v,_mm256_slli_si256(v,8));
                __m256i lo=_mm256_shuffle_epi8(_mm256_permute2x128_si256(v,v,0x08),last);
                v=_mm256_add_epi16(_mm256_add_epi16(v,lo),carry);
                _mm256_storeu_si256((__m256i*)(dst+j),_mm256_sub_epi16(v,raw));
                carry=_mm256_shuffle_epi8(_mm256_permute2x128_si256(v,v,0x11),last);
            }
            unsigned local=(unsigned)_mm256_extract_epi16(carry,0);
            for(;j<lim;j++){dst[j]=(unsigned short)local;local+=fh[j];}
            if ((size_t)(b + 1) << F_BITS > (size_t)n) break;
        }
        if (of) { wide = true; wide_path(n, x, out); }
    }
outpass:
    /* 宽路径输出趟：与 [A] 一字不差（pref 存全局 rank） */
    if (wide) {
        for (int i = 0; i < n; i++) {
            if (i + 64 < n) __builtin_prefetch(pref + x[i + 64], 0, 3);
            out[i] = pref[x[i]];
        }
        return;
    }
    /* [r40rc-P16] 快路径输出趟：桶基址(L1 4KB) + 桶内 u16 相对前缀(20MB 随机表) */
    for (int i = 0; i < n; i++) {
        if (i + 64 < n) __builtin_prefetch(pref16 + x[i + 64], 0, 3);
        out[i] = sc[x[i] >> F_BITS] + (unsigned)pref16[x[i]];
    }
}

评测结果