Cod sursa(job #2205685)

Utilizator andreiudilaUdila Andrei andreiudila Data 19 mai 2018 21:49:25
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("radixsort.in");
ofstream cout("radixsort.out");

int n,a,b,c,i,maxi;
int v[10000010];
int rez[10000010];
int fr[20];
void radix(int nr)
{
    memset(fr,0,sizeof(fr));
    memset(rez,0,sizeof(rez));

    for(int i=1;i<=n;++i)
        fr[(v[i]/nr)%10] ++;
    for(int i=1;i<=9;++i)
        fr[i]+=fr[i-1];
    for(int i=n;i>=1;--i)
    {
        rez[fr[(v[i]/nr)%10]] = v[i];
        fr[(v[i]/nr)%10]--;
    }

    for(int i=1;i<=n;++i)
        v[i]=rez[i];
}
int main()
{
    cin>>n>>a>>b>>c;
    v[1]=b; maxi = v[1];
    for(i=2;i<=n;++i)
        {
            v[i] = (a*v[i-1]+b) % c;
            maxi = max(maxi,v[i]);
        }

    for(i=1;maxi/i>0;i*=10)
        radix(i);

        radix(i);

    for(i=1;i<=n;i+=10)
        cout<<v[i]<<" ";

    return 0;
}