代码

#pragma GCC optimize("Ofast")
#include <cstdio>
#include <algorithm>

using u32 = unsigned int;

void sort(u32 *a, int n) {
  u32 *ed = a + n;
  u32 *b = new u32[n];
  static int cnt0[256], cnt8[256], cnt16[256], cnt24[256];
  std::fill(cnt0, cnt0 + 256, 0);
  std::fill(cnt8, cnt8 + 256, 0);
  std::fill(cnt16, cnt16 + 256, 0);
  std::fill(cnt24, cnt24 + 256, 0);
  u32 *p, *q;
  for (p = a; p != ed; ++p) {
    ++cnt0[static_cast<u32>(*p) & 255];
    ++cnt8[static_cast<u32>(*p) >> 8 & 255];
    ++cnt16[static_cast<u32>(*p) >> 16 & 255];
    ++cnt24[static_cast<u32>(*p) >> 24];
  }
  for (int i = 1; i < 256; ++i) {
    cnt0[i] += cnt0[i - 1];
    cnt8[i] += cnt8[i - 1];
    cnt16[i] += cnt16[i - 1];
    cnt24[i] += cnt24[i - 1];
  }
  for (p = a + n - 1; p - 7 >= a; p -= 8) {
    b[--cnt0[static_cast<u32>(*p) & 255]] = *p;
    b[--cnt0[static_cast<u32>(p[-1]) & 255]] = p[-1];
    b[--cnt0[static_cast<u32>(p[-2]) & 255]] = p[-2];
    b[--cnt0[static_cast<u32>(p[-3]) & 255]] = p[-3];
    b[--cnt0[static_cast<u32>(p[-4]) & 255]] = p[-4];
    b[--cnt0[static_cast<u32>(p[-5]) & 255]] = p[-5];
    b[--cnt0[static_cast<u32>(p[-6]) & 255]] = p[-6];
    b[--cnt0[static_cast<u32>(p[-7]) & 255]] = p[-7];
  }
  for (; p >= a; --p) {
    b[--cnt0[static_cast<u32>(*p) & 255]] = *p;
  }
  for (q = b + n - 1; q - 7 >= b; q -= 8) {
    a[--cnt8[static_cast<u32>(*q) >> 8 & 255]] = *q;
    a[--cnt8[static_cast<u32>(q[-1]) >> 8 & 255]] = q[-1];
    a[--cnt8[static_cast<u32>(q[-2]) >> 8 & 255]] = q[-2];
    a[--cnt8[static_cast<u32>(q[-3]) >> 8 & 255]] = q[-3];
    a[--cnt8[static_cast<u32>(q[-4]) >> 8 & 255]] = q[-4];
    a[--cnt8[static_cast<u32>(q[-5]) >> 8 & 255]] = q[-5];
    a[--cnt8[static_cast<u32>(q[-6]) >> 8 & 255]] = q[-6];
    a[--cnt8[static_cast<u32>(q[-7]) >> 8 & 255]] = q[-7];
  }
  for (; q >= b; --q) {
    a[--cnt8[*q >> 8 & 255]] = *q;
  }
  for (p = a + n - 1; p - 7 >= a; p -= 8) {
    b[--cnt16[static_cast<u32>(*p) >> 16 & 255]] = *p;
    b[--cnt16[static_cast<u32>(p[-1]) >> 16 & 255]] = p[-1];
    b[--cnt16[static_cast<u32>(p[-2]) >> 16 & 255]] = p[-2];
    b[--cnt16[static_cast<u32>(p[-3]) >> 16 & 255]] = p[-3];
    b[--cnt16[static_cast<u32>(p[-4]) >> 16 & 255]] = p[-4];
    b[--cnt16[static_cast<u32>(p[-5]) >> 16 & 255]] = p[-5];
    b[--cnt16[static_cast<u32>(p[-6]) >> 16 & 255]] = p[-6];
    b[--cnt16[static_cast<u32>(p[-7]) >> 16 & 255]] = p[-7];
  }
  for (; p >= a; --p) {
    b[--cnt16[static_cast<u32>(*p) >> 16 & 255]] = *p;
  }
  for (q = b + n - 1; q - 7 >= b; q -= 8) {
    a[--cnt24[static_cast<u32>(*q) >> 24]] = *q;
    a[--cnt24[static_cast<u32>(q[-1]) >> 24]] = q[-1];
    a[--cnt24[static_cast<u32>(q[-2]) >> 24]] = q[-2];
    a[--cnt24[static_cast<u32>(q[-3]) >> 24]] = q[-3];
    a[--cnt24[static_cast<u32>(q[-4]) >> 24]] = q[-4];
    a[--cnt24[static_cast<u32>(q[-5]) >> 24]] = q[-5];
    a[--cnt24[static_cast<u32>(q[-6]) >> 24]] = q[-6];
    a[--cnt24[static_cast<u32>(q[-7]) >> 24]] = q[-7];
  }
  for (; q >= b; --q) {
    a[--cnt24[static_cast<u32>(*q) >> 24 ^ 128]] = *q;
  }
  delete[] b;
}

评测结果