Cod sursa(job #3208772)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 29 februarie 2024 22:02:57
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <stdio.h>
#pragma GCC optimize "O3"

#define MAX 10000000
int v[MAX];

#define BITS 4
#define MASK 0xf
#define TINY 0x1f

inline void insertion(int lef, int rig) {
  for (int i = lef; i < rig; ++i) {
    int t, j; for (t = v[i], j = i - 1; j >= lef; --j)
      if (t < v[j]) v[j + 1] = v[j]; else break;
    v[j + 1] = t;
  }
}

void radix(int lef, int rig, int bit) {
  int x[MASK + 1], y[MASK + 1], i, j, tmp;
  y[0] = lef; for (int i = 1; i <= MASK; ++i) y[i] = 0;
  for (i = lef; i < rig; ++i) ++y[v[i] >> bit & MASK];
  for (i = 1; i <= MASK; ++i) y[i] += y[i - 1];
  for (i = 1; i <= MASK; ++i) x[i] = y[i - 1]; x[0] = lef;
  for (i = 0; i <= MASK; ++i)
    for (; x[i] < y[i]; ++x[i])
      for (j = v[x[i]] >> bit & MASK; j != i; j = v[x[i]] >> bit & MASK) {
        tmp = v[x[i]]; v[x[i]] = v[x[j]]; v[x[j]++] = tmp; }
  if (bit <= 0) return;
  for (i = 1; i <= MASK; ++i) x[i] = y[i - 1]; x[0] = lef;
  for (i = 0; i <= MASK; ++i) {
    if (y[i] - x[i] < 2) continue;
    if (y[i] - x[i] < TINY) insertion(x[i], y[i]);
    else radix(x[i], y[i], bit - BITS);
  }
}

#define BUFMAX 0xfff
char buf[BUFMAX]; int bufcnt = 0;
inline void write(int x) {
  char dig[11]; int digcnt = 0;
  dig[digcnt++] = ' ';
  do dig[digcnt++] = x % 10 + '0', x /= 10; while (x);

  for (int i = digcnt - 1; i >= 0; --i) {
    if (bufcnt == BUFMAX) fwrite(buf, 1, bufcnt, stdout), bufcnt = 0;
    buf[bufcnt++] = dig[i];
  }
}
inline void flush() {
  fwrite(buf, 1, bufcnt, stdout);
}

int main() {
  freopen("radixsort.in", "r", stdin);
  freopen("radixsort.out", "w", stdout);
  int n, a, c; scanf("%d%d%d%d", &n, &a, &v[0], &c);
  for (int i = 1; i < n; ++i) v[i] = (1ULL * a * v[i - 1] + v[0]) % c;
  radix(0, n, 31 - 31 % BITS);
  for (int i = 0; i < n; i += 10) write(v[i]); flush();
}