代码

/* ===== 引用区 =====
 * [A] 底盘/正文主要来源（逐字节借用的部分）：duck.ac 用户 saffah_cc_v41_agg1 提交 #130124
 *     <https://duck.ac/submission/130124>（1017 实时 T = 1.377 s，rank 1）。沿用内容：
 *     ① `count_1d` 的单趟定容散射结构（`part[wp[v>>F_BITS]++] = v & FM`、wp 由 BUCKPOS(b) 起、
 *        桶计数由游标反读 `wp[b]-BUCKPOS(b)`、容量守卫 C_BUCKCAP=67584、BSTRIDE=67616 及其
 *        L1 组相联定步长论证）；
 *     ② 宽路径 `wide_path`（memset/pref 计数/前缀/查表）与守卫回退思路；
 *     ③ 输出趟的 [r110a-HOIST]+[r110a-NT] 结构（16 元素暂存 + 2 条 _mm256_stream_si256、
 *        32 B 对齐前言、__m_sfence、尾段标量）与预取距离 32；
 *     ④ B_BITS=11、F_BITS=16、C_BUCKCAP、BSTRIDE 等几何常数。
 * [B] 机制来源：duck.ac 用户 saffah_cc_v41_agg1 提交 #130103 <https://duck.ac/submission/130103>
 *     （1017a rank 1）的「一元位掩码 + PDEP/CTZ 恢复局部秩」思想：u64 低若干位按
 *     `pos = prefix(k)+k` 置位，`_pdep_u64(1<<r, marks)` 后 `ctz - r` 即得组内秩；本件按
 *     本题几何（n=1e8、B=11/F=16）自行重写编码与守卫，并作了下述两处新改。
 * [C] 机制来源：duck.ac 用户 saffah_cc_v41_agg1 提交 #130116 <https://duck.ac/submission/130116>
 *     （1017b rank 1）的「无分支细计数 + 宽和校验」：细直方图自增不再逐元素判回绕，改为对
 *     桶内全部 fh 字节做精确宽和，与桶计数 cnt[b] 相等才证明无回绕（回绕必使和恰少 256 的倍数）。
 * [D] 许可：以上均为 duck.ac 公开提交（站点 FAQ 明示提交代码将被公开），均未附独立软件许可证
 *     声明 ⇒ 按「原作者账号 + 原始提交 URL + 所用内容」具名引用，遵守方式 = 完整保留本署名段。
 *     本件未参考任何论文 / 外部开源仓库 / 第三方代码。
 * ===== 思路区（本发为新算法试验/正式性能提交） =====
 * 【判型】1017: n=1e8，x 均匀随机于 [0,n)。rank-1 件（#130124）的三相耗时中，输出趟
 *   `out[i] = base32768[x[i]>>15] + pref16[x[i]]` 对一张 **200 MB** 表做 1e8 次随机读。
 *   本机对判题机同构实测（立即体验探针，判题机 TSC）：随机查表代价随表尺寸剧烈变化
 *   （每元素：200MB 28.3 cyc / 100MB 22.8 / 50MB 13.3 / 25MB 6.9）⇒ 把随机表减半是最大杠杆。
 * 【本发新改 1：16 值组一元编码，随机表 200 MB -> 50 MB，且**取消 cb 表**】
 *   rank-1 件把 u16 桶内相对秩按值一格格存（n×2 B = 200 MB）。本发每 16 个连续值只存一个 u64：
 *     bits[0..45] 一元标记（第 k 个值的标记位 = 组内前缀 + k），bits[46..62] = 本 16 值组起点的
 *     **桶内相对秩**（17 位，桶计数守卫保证 ≤ C_BUCKCAP=67584 < 2^17），bit63 = 异常标志。
 *   输出：`out[i] = sc[v>>16] + (w>>46) + ctz(pdep(1<<(v&15), w&(2^46-1))) - (v&15)`。
 *   与 1017a 的同类刀（#130103，另需每 256 值块的 cb 表）相比，本发把块基址塞进同一个 u64，
 *   彻底删掉每元素**第二次随机读**（1017a 件实测 cb 表 256KB->78KB 值 -8.6%，说明该表很贵；
 *   本题若用 256 值块 cb 将达 1 MB 且被 50 MB 随机流冲刷）。代价是标记位由 55 缩到 46。
 * 【本发新改 2：计数局部异常表代替整体回退】标记位缩短后，组内元素数 > 30（约 3.6σ）的组
 *   无法编码。若照旧整体回退宽路径，随机数据下必然触发（期望约 900 组）⇒ 本发改为**逐组异常**：
 *   该组在 u64 中写 bit63|异常槽号，异常槽存 16 个值的精确全局秩（u32×16）；输出趟对 bit63
 *   做一次极稀有分支（约 0.014% 元素）。异常槽容量 65536 组（随机数据期望 ~900，70σ 余量），
 *   超容量即整体回退宽路径 ⇒ 任意输入下正确。
 * 【本发新改 3：无分支细计数 + 宽和校验】见引用 [C]：删除 1e8 次可预测的 `if(++fh[v]==0)`。
 * 【内存/触页】compact 路径只写 part（约 206 MB，仅用到的 1526 个桶）+ U 表（50 MB），较 rank-1
 *   件的 part 206 MB + pref16 200 MB 少写 150 MB；官方计时含缺页系统时间（约 0.242µs/页）。
 *   wide 路径的 pref[n]（400 MB）与 compact 的 part+U 用同一块 400 MB arena 叠加（互斥使用），
 *   故 .bss 仅 400 MB。
 * 【正确性守卫】① 桶计数 > C_BUCKCAP -> 宽路径；② fh 宽和 != cnt[b]（u8 回绕）-> 宽路径；
 *   ③ 异常槽溢出 -> 宽路径；④ n > 1e8 或值域越界 -> 宽路径。异常组内秩由 fh 精确前缀直接算出。
 * 【目的】本题阈值 = 0.99*T+1µs = 1363.231 ms（T=1377.0 ms）。目标：以随机表 200->50 MB
 *   换取输出趟约 -15 cyc/元素（约 -0.4 s），预计 ~0.95-1.0 s，留足余量。
 * ================================================ */
