Cod sursa(job #1960835)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 10 aprilie 2017 18:31:59
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#define DIM 10000010

using namespace std;

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

int i, a, b, c, n, t, frecv[256];

int v[DIM], w[DIM];

int p;

void build()
{
    v[1]=b;
    for(int i = 2;i <= n; i ++)
    {
        v[i] = (a * 1LL * v[i-1] + b) % c;
    }
}

inline int fract(int x, long long p)
{
    return ((x>>p)&255);
}

int main()
{
    f>>n>>a>>b>>c;

    build();

    long long p = 0;

    for(t=1;t<=4;t++)
    {
        for(i = 0;i <= 255; ++ i)
            frecv[i]=0;

        for(i = 1;i <= n; ++ i)
            frecv[ fract(v[i],p) ] ++;

        for(i = 1;i <= 255; ++ i )
            frecv[i] += frecv[i-1];

        for(i = n;i >= 1; -- i)
        {
            w[ frecv[ fract(v[i],p) ]-- ] = v[i];
        }

        for( i = 1; i <= n; ++ i )
            v[i]=w[i];

        p += 8;

    }

    for( i = 1; i <= n; i += 10 )
        g<<v[i]<<" ";
    return 0;
}