Cod sursa(job #2297659)

Utilizator RaduXD1Nicolae Radu RaduXD1 Data 6 decembrie 2018 10:21:24
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include<fstream>
#include<cstring>
#include<algorithm>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int maxi,i,n,a,b,c,ex,v[10000001],f[11][10],o[11][10000001];

void Radix(int ex,int nr)
{
    int i;
    for(i=1;i<=n;i++)f[nr][(v[i]/ex)%10]++;
    for(i=1;i<=9;i++)f[nr][i]+=f[nr][i-1];
    for(i=n;i>=1;i--)o[nr][f[nr][(v[i]/ex)%10]--]=v[i];
    memcpy(v,o[nr],sizeof(v));
}

int main()
{
    fin>>n>>a>>b>>c;v[1]=b;maxi=b;
    for(i=2;i<=n;i++){v[i]=(a*v[i-1]+b)%c;maxi=max(maxi,v[i]);}
    for(ex=1,i=0;ex<=maxi;ex*=10,i++)Radix(ex,i);
    for(i=1;i<=n;i+=10) fout<<v[i]<<" ";
    return 0;
}