Cod sursa(job #1430383)

Utilizator hrazvanHarsan Razvan hrazvan Data 8 mai 2015 12:18:13
Problema Radix Sort Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.38 kb
#include <stdio.h>
#define MAXN 10000000
#define BITE 16
#define NRBCK (1 << 16)
#define BUFF 21
#define MASK ((1 << BITE) - 1)
FILE *out;
int v[MAXN], fr[NRBCK], aux[MAXN];
int poz = 0;
char buff[(1 << BUFF) + 1];

inline void radixsort(int n){
  int i, j, bck;
  for(i = 0; i < 2; i++){
    for(j = 0; j < n; j++)
      fr[(v[j] >> (BITE * i)) & MASK]++;
    for(j = 1; j < NRBCK; j++)
      fr[j] += fr[j - 1];
    for(j = n - 1; j >= 0; j--){
      bck = (v[j] >> (BITE * i)) & MASK;
      aux[fr[bck] - 1] = v[j];
      fr[bck]--;
    }
    for(j = 0; j < n; j++)
      v[j] = aux[j];
    for(j = 0; j < NRBCK; j++)
      fr[j] = 0;
  }
}

inline void flush(){
  buff[poz] = '\0';
  fputs(buff, out);
  poz = 0;
}

inline void add(char ch){
  buff[poz] = ch;
  poz++;
  if(poz == (1 << BUFF)){
    flush();
  }
}

inline void print(int x){
  int p10 = 1;
  while(1LL * p10 * 10 <= x)
    p10 *= 10;
  while(p10 > 0){
    add(x / p10 % 10 + '0');
    p10 /= 10;
  }
  add(' ');
}

int main(){
  FILE *in = fopen("radixsort.in", "r");
  int n, a, b, c, i;
  fscanf(in, "%d%d%d%d", &n, &a, &b, &c);
  fclose(in);
  v[0] = b;
  for(i = 1; i < n; i++){
    v[i] = (1LL * a * v[i - 1] + b) % c;
  }
  radixsort(n);
  out = fopen("radixsort.out", "w");
  for(i = 0; i < n; i += 10)
    print(v[i]);
  flush();
  fclose(out);
  return 0;
}