代码

/* References: saffah_codex_6a_agg3 https://duck.ac/submission/128110:
Retained its accepted SIMD fine-prefix version and all inherited references.
Idea: Validate fine-byte histogram overflow by comparing the sum accumulated
by the existing prefix pass with the known coarse bucket population. Each
byte wrap subtracts exactly 256 from this sum and cannot be canceled by other
counts. Equality proves no wrap; otherwise retain the unchanged wide fallback.
This removes the conditional from all fine-count increments without adding
a counting pass. Output is deferred until after successful validation.
Purpose: Delete 100 million overflow checks while preserving exact fallback. */
/* 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 <cstdint>
#include <immintrin.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi2,popcnt")

#define B_BITS 10
#define F_BITS 17
#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 part[100000016 + 64];
alignas(64) static unsigned cnt[1024 + 8];
alignas(64) static unsigned sc[1024 + 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 ok = ((size_t)n <= ((size_t)1 << (B_BITS + F_BITS))) && (n <= 100000000);
    if (!ok) { 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]++] = v; }
        }
        /* ③ 桶内 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;
            std::memset(fh, 0, (size_t)1 << F_BITS);
            for (size_t t = beg; t < end; t++) ++fh[part[t] & FM];
            unsigned s = sc[b];
            unsigned *dst = pref + ((size_t)b << F_BITS);
            size_t j=0;
            __m256i base=_mm256_set1_epi32(s);
            for(;j+16<=lim;j+=16){
                __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);
                __m256i ex=_mm256_sub_epi16(p,counts);
                __m256i a=_mm256_cvtepu16_epi32(_mm256_castsi256_si128(ex));
                __m256i b=_mm256_cvtepu16_epi32(_mm256_extracti128_si256(ex,1));
                _mm256_storeu_si256((__m256i*)(dst+j),_mm256_add_epi32(a,base));
                _mm256_storeu_si256((__m256i*)(dst+j+8),_mm256_add_epi32(b,base));
                unsigned sum=(unsigned)_mm_extract_epi16(_mm256_extracti128_si256(p,1),7);
                base=_mm256_add_epi32(base,_mm256_set1_epi32(sum));
            }
            s=(unsigned)_mm_cvtsi128_si32(_mm256_castsi256_si128(base));
            for (; j < lim; j++) { unsigned c = fh[j]; dst[j] = s; s += c; }
            if (s - sc[b] != cnt[b]) { of = true; break; }
            if ((size_t)(b + 1) << F_BITS > (size_t)n) break;
        }
        if (of) wide_path(n, x, out);
    }
outpass:
    /* 输出趟：引用 [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]];
    }
}

评测结果