Cod sursa(job #2680815)

Utilizator Luca_Miscocilucainfoarena Luca_Miscoci Data 4 decembrie 2020 14:07:40
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <stdio.h>
#include <string.h>
#define NMAX 10000000
#define MAX_BITS 32
#define BITS_PER_STEP 8
#define BASE ( 1 << 8 )
#define MASK (1 << 8) - 1
using namespace std;
int v[NMAX + 3],v1[NMAX + 3] ,f[BASE + 3], ind[BASE + 3];
void mysort (int vec[] , int aux[] ,int n ,int bits){
  int nr,maxx;
  maxx = 0;
  if (bits == MAX_BITS)
    return;
  memset (f ,0, sizeof(f));
  for (int i = 0; i < n; i++) {
    nr = vec[i] >> bits & MASK;
    f[nr]++;
    if(nr > maxx){
      maxx = nr;
    }
  }

  ind[0] = 0;
  for (int i = 1; i <= maxx; i++)
    ind[i] = f[i - 1] + ind[i - 1];

  for (int i = 0; i < n; i  ++) {
    nr = vec[i] >> bits & MASK;
    aux[ind[nr]++] = vec[i];
  }
  mysort(aux , vec ,n ,bits + BITS_PER_STEP);
}
int main(){
  FILE *fin ,*fout;
  fin = fopen("radixsort.in","r");
  fout = fopen("radixsort.out","w");
  int a, b, c, n;
  fscanf(fin , "%d%d%d%d" ,&n ,&a ,&b, &c);
  v[0] = b;
  for (int i = 1;i < n; i++){
    v[i] = ((long long) a * v[i - 1] + b) % c;
  }
  mysort(v,v1,n,0);
  for(int i = 0; i < n; i += 10)
    fprintf(fout, "%d " ,v[i]);
  return 0;
}