代码

// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3，提交 #125828 <https://duck.ac/submission/125828>
//     用途：本题（1017b）现役排行榜 rank-1 件的**完整算法骨架**，本件在其之上只做两处删除（见思路），
//     其余一字未动：① 1 字节直方图 + `++hist[x[i]] == 0` 回绕检测 ⇒ 回退 4 字节宽计数那套**逐位精确**保障；
//     ② AVX2 八格前缀扫描（`_mm256_cvtepu8_epi32` + 两级 `slli_si256` 与 128 位半区携带）；
//     ③ 输出趟 `out[i] = pref[x[i]]`；④ `count_1d(int n, const unsigned *x, unsigned *out)` 接口约定。
//     （同源件亦见 1017 #125836 / 1017a #125829 —— 三题同源。）
// [2] 本工作区 `problems/1010/work/r2g_*`、`problems/1017/work/r2g2__tmp/` 的判题机探针规程
//     （tools/probe.py 立即体验通道 + 同进程多臂批内对照），本发的两处删除按该规程定价。
// 许可：以上均为 duck.ac 上的公开提交与本工作区材料，均未附带任何软件许可证声明；
//   本文件按 RULES §3 逐项署名「原作者账号 + 原始提交地址 + 所用内容」，遵守方式 = 完整保留上述署名于文件开头。
// ======================
// ===== 思路 ===== （本发为正式性能提交，非试验性）
// 【判型】本题 n=1e6 ⇒ 直方图 1MB、前缀表 4MB —— **两者都小于判题机 L3（6MB）**，与 n=1e8 的"随机访问墙"
//   区制完全不同：随机访问落在 L2/L3，**显式预取（PREFETCHT0）此时是纯开销**（占 issue/LFB 槽而不省延迟）。
//   判题机探针（立即体验通道，同进程多臂、单臂 1 次调用、n=1e6）实测（ticks，TSC 3.6GHz，批内 base=19.414M）：
//     base（rank-1 件原样）        19.414M
//     去计数趟预取（[r2g2-CNTNOPF]） 18.328M  (−5.6%)
//     去输出趟预取（[r2g2-OUTNOPF]）＋上式  **17.352M（−10.6%）** ← 本发所取
//     （对照：NT 批存 out 18.568M / 保留预取 18.586M ⇒ 本区制下**删除**优于换法；两臂均逐位同 base）
// 【两把刀（都是删除，语义不可能变）】
//   [r2g2-CNTNOPF]：删去计数趟里 `if (i+64<n) __builtin_prefetch(hist+x[i+64],1,3);`
//     —— 直方图 1MB 已在 L2/L3，软件预取只是把同一行提前拉进 L1，反而占 L1 miss 队列。
//     （回绕检测 `if (++hist[x[i]] == 0) {wide=true;break;}` **原样保留** ⇒ 精度保障不变。）
//   [r2g2-OUTNOPF]：删去输出趟里 `if (i+64<n) __builtin_prefetch(pref+x[i+64],0,3);`
//     —— 前缀表 4MB 的随机查表同样落在 L3，乱序引擎 + 硬件预取已足够覆盖。
// 【逐位精确保障】与 [1] 完全一致：字节直方图任一回绕即转 4 字节宽路径（本件未改动该路径），
//   两处删除只影响访存调度、不改变任何取值 ⇒ 输出与 rank-1 件逐位相同（探针各臂 FNV 相同已验）。
// ======================
#include <immintrin.h>
#include <cstring>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi2,popcnt")
static unsigned char hist[100000000];
alignas(64) static unsigned pref[100000016];
void count_1d(int n, const unsigned *x, unsigned *out) {
    std::memset(hist, 0, (size_t)n);
    bool wide = false;
    for (int i = 0; i < n; i++) {
        /* [r2g2-CNTNOPF] 原 `__builtin_prefetch(hist+x[i+64],1,3)` 已删（n≤1e6 ⇒ 直方图驻留 L2/L3） */
        if (++hist[x[i]] == 0) { wide = true; break; }
    }
    if (wide) {
        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; }
    } else {
        __m256i carry = _mm256_setzero_si256(); int i = 0;
        for (; i + 8 <= n; i += 8) {
            __m256i raw = _mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i *)(hist + i)));
            __m256i v = raw;
            v = _mm256_add_epi32(v, _mm256_slli_si256(v, 4));
            v = _mm256_add_epi32(v, _mm256_slli_si256(v, 8));
            __m256i low = _mm256_permute2x128_si256(v, v, 0x08);
            low = _mm256_shuffle_epi32(low, 0xff);
            v = _mm256_add_epi32(v, low);
            __m256i total = _mm256_permutevar8x32_epi32(v, _mm256_set1_epi32(7));
            __m256i result = _mm256_sub_epi32(_mm256_add_epi32(v, carry), raw);
            _mm256_store_si256((__m256i *)(pref + i), result);
            carry = _mm256_add_epi32(carry, total);
        }
        unsigned s = (unsigned)_mm256_extract_epi32(carry, 0);
        for (; i < n; i++) { pref[i] = s; s += hist[i]; }
    }
    /* [r2g2-OUTNOPF] 原 `__builtin_prefetch(pref+x[i+64],0,3)` 已删（n≤1e6 ⇒ 前缀表驻留 L3） */
    for (int i = 0; i < n; i++) out[i] = pref[x[i]];
}

评测结果