Cod sursa(job #1111214)

Utilizator MutescuMutescu Alexandru Mutescu Data 18 februarie 2014 18:31:19
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<cstdio>
#define Ser 10000005
#define py (1<<8)-1
using namespace std;
long long  a,b,c,n,i,in[py],bi[Ser],v[Ser];
void radixsort(long long  a[Ser], long long n)
{
  long long mx= a[0], lv = 1;
  for (i=1;i<n;++i)
    if (a[i] > mx)
      mx=a[i];

  while (mx/lv > 0)
  {

    for (i = 0; i < n; i++)
      in[(a[i]/lv)%256]++;
    for (i = 1; i < 256; i++)
     in[i] += in[i - 1];
    for (i = n - 1; i >= 0; i--)
      bi[--in[(a[i] / lv) % 256]] = a[i];
    for (i = 0; i < n; i++)
      a[i] = bi[i];
    lv *= 256;

  }
}

int main()

{ freopen ("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);

  scanf("%d%d%d%d", &n,&a,&b,&c);
  v[0]=b;
   for (i =1; i < n; i++)
  v[i] = (a * v[i-1] + b) % c;




  radixsort(v, n);


  for (i = 0; i < n; i+=10)
    printf("%d ", v[i]);


  return 0;
}