Cod sursa(job #2446190)

Utilizator GabyD002Dobrita Gabriel GabyD002 Data 7 august 2019 13:58:23
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
#define NM 10000005
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");

int n,a,b,c,k,p=1,fr[15],v[NM],grupe[15][NM/10];
void Read();
void Solve();

int main()
{   Read();
    Solve();
    return 0;
}

void Read()
{   f>>n>>a>>b>>c;
    v[1]=b;
    int nrCif=0,aux=b;
    while(aux)
    {   nrCif++;
        aux/=10;
    }
    k=max(nrCif,k);
    for(int i=2; i<=n; i++)
    {   v[i]=(a*v[i-1]+b)%c;
        nrCif=0;
        aux=v[i];
        while(aux)
        {   nrCif++;
            aux/=10;
        }
        k=max(nrCif,k);
    }
}

void Solve()
{   for(int pas=1; pas<=k; pas++)
    {   memset(fr,0,sizeof(fr));
        for(int i=1; i<=n; i++)
        {   int uc=(v[i]/p)%10;
            grupe[uc][++fr[uc]]=v[i];
        }
        p*=10;
        n=0;
        for(int i=0; i<10; i++)
            for(int j=1; j<=fr[i]; j++)
                v[++n]=grupe[i][j];
    }
    for(int i=1; i<=n; i+=10)
        g<<v[i]<<' ';
}