代码

// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3，提交 #125828 <https://duck.ac/submission/125828>
//     用途：本题（1017b）现役排行榜 rank-1 件的**完整算法骨架**，本件在其之上只做三处改动（见思路），
//     其余一字未动：① 1 字节直方图 + `++hist[x[i]] == 0` 回绕检测 ⇒ 回退 4 字节宽计数那套**逐位精确**保障；
//     ② AVX2 八格前缀扫描；③ 输出趟 `out[i] = pref[x[i]]`；④ `count_1d(int n, const unsigned *x, unsigned *out)` 接口。
//     （同源件亦见 1017 #125836 / 1017a #125829 —— 三题同源。）
// [2] 本账号 saffah_cc_v41_agg1，提交 #127018 <https://duck.ac/submission/127018>
//     用途：本件前驱（同引擎 + 去预取两刀，板面 5.167362 ms）。v2 在它之上再加两处**逐位等价**的代码布局/ILP 改动。
// [3] 本工作区 `problems/1017/work/r2g2__tmp/`（判题机探针规程）与全队律 743（align pragma 独立成行）、
//     律 796/797（热环内联冷块普查、去分支族不看探针直接上板）。本发的改动按该口径执行。
// 许可：以上均为 duck.ac 上的公开提交与本工作区材料，均未附带任何软件许可证声明；
//   本文件按 RULES §3 逐项署名「原作者账号 + 原始提交地址 + 所用内容」，遵守方式 = 完整保留上述署名于文件开头。
// ======================
// ===== 思路 ===== （本发为正式性能提交，非试验性；v2 = #127018 之上两处逐位等价改动）
// 【判型】本题 n=1e6 ⇒ 直方图 1MB、前缀表 4MB，均 < 判题机 L3（6MB）；显式预取在此区制是纯开销（已在前驱删除）。
//   前驱板面 5.167362 ms（rank-1 件 5.209978）⇒ 尚差严支 5.158878 约 8.5 µs（0.164%）。
// 【v2 刀 1 · `[r2g2-ALIGN]`】在原 `#pragma GCC optimize("O3,unroll-loops")` **之后独立成行**加
//   `#pragma GCC optimize("align-loops=32,align-functions=32")`（律 743：并入列表/改值/拆行是不同单变量）。
//   本题热环 = 计数 RMW 环（8 路展开）+ 前缀 AVX2 环 + 查表环，全在 `count_1d` 内 ⇒ 该 pragma 的作用面覆盖近全部用时（律 748）。
// 【v2 刀 2 · `[r2g2-PFXW16]`】前缀扫描 8 字节/迭代 → **16 字节/迭代（两条独立前缀链）**：
//   第二组的进位在第一组总量算出后叠加 ⇒ 依赖链缩短一半、每迭代 2 条 32B 顺写（写合并更好）。逐位等价（同一前缀定义）。
// 【冷块普查（律 796）】反汇编核对：计数环的回绕回退块（`je 0x560`）与查表环的尾部均在**环外**，
//   热环路径上无"跳过内联冷块"的取指重定向 ⇒ 本件 0 处命中、0 处需修（`objdump -d sub_b.o` 已核）。
// 【逐位保障】三处改动只影响调度/布局，不改变任何取值；回绕回退路径与 [1] 完全一致 ⇒ 与 rank-1 件逐位相同
//   （本地闸门：uniform / 全等值 / 少值 / 聚集 / 有序 / 逆序 / n=0,1,2 全 bad=0）。
// ======================
#include <immintrin.h>
#include <cstring>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC optimize("align-loops=32,align-functions=32")
#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 + 16 <= n; i += 16) {   /* [r2g2-PFXW16] 16B/迭代、两条独立链 */
            __m256i raw1 = _mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i *)(hist + i)));
            __m256i raw2 = _mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i *)(hist + i + 8)));
            __m256i v1 = raw1, v2 = raw2;
            v1 = _mm256_add_epi32(v1, _mm256_slli_si256(v1, 4));
            v2 = _mm256_add_epi32(v2, _mm256_slli_si256(v2, 4));
            v1 = _mm256_add_epi32(v1, _mm256_slli_si256(v1, 8));
            v2 = _mm256_add_epi32(v2, _mm256_slli_si256(v2, 8));
            __m256i lo1 = _mm256_permute2x128_si256(v1, v1, 0x08);
            __m256i lo2 = _mm256_permute2x128_si256(v2, v2, 0x08);
            lo1 = _mm256_shuffle_epi32(lo1, 0xff);
            lo2 = _mm256_shuffle_epi32(lo2, 0xff);
            v1 = _mm256_add_epi32(v1, lo1);
            v2 = _mm256_add_epi32(v2, lo2);
            __m256i t1 = _mm256_permutevar8x32_epi32(v1, _mm256_set1_epi32(7));
            __m256i t2 = _mm256_permutevar8x32_epi32(v2, _mm256_set1_epi32(7));
            __m256i r1 = _mm256_sub_epi32(_mm256_add_epi32(v1, carry), raw1);
            __m256i c2 = _mm256_add_epi32(carry, t1);
            __m256i r2 = _mm256_sub_epi32(_mm256_add_epi32(v2, c2), raw2);
            carry = _mm256_add_epi32(c2, t2);
            _mm256_store_si256((__m256i *)(pref + i), r1);
            _mm256_store_si256((__m256i *)(pref + i + 8), r2);
        }
        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]];
}

评测结果