/* wc2017b1 data-distribution probe via mem-channel.
* sort() computes ONE statistic of a[0..n) and encodes dig (0..9999) into
* big[] via memset(big, 1, dig*4096). Reported per-testcase Memory (KiB) =
* base + dig*4 KiB. MODE selects the statistic.
*/
#include <string.h>
typedef unsigned int u32;
#define MODE 3
static char big[10000 * 4096] __attribute__((aligned(4096)));
static int ilog2ll(unsigned long long x) {
return 63 - __builtin_clzll(x);
}
static unsigned do_stat(const u32 *a, int n) {
int i;
unsigned dig = 0;
switch (MODE) {
case 1: { /* in-order fraction (full value) *9999 */
long long c = 0;
for (i = 0; i + 1 < n; i++) if (a[i] <= a[i+1]) c++;
dig = (unsigned)(c * 9999 / (n - 1));
break;
}
case 2: { /* number of DISTINCT top-16 values (capped 9999) */
static unsigned char seen[65536];
int d = 0;
for (i = 0; i < n; i++) { unsigned b = a[i] >> 16; if (!seen[b]) { seen[b] = 1; d++; } }
dig = (unsigned)(d > 9999 ? 9999 : d);
break;
}
case 3: { /* max top byte (a[i]>>24), 0..255 */
unsigned m = 0;
for (i = 0; i < n; i++) { unsigned b = a[i] >> 24; if (b > m) m = b; }
dig = m;
break;
}
case 4: { /* histogram entropy of top byte, floor-log2 approx *1000 */
static unsigned long long hist[256];
for (i = 0; i < 256; i++) hist[i] = 0;
for (i = 0; i < n; i++) hist[a[i] >> 24]++;
unsigned long long sclog = 0;
for (i = 0; i < 256; i++) if (hist[i]) sclog += hist[i] * (unsigned)ilog2ll(hist[i]);
unsigned long long nlog = (unsigned long long)n * (unsigned)ilog2ll((unsigned long long)n);
unsigned long long num = nlog > sclog ? nlog - sclog : 0;
dig = (unsigned)(num * 1000 / (unsigned long long)n);
break;
}
case 5: { /* max value >> 16 (top 16 bits of max), capped 9999 */
unsigned m = 0;
for (i = 0; i < n; i++) if (a[i] > m) m = a[i];
dig = (unsigned)(m >> 16);
if (dig > 9999) dig = 9999;
break;
}
case 6: { /* in-order fraction of LOW byte *9999 */
long long c = 0;
for (i = 0; i + 1 < n; i++) if ((a[i] & 255) <= (a[i+1] & 255)) c++;
dig = (unsigned)(c * 9999 / (n - 1));
break;
}
case 7: { /* longest sorted run (capped 9999) */
unsigned best = 0, cur = 1;
for (i = 1; i < n; i++) { if (a[i-1] <= a[i]) cur++; else { if (cur > best) best = cur; cur = 1; } }
if (cur > best) best = cur;
dig = best > 9999 ? 9999 : best;
break;
}
case 8: { /* fraction of adjacent pairs differing by exactly 1 *9999 */
long long c = 0;
for (i = 0; i + 1 < n; i++) { u32 x = a[i], y = a[i+1]; if (x == y + 1 || y == x + 1) c++; }
dig = (unsigned)(c * 9999 / (n - 1));
break;
}
case 9: { /* min value >> 16 (top 16 bits of min), capped 9999 */
unsigned m = ~0u;
for (i = 0; i < n; i++) if (a[i] < m) m = a[i];
dig = (unsigned)(m >> 16);
if (dig > 9999) dig = 9999;
break;
}
case 10: { /* max value >> 8 (top 24 bits of max), capped 9999 */
unsigned m = 0;
for (i = 0; i < n; i++) if (a[i] > m) m = a[i];
dig = (unsigned)(m >> 8);
if (dig > 9999) dig = 9999;
break;
}
case 11: { /* exact max value, low 14 bits (max & 16383) */
unsigned m = 0;
for (i = 0; i < n; i++) if (a[i] > m) m = a[i];
dig = m & 16383;
break;
}
default:
dig = 0;
}
return dig;
}
void sort(unsigned *a, int n) {
unsigned dig = do_stat(a, n);
if (dig > 9999) dig = 9999;
memset(big, 1, (size_t)dig * 4096);
}