Cod sursa(job #1647662)

Utilizator mateidanutDanut Gabriel Matei mateidanut Data 10 martie 2016 21:33:10
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
using namespace std;

const long long NMAX=10000003;
long long a[NMAX], n;

ifstream f("radixsort.in");
ofstream g("radixsort.out");

void Sort(int p)
{   long long v[20], b[NMAX], i, x;
    for (i=0; i<10; ++i)
        v[i]=0;
    for (i=1; i<=n; ++i)
    {   x=(a[i]/p)%10;
        v[x]++;
    }
    for (i=1; i<10; ++i)
        v[i]+=v[i-1];
    for (i=n; i; --i)
    {   x=(a[i]/p)%10;
        b[v[x]--]=a[i];
    }
    for (i=1; i<=n; ++i)
        a[i]=b[i];
}

void Radix(long long maxi)
{   for (long long p=1; p<=maxi; p=p*10)
        Sort(p);
}

void Citire()
{   long long v, b, c, i;
    f>>n>>v>>b>>c;
    a[1]=b;
    for (i=2; i<=n; ++i)
        a[i]=(v*a[i-1]+b)%c;
}

int main()
{   Citire();
    long long i, maxi=0;
    f>>n;
    for (i=1; i<=n; ++i)
        maxi=max(maxi, a[i]);
    Radix(maxi);
    for (i=1; i<=n; i+=10)
        g<<a[i]<<' ';
    return 0;
}