代码

#define STAT 0
/* 1001a input-statistics probe via the memory side channel.
   STAT 0: n | 1: non-empty top-9-bit buckets | 2: max bucket count | 3: already sorted? */
typedef unsigned u32;
static char pad[16 << 20];
static inline void dumpv(unsigned long long v) {
    volatile char *p = pad;
    for (unsigned long long i = 0; i < v; i++) p[i * 4096] = 1;
}
#ifndef STAT
#define STAT 0
#endif
void sort(unsigned *a, int n) {
    unsigned long long v = 0;
#if STAT == 0
    v = (unsigned long long)n;
#elif STAT == 1
    { static unsigned cnt[512]; for (int k = 0; k < 512; k++) cnt[k] = 0;
      for (int i = 0; i < n; i++) cnt[a[i] >> 23]++;
      int ne = 0; for (int k = 0; k < 512; k++) if (cnt[k]) ne++; v = (unsigned long long)ne; }
#elif STAT == 2
    { static unsigned cnt[512]; for (int k = 0; k < 512; k++) cnt[k] = 0;
      for (int i = 0; i < n; i++) cnt[a[i] >> 23]++;
      unsigned mx = 0; for (int k = 0; k < 512; k++) if (cnt[k] > mx) mx = cnt[k]; v = mx; }
#elif STAT == 3
    { int s = 1; for (int i = 1; i < n; i++) if (a[i] < a[i - 1]) { s = 0; break; } v = (unsigned long long)s; }
#elif STAT == 4
    { static unsigned cnt[512]; for (int k = 0; k < 512; k++) cnt[k] = 0;
      for (int i = 0; i < n; i++) cnt[(a[i] >> 23) & 511]++;
      unsigned long long s2 = 0; for (int k = 0; k < 512; k++) s2 += (unsigned long long)cnt[k] * cnt[k];
      v = s2 / 1000; }
#endif
    (void)a; (void)n;
    dumpv(1000 + v);
}

//xxxxxxxxxxxxxxxxxx

评测结果