代码

/* 1008 二维数点, n <= 1e7.
 * Pipeline: LSD radix sort by key=(x<<32)|(~y)  (x asc, y desc)  +  bottom-up
 * branchless merge counting where the accumulated counts travel in array order
 * (no random out[id] RMW in the hot loop)  +  one final scatter to out[id].
 * Local phase profile, n=1e7 (i5-6500): sort(4x16bit) 767ms, build 154ms,
 * merge 1659ms, scatter 95ms -> ~2676ms total.
 * (heavy-b's accepted hierarchical-counter version: 3960ms; first place 497ms.)
 * Remaining gap: the 24-level merge is now the bottleneck; reaching ~0.5s needs
 * a cache-blocked radix for the sort AND a cheaper counting scheme.
 */
#include <stdlib.h>
#include <string.h>

typedef unsigned u32;
typedef unsigned long long u64;

void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
    if (n <= 0) return;
    if (n == 1) { out[0] = 0; return; }
    u64 *key = (u64 *)malloc(8 * (size_t)n);
    u64 *key2 = (u64 *)malloc(8 * (size_t)n);
    u32 *id = (u32 *)malloc(4 * (size_t)n);
    u32 *id2 = (u32 *)malloc(4 * (size_t)n);
    u64 *a = (u64 *)malloc(8 * (size_t)n);
    u64 *b = (u64 *)malloc(8 * (size_t)n);
    u32 *ac = (u32 *)calloc((size_t)n, 4);
    u32 *bc = (u32 *)malloc(4 * (size_t)n);
    u32 *cnt = (u32 *)malloc(4 * 65536);
    if (!key || !key2 || !id || !id2 || !a || !b || !ac || !bc || !cnt) return;
    for (int i = 0; i < n; i++) {
        key[i] = ((u64)x[i] << 24) | (u64)(0xFFFFFFu - (y[i] & 0xFFFFFFu));
        id[i] = (u32)i;
    }
    for (int pass = 0; pass < 6; pass++) {
        int sh = pass * 8;
        memset(cnt, 0, 4 * 256);
        for (int i = 0; i < n; i++) cnt[(key[i] >> sh) & 0xFFu]++;
        u32 sum = 0;
        for (int bkt = 0; bkt < 256; bkt++) { u32 c = cnt[bkt]; cnt[bkt] = sum; sum += c; }
        for (int i = 0; i < n; i++) {
            u32 bkt = (u32)((key[i] >> sh) & 0xFFu);
            u32 p = cnt[bkt]++;
            key2[p] = key[i];
            id2[p] = id[i];
        }
        u64 *tk = key; key = key2; key2 = tk;
        u32 *ti = id; id = id2; id2 = ti;
    }
    for (int i = 0; i < n; i++) a[i] = ((u64)y[id[i]] << 24) | (u64)id[i];
    for (int width = 1; width < n; width <<= 1) {
        u64 *src = a, *dst = b;
        u32 *cs = ac, *cd = bc;
        for (int l = 0; l < n; l += width << 1) {
            int mid = l + width; if (mid > n) mid = n;
            int r = l + (width << 1); if (r > n) r = n;
            if (mid >= r) {
                memcpy(dst + l, src + l, 8 * (size_t)(r - l));
                memcpy(cd + l, cs + l, 4 * (size_t)(r - l));
                continue;
            }
            int i = l, j = mid, k = l;
            while (i < mid && j < r) {
                u64 li = src[i], lj = src[j];
                u32 take = (u32)((li >> 24) < (lj >> 24));
                dst[k] = take ? li : lj;
                cd[k] = take ? cs[i] : (cs[j] + (u32)(i - l));
                i += (int)take; j += (int)(take ^ 1); k++;
            }
            while (i < mid) { dst[k] = src[i]; cd[k] = cs[i]; i++; k++; }
            while (j < r) { dst[k] = src[j]; cd[k] = cs[j] + (u32)(i - l); j++; k++; }
        }
        u64 *t = a; a = b; b = t;
        u32 *tc = ac; ac = bc; bc = tc;
    }
    for (int i = 0; i < n; i++) out[(u32)(a[i] & 0xFFFFFFu)] = ac[i];
    free(key); free(key2); free(id); free(id2); free(a); free(b); free(ac); free(bc); free(cnt);
}

评测结果