Cod sursa(job #1475526)

Utilizator salam1Florin Salam salam1 Data 24 august 2015 10:43:30
Problema Radix Sort Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <cstdio>
#include <cstring>
const int NMAX = 10000505;
const int FBYTE = (1 << 8) - 1;
const int LMAX = (1 << 8);
int n, a, b, c, A[NMAX], B[NMAX];

int getByte(int idx, int val) {
  return (val & (FBYTE << (idx * 8))) >> (idx * 8);
}

void read() {
  scanf("%d%d%d%d", &n, &a, &b, &c);
  A[1] = b;
  for (int i = 2; i <= n; i++) {
    A[i] = (1LL * a * A[i - 1] + b) % c;
  }
}

void radixSort(int left, int right, int byte) {
  int cnt[LMAX], st[LMAX];
  memset(cnt, 0, sizeof(cnt));
  
  for (int i = left; i <= right; i++) {
    cnt[getByte(byte, A[i])]++;
  }
  st[0] = left - 1;
  for (int i = 1; i <= FBYTE; i++) {
    st[i] = st[i - 1] + cnt[i - 1];
  }
  
  for (int i = left; i <= right; i++) {
    int val = getByte(byte, A[i]);
    B[++st[val]] = A[i];
  }
  for (int i = left; i <= right; i++) {
    A[i] = B[i];
  }
  
  if (byte > 0) {
    for (int i = 0; i <= FBYTE; i++) 
      if (cnt[i] > 1) {
        radixSort(st[i] - cnt[i] + 1, st[i], byte - 1);
      }
  }
}

int main() {
  freopen("radixsort.in", "r", stdin);
  freopen("radixsort.out", "w", stdout);
  
  read();
  radixSort(1, n, 3);
  
  for (int i = 1; i <= n; i += 10)
    printf("%d ", A[i]);
  printf("\n");
  return 0;
}