#include <cstring>
#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
#define KMASK ((1u << B_BITS) - 1u)
#define FMASK ((1u << F_BITS) - 1u)
#define C_BUCKCAP 67584u
#define BSTRIDE 67616u
#define BUCKPOS(b) ((size_t)(b) * BSTRIDE)
#define NMAX 100000000

#define ARENA_BYTES ((size_t)400000064)
#define PART_BYTES ((size_t)(1u << B_BITS) * BSTRIDE * 2)
#define U_N ((size_t)(NMAX / 16) + 16)
#define U_BYTES (U_N * 8)

alignas(64) static unsigned char arena[ARENA_BYTES];
#define PART ((unsigned short *)arena)
#define UTAB ((uint64_t *)(arena + PART_BYTES))
#define PREF ((unsigned *)arena)

alignas(64) static unsigned cnt[(1u << B_BITS) + 8];
alignas(64) static unsigned sc[(1u << B_BITS) + 8];
static unsigned wp[(1u << B_BITS) + 8];
static unsigned char fh[1 << F_BITS];

#define OVF_CAP 65536u
alignas(64) static unsigned ovf[OVF_CAP][16];
static unsigned exc_n;

static inline unsigned unary_query(unsigned v) {
    uint64_t w = UTAB[v >> 4];
    unsigned r = v & 15u;
    if (__builtin_expect((w >> 63) != 0, 0)) return ovf[(unsigned)w][r];
    uint64_t sel = _pdep_u64(1ull << r, w & ((1ull << 46) - 1));
    return sc[v >> F_BITS] + (unsigned)(w >> 46) + (unsigned)__builtin_ctzll(sel) - r;
}

static void wide_path(int n, const unsigned *x, unsigned *out) {
    unsigned *p = PREF;
    std::memset(p, 0, (size_t)n * sizeof(unsigned));
    for (int i = 0; i < n; i++) ++p[x[i]];
    unsigned s = 0;
    for (int i = 0; i < n; i++) { unsigned c = p[i]; p[i] = s; s += c; }
    for (int i = 0; i < n; i++) out[i] = p[x[i]];
}

void count_1d(int n, const unsigned *x, unsigned *out) {
    if (n <= 0) return;
    if (!((size_t)n <= ((size_t)1 << (B_BITS + F_BITS)) && n <= NMAX)) { wide_path(n, x, out); return; }
    const unsigned K = 1u << B_BITS;
    const unsigned FM = FMASK;
    bool okc = true;

    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) { okc = false; break; }
        cnt[b] = c; sc[b] = o; o += c;
    }

    exc_n = 0;
    for (unsigned b = 0; b < K && okc; 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 beg = BUCKPOS(b);
        size_t end = beg + (size_t)cnt[b];
        std::memset(fh, 0, (size_t)1 << F_BITS);
        for (size_t t = beg; t < end; t++) { unsigned v = PART[t] & FM; ++fh[v]; }
        uint64_t *Ub = UTAB + ((size_t)b << (F_BITS - 4));
        unsigned local = 0, sum = 0;
        for (size_t c = 0; c < lim; c += 16) {
            const unsigned char *F = fh + c;
            /* 组和 <= 30 时，任意标记位 pos = prefix(k)+k <= 30+15 = 45 < 46，故快路径无需逐 k 判守卫。 */
            unsigned total = 0;
            for (int k = 0; k < 16; k++) total += F[k];
            if (__builtin_expect(total <= 30u, 1)) {
                unsigned gc = 0;
                uint64_t marks = 0;
                for (int k = 0; k < 16; k++) {
                    marks |= (uint64_t)1 << (gc + (unsigned)k);
                    gc += F[k];
                }
                Ub[c >> 4] = marks | ((uint64_t)local << 46);
                sum += total;
                local += total;
            } else {
                if (exc_n >= OVF_CAP) { okc = false; break; }
                unsigned *dst = ovf[exc_n];
                unsigned p = 0;
                for (int j = 0; j < 16; j++) { dst[j] = sc[b] + local + p; p += F[j]; }
                Ub[c >> 4] = 0x8000000000000000ull | (uint64_t)exc_n;
                exc_n++;
                sum += p;
                local += p;
            }
        }
        if (!okc) break;
        if (sum != cnt[b]) { okc = false; break; }
        if (((size_t)(b + 1) << F_BITS) > (size_t)n) break;
    }
    if (!okc) { wide_path(n, x, out); return; }

    int i = 0;
    for (; i < n && ((uintptr_t)(out + i) & 31u); ++i) {
        if (i + 32 < n) __builtin_prefetch(UTAB + (x[i + 32] >> 4), 0, 3);
        out[i] = unary_query(x[i]);
    }
    alignas(64) unsigned buf[16];
    for (; i + 16 + 32 < n; i += 16) {
        for (int j = 0; j < 16; j++) {
            __builtin_prefetch(UTAB + (x[i + j + 32] >> 4), 0, 3);
            buf[j] = unary_query(x[i + j]);
        }
        _mm256_stream_si256((__m256i *)(out + i), _mm256_load_si256((const __m256i *)buf));
        _mm256_stream_si256((__m256i *)(out + i + 8), _mm256_load_si256((const __m256i *)(buf + 8)));
    }
    _mm_sfence();
    for (; i < n; ++i) {
        if (i + 32 < n) __builtin_prefetch(UTAB + (x[i + 32] >> 4), 0, 3);
        out[i] = unary_query(x[i]);
    }
}

评测结果