Cod sursa(job #1430375)

Utilizator hrazvanHarsan Razvan hrazvan Data 8 mai 2015 12:01:07
Problema Radix Sort Scor 30
Compilator c Status done
Runda Arhiva educationala Marime 1.66 kb
#include <stdio.h>
#define MAXN 10000000
#define BYTE 16
#define NRBCK (1 << 16)
#define BUFF 21
FILE *out;
int v[MAXN], next[MAXN], prim, ult[NRBCK], pr[NRBCK];
int poz = 0;
char buff[(1 << BUFF) + 1];

inline void radixsort(int n){
  int i, j, p, bck, np;
  prim = 0;
  for(i = 0; i < 2; i++){
    for(j = 0; j < (1 << BYTE); j++){
      ult[j] = n;
      pr[j] = n;
    }
    p = prim;
    for(j = 0; j < n; j++){
      np = next[p];
      bck = (v[p] >> (BYTE * i)) & ((1 << BYTE) - 1);
      if(ult[bck] != n)
        next[ult[bck]] = p;
      else
        pr[bck] = p;
      next[p] = n;
      ult[bck] = p;
      p = np;
    }
    j = 0;
    while(ult[j] == n)
      j++;
    prim = pr[j];
    p = j;
    for(j++; j < NRBCK; j++){
      if(pr[j] != n){
        next[ult[p]] = pr[j];
        p = j;
      }
    }
  }
}

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;
  next[0] = 1;
  for(i = 1; i < n; i++){
    v[i] = (1LL * a * v[i - 1] + b) % c;
    next[i] = i + 1;
  }
  radixsort(n);
  out = fopen("radixsort.out", "w");
  int p = prim;
  for(i = 0; i < n; i++){
    if(i % 10 == 0)
      print(v[p]);
    p = next[p];
  }
  flush();
  fclose(out);
  return 0;
}