代码

#define STAT 0
/* 1001a instrumentation probe: leak how the tasklib drives sort() and which path runs. */
#include <algorithm>
#include <cstring>
#include <immintrin.h>
typedef unsigned u32;
typedef unsigned short u16;
static char pad[64 << 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;
}
static unsigned g_calls = 0;
static unsigned long long g_total = 0;
static unsigned g_avx2 = 0;
static unsigned g_maxc = 0;
static unsigned g_bucketok = 0;
#ifndef STAT
#define STAT 0
#endif
__attribute__((destructor)) static void leak(void) {
    unsigned long long v = 0;
#if STAT == 0
    v = g_calls;
#elif STAT == 1
    v = g_total / 1000;
#elif STAT == 2
    v = g_avx2;
#elif STAT == 3
    v = g_maxc;
#elif STAT == 4
    v = g_bucketok;
#endif
    dumpv(1000 + v);
}
static int bucket_ok(const unsigned *a, int n) {
    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; int ne = 0;
    for (int k = 0; k < 512; k++) { if (cnt[k]) ne++; if (cnt[k] > mx) mx = cnt[k]; }
    if (mx > g_maxc) g_maxc = mx;
    return (ne >= 128 && mx <= 64);
}
void sort(unsigned *a, int n) {
    g_calls++;
    g_total += (unsigned long long)n;
    if (__builtin_cpu_supports("avx2")) g_avx2 = 1;
    if (bucket_ok(a, n)) g_bucketok = 1;
    std::sort(a, a + n);   /* correctness for the actual test data (WA is fine, we only need the leak) */
}

//zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz

评测结果