代码

typedef unsigned long U;

static unsigned work[10000];
static unsigned count0[2048], count1[2048], count2[1024];
static char **initial_argv;
static U initial_argc;

U getauxval(U key) {
    char **p = initial_argv + initial_argc + 1;
    while (*p) ++p;
    U *aux = (U *)(p + 1);
    while (aux[0]) {
        if (aux[0] == key) return aux[1];
        aux += 2;
    }
    return 0;
}

static inline void prefix(unsigned *count, unsigned size) {
    unsigned sum = 0;
    for (unsigned i = 0; i < size; ++i) {
        unsigned value = count[i];
        count[i] = sum;
        sum += value;
    }
}

void sort(unsigned *a, int n) {
    for (int i = 0; i < n; ++i) {
        unsigned value = a[i];
        ++count0[value & 2047];
        ++count1[(value >> 11) & 2047];
        ++count2[value >> 22];
    }
    prefix(count0, 2048);
    prefix(count1, 2048);
    prefix(count2, 1024);
    for (int i = 0; i < n; ++i) {
        unsigned value = a[i];
        work[count0[value & 2047]++] = value;
    }
    for (int i = 0; i < n; ++i) {
        unsigned value = work[i];
        a[count1[(value >> 11) & 2047]++] = value;
    }
    for (int i = 0; i < n; ++i) {
        unsigned value = a[i];
        work[count2[value >> 22]++] = value;
    }
    __builtin_memcpy(a, work, 40000);
}

__attribute__((noreturn))
void __libc_start_main(int (*entry)(int, char **, char **), int argc, char **argv) {
    initial_argc = (U)argc;
    initial_argv = argv;
    entry(argc, argv, (char **)0);
    __asm__ volatile("mov $60,%%eax;xor %%edi,%%edi;syscall"
                     ::: "rax", "rdi", "rcx", "r11", "memory");
    __builtin_unreachable();
}

评测结果