Cod sursa(job #1602374)

Utilizator RadduFMI Dinu Radu Raddu Data 16 februarie 2016 19:07:51
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define ll long long
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
 int n,a,b,c,v[10000005],v2[10000005],ap[260],s[260];


void Radix(int b1)
{ int i;
  memset(ap,0,sizeof(ap));
  for(i=1;i<=n;i++)
   ap[(v[i]>>b1)&255]++;

  s[0]=ap[0];
  for(i=1;i<=255;i++)
   s[i]=s[i-1]+ap[i];

  for(i=n;i>=1;i--)
  { v2[s[((v[i]>>b1)&255)-1]+ap[((v[i]>>b1)&255)]]=v[i];
    ap[((v[i]>>b1)&255)]--;
  }

  for(i=1;i<=n;i++)
   v[i]=v2[i];
}

int main()
{ int i;
   f>>n>>a>>b>>c;
   v[1]=b;

   for(i=2;i<=n;i++)
    v[i]=((ll) a*v[i-1]+b)%c;

  for(i=0;i<32;i+=8)
   Radix(i);

  for(i=1;i<=n;i+=10)
   g<<v[i]<<" ";

    return 0;
}