代码

/* wc2017b1 pack3: same as fs2 (fixed-stride MSD by the top byte, no counting
 * pass) but the staging buffer stores only the low 24 bits of every element
 * (3 bytes each, unaligned 4-byte stores, 1 padding byte per bucket), which
 * cuts the first-touch page-fault cost and the scatter traffic by 25%.
 * The bucket phase then sub-buckets by byte 2 (fixed stride) and LSD-sorts
 * bytes 0,1 inside each ~m/256-element sub-bucket straight into `a`. */
#include <stdlib.h>
#include <string.h>

static unsigned g_c0[256], g_c1[256], g_c2[256];

static void bucket_phase(unsigned *a, const unsigned char *tp, int m, unsigned *scr,
                         unsigned *ap, unsigned *loc, unsigned stride2, unsigned topb) {
    (void)a;
    static unsigned fill2[256];
    unsigned off2[256];
    memset(fill2, 0, sizeof(fill2));
    int of = 0;
    {
        const unsigned char *q = tp;
        for (int i = 0; i < m; i++) {
            unsigned v = *(const unsigned *)q & 0xFFFFFFu;
            q += 3;
            unsigned k = (v >> 16) & 255u;
            unsigned f = fill2[k];
            if (f >= stride2) { of = 1; break; }
            scr[(size_t)k * stride2 + f] = v;
            fill2[k] = f + 1;
        }
    }
    if (of) {                              /* adversarial: exact counting partition */
        memset(g_c1, 0, sizeof(g_c1));
        const unsigned char *q = tp;
        for (int i = 0; i < m; i++) { g_c1[(*(const unsigned *)q >> 16) & 255u]++; q += 3; }
        unsigned t = 0;
        for (int k = 0; k < 256; k++) { unsigned c = g_c1[k]; g_c1[k] = t; off2[k] = t; t += c; fill2[k] = c; }
        q = tp;
        for (int i = 0; i < m; i++) { unsigned v = *(const unsigned *)q & 0xFFFFFFu; q += 3; scr[g_c1[(v >> 16) & 255u]++] = v; }
    } else {
        unsigned t = 0;
        for (int k = 0; k < 256; k++) { off2[k] = t; t += fill2[k]; }
    }
    for (int k = 0; k < 256; k++) {
        unsigned cnt = fill2[k];
        unsigned *sk = scr + (of ? (size_t)off2[k] : (size_t)k * stride2);
        if (cnt == 0) continue;
        if (cnt == 1) { ap[off2[k]] = sk[0] | topb; continue; }
        memset(g_c1, 0, sizeof(g_c1));
        for (unsigned i = 0; i < cnt; i++) g_c1[sk[i] & 255u]++;
        unsigned t2 = 0;
        for (int q = 0; q < 256; q++) { unsigned c = g_c1[q]; g_c1[q] = t2; t2 += c; }
        memset(g_c2, 0, sizeof(g_c2));
        for (unsigned i = 0; i < cnt; i++) {
            unsigned v = sk[i];
            loc[g_c1[v & 255u]++] = v;
            g_c2[(v >> 8) & 255u]++;
        }
        t2 = 0;
        for (int q = 0; q < 256; q++) { unsigned c = g_c2[q]; g_c2[q] = t2; t2 += c; }
        unsigned *d = ap + off2[k];
        for (unsigned i = 0; i < cnt; i++) { unsigned v = loc[i]; d[g_c2[(v >> 8) & 255u]++] = v | topb; }
    }
}

void sort(unsigned *a, int n) {
    if (n <= 1) return;
    unsigned stride = (unsigned)((n + 255) / 256) + (unsigned)(n >> 9) + 4096;
    size_t stride3 = (size_t)stride * 3u + 8u;          /* bytes per bucket + pad */
    unsigned char *tmp = (unsigned char *)malloc(stride3 * 256u);
    if (!tmp) return;
    static unsigned fill[256];
    memset(fill, 0, sizeof(fill));
    int i = 0, of = 0;
    for (; i < n; i++) {
        unsigned v = a[i];
        unsigned b = v >> 24;
        unsigned f = fill[b];
        if (f >= stride) { of = 1; break; }
        *(unsigned *)(tmp + (size_t)b * stride3 + (size_t)f * 3u) = v & 0xFFFFFFu;
        fill[b] = f + 1;
    }
    if (of) {
        free(tmp);
        /* adversarial distribution: exact counting partition into a packed buffer */
        memset(g_c0, 0, sizeof(g_c0));
        for (int k = 0; k < n; k++) g_c0[a[k] >> 24]++;
        size_t offb[257];
        unsigned offw[257];
        size_t s = 0; unsigned w = 0; unsigned maxb = 0;
        for (int k = 0; k < 256; k++) { offb[k] = s; offw[k] = w; unsigned c = g_c0[k]; s += (size_t)c * 3u + 1u; w += c; if (c > maxb) maxb = c; }
        offb[256] = s; offw[256] = w;
        unsigned char *tmp2 = (unsigned char *)malloc(s + 8);
        if (!tmp2) return;
        {
            size_t pos[256];
            for (int k = 0; k < 256; k++) pos[k] = offb[k];
            for (int k = 0; k < n; k++) {
                unsigned v = a[k];
                *(unsigned *)(tmp2 + pos[v >> 24]) = v & 0xFFFFFFu;
                pos[v >> 24] += 3;
            }
        }
        unsigned stride2b = (maxb + 255) / 256 + (maxb >> 9) + 1024;
        unsigned *scr = (unsigned *)malloc(((size_t)stride2b * 256u + 1024u) * 4u);
        unsigned *locs2 = (unsigned *)malloc((size_t)(maxb ? maxb : 1) * 4);
        if (!scr || !locs2) { free(scr); free(locs2); free(tmp2); return; }
        for (int b = 0; b < 256; b++) {
            unsigned m = g_c0[b];
            if (m == 0) continue;
            if (m == 1) { unsigned v = *(unsigned *)(tmp2 + offb[b]) & 0xFFFFFFu; a[offw[b]] = v | ((unsigned)b << 24); continue; }
            bucket_phase(a, tmp2 + offb[b], (int)m, scr, a + offw[b], locs2, stride2b, (unsigned)b << 24);
        }
        free(scr); free(locs2); free(tmp2);
        return;
    }
    unsigned off[257];
    unsigned s = 0;
    for (int b = 0; b < 256; b++) { off[b] = s; s += fill[b]; }
    off[256] = s;
    unsigned maxb = 0;
    for (int b = 0; b < 256; b++) if (fill[b] > maxb) maxb = fill[b];
    unsigned stride2 = (maxb + 255) / 256 + (maxb >> 9) + 1024;
    unsigned *scr = (unsigned *)malloc(((size_t)stride2 * 256u + 1024u) * 4u);
    unsigned *locs = (unsigned *)malloc((size_t)(maxb ? maxb : 1) * 4);
    if (!scr || !locs) { free(scr); free(locs); free(tmp); return; }
    for (int b = 0; b < 256; b++) {
        unsigned m = fill[b];
        if (m == 0) continue;
        const unsigned char *tp = tmp + (size_t)b * stride3;
        if (m == 1) { a[off[b]] = (*(const unsigned *)tp & 0xFFFFFFu) | ((unsigned)b << 24); continue; }
        bucket_phase(a, tp, (int)m, scr, a + off[b], locs, stride2, (unsigned)b << 24);
    }
    free(scr);
    free(locs);
    free(tmp);
}

//TOKB1pack3.cppQ

评测结果