Cod sursa(job #1519032)

Utilizator DjokValeriu Motroi Djok Data 6 noiembrie 2015 18:45:32
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<bits/stdc++.h>
using namespace std;

int i,j,a[10000005],b[10000005],N,Ax,Bx,Cx,aux[260];

int main()
{
  ifstream cin("radixsort.in");
  ofstream cout("radixsort.out");

  ios_base::sync_with_stdio(0); cin.tie(0);

  cin>>N>>Ax>>Bx>>Cx; a[1]=Bx;

  for(i=2;i<=N;++i) a[i]=(1LL*Ax*a[i-1]+Bx)%Cx;

  for(j=0;j<25;j+=8)
  {
    memset(aux,0,sizeof(aux));

    for(i=1;i<=N;++i) ++aux[(a[i]>>j)&255];

    for(i=1;i<256;++i) aux[i]+=aux[i-1];

    for(i=N;i;--i) b[aux[(a[i]>>j)&255]--]=a[i];

    memcpy(a,b,sizeof(b));
  }

  for(i=1;i<=N;i+=10) cout<<a[i]<<" \n"[i+10>N];

 return 0;
}