Cod sursa(job #1318501)

Utilizator Vladut-Vlad Panait Vladut- Data 16 ianuarie 2015 00:04:33
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>

using namespace std;

#define maxn 10000005
#define base 255

ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");

int v[maxn], s[maxn], g[base+1];

int cifra(int x)
{
    int t=0;
    do
    {
        x>>=1;
        t++;
    }
    while (x);
    return t;
}

int main()
{
    int n, a, b, c, i, m, p, nr;
    fin >> n >> a >> b >> c;
    v[0]=b;
    m=0;
    for (i=0; i<n; i++)
        {
            v[i]=(a*v[i-1]+b)%c;
            if (v[i]>m)
                m=v[i];
        }
    nr=cifra(m);
    for (p=0; p<nr; p+=8)
    {
        for(i=0; i<n; i++)
            g[i]=0;

        for (i=0; i<n; i++)
            g[(v[i]>>p)&base]++;

        for (i=1; i<=base; i++)
            g[i]+=g[i-1];

        for (i=n-1; i>=0; i--)
            s[--g[(v[i]>>p)&base]]=v[i];

        for (i=0; i<n; i++)
            v[i]=s[i];
    }
    for (i=0; i<n; i+=10)
    fout << v[i] << ' ';
    fin.close();
    fout.close();
    return 0;
}