Cod sursa(job #1519023)

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

int i,j,a[10000005],b[10000005],N,Ax,Bx,Cx,aux[11],MOD=10;
bool ok=1;

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=1;j<9 && ok;++j,MOD*=10)
  {
    memset(aux,0,sizeof(aux));

    for(ok=0,i=1;i<=N;++i)
    {
      ++aux[(a[i]%MOD)/(MOD/10)];
      if(a[i]/MOD) ok=1;
    }

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

    for(i=N;i;--i) b[aux[(a[i]%MOD)/(MOD/10)]]=a[i],--aux[(a[i]%MOD)/(MOD/10)];

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

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

 return 0;
}