Cod sursa(job #2190890)

Utilizator hrazvanHarsan Razvan hrazvan Data 31 martie 2018 22:22:51
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <cstdio>
#include <cstring>
#define MAXN 10000000
#define D 8
#define BUFF (1<<16)
#define MASK ((1 << D) - 1)
int v[MAXN], nr[MASK], aux[MAXN];
char s[BUFF + 1];
int ds;
FILE *out;

inline void flush(){
  s[ds] = 0;
  fputs(s, out);
  ds = 0;
}

inline void afisch(char ch){
  s[ds++] = ch;
  if(ds == BUFF)
    flush();
}

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

int main(){
  FILE *in = fopen("radixsort.in", "r");
  int n, a, b, c, l, i, sft;
  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;
  }
  l = 0;
  for(sft = 0; sft < 32; sft += D){
    l = !l;
    memset(nr, 0, sizeof nr);
    for(i = 0; i < n; i++){
      nr[(v[i] >> sft) & MASK]++;
    }
    for(i = 1; i <= MASK; i++){
      nr[i] += nr[i - 1];
    }
    for(i = n - 1; i >= 0; i--){
      aux[--nr[(v[i] >> sft) & MASK]] = v[i];
    }
    for(i = 0; i < n; i++)
      v[i] = aux[i];
  }
  out = fopen("radixsort.out", "w");
  for(i = 0; i < n; i += 10)
    afis(v[i]);
  flush();
  fclose(out);
  return 0;
}