代码

/* ===== 引用区 =====
 * [A] 结构与宽路径来源：duck.ac 用户 saffah_cc_v41_agg1 提交 #130124 <https://duck.ac/submission/130124>
 *     （1017 rank 1）与提交 #130103 <https://duck.ac/submission/130103>（1017a rank 1）。沿用内容：
 *     单趟定容散射 `part[wp[v>>F_BITS]++] = v & FM`（桶计数由游标反读、容量守卫、BSTRIDE 定步长律）、
 *     宽路径计数/前缀/查表、输出趟 [r110a-HOIST]+[r110a-NT]（16 元素暂存 + 2×_mm256_stream_si256、
 *     32B 对齐前言、__m_sfence、尾段标量）、以及 1017a 的几何 B=10/F=14、C_BUCKCAP=17408、BSTRIDE=17440。
 * [B] 机制来源：saffah_cc_v41_agg1 #130103 的「一元位掩码 + PDEP/CTZ 组内局部秩」思想；本件按本题
 *     几何重写编码，并作新改：把基址塞进同一 u64、取消 cb 表、加逐组异常表（见思路）。
 * [C] 机制来源：saffah_cc_v41_agg1 #130116 的「无分支细计数 + 宽和校验」防 u8 回绕思想。
 * [D] 许可：以上均为 duck.ac 公开提交（FAQ 明示代码公开），无独立许可证声明 ⇒ 按「原作者账号 +
 *     原始提交 URL + 所用内容」具名引用，遵守方式 = 完整保留本署名段。未参考任何论文/外部仓库。
 * ===== 思路区（正式性能提交） =====
 * 【本发新改 1】16 值组一元编码：u64 = bits[0..45] 标记（第 k 值标记位=组内前缀+k）+
 *   bits[46..62] 桶内相对基址（17 位，桶计数守卫 ≤ C_BUCKCAP 保证）+ bit63 异常标志。
 *   输出 out[i] = sc[v>>F_BITS] + (w>>46) + ctz(pdep(1<<(v&15), w&(2^46-1))) - (v&15)。
 *   相比 #130103 每元素另需一次 cb 表随机读（其探针实测 cb 面积 256KB->1.2KB 值 -12.5%），
 *   本发彻底删除 cb 表，只保留 L1 常驻的 sc。随机表尺寸：U 表 n/16×8B = 5 MB（#130103 同为 5 MB，但本发无 cb）。
 * 【本发新改 2】逐组异常：组内元素数 > 30（约 3.6σ）的组无法用 46 位标记编码，改为 u64 写
 *   bit63|异常槽号，槽存 16 个 u32 精确全局秩；输出对 bit63 做极稀有分支（约 0.014% 元素）。
 *   异常槽容量 65536 组，超容量整体回退宽路径 ⇒ 任意输入正确。
 * 【本发新改 3】无分支细计数 + 宽和校验（引用 [C]）。
 * 【内存/触页】compact 只写 part（按实际桶数）+ U 表；wide 的 pref[n] 与 part+U 共用 arena 叠加，
 *   BSS = 40717312；官方计时含缺页（约 0.242µs/页）。
 * 【目的】1017a 阈值 = 0.99*T+1µs = 62.619 ms（T=63.251 ms）（T=63.251 ms）。预期以「删 cb + 随机表/触页缩减」跨过阈值。
 * ================================================ */
#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 C_BUCKCAP 17408u
#define BSTRIDE 17440u
#define BUCKPOS(b) ((size_t)(b) * BSTRIDE)
#define NMAX 10000000

#define ARENA_BYTES ((size_t)40717312)
#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]);
    }
}

评测结果