Cod sursa(job #1393847)

Utilizator danalex97Dan H Alexandru danalex97 Data 19 martie 2015 19:55:18
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <algorithm>
#include <list>
using namespace std;

ifstream F("radixsort.in");
ofstream G("radixsort.out");

const unsigned int N = 10000010;
const unsigned int M = 1<<16;

unsigned n,x,y,z,a[N];
list<unsigned int> v[M];

void phase1()
{
    for (int i=1;i<=n;++i)
        v[a[i]%M].push_back(a[i]);
    for (int i=M-1,j=0;i>=0;--i)
        while ( !v[i].empty() )
        {
            a[++j] = v[i].back();
            v[i].pop_back();
        }
}

void phase2()
{
    for (int i=1;i<=n;++i)
        v[a[i]/M].push_back(a[i]);
    for (int i=0,j=0;i<M;++i)
        while ( !v[i].empty() )
        {
            a[++j] = v[i].back();
            v[i].pop_back();
        }
}

void mysort()
{
    phase1();
    phase2();
}

int main()
{
    F>>n>>x>>y>>z;
    a[1] = y;
    for (int i=2;i<=n;++i)
        a[i] = (a[i-1] * x + y) % z;
    mysort();
    for (int i=1;i<=n;i+=10)
        G<<a[i]<<' ';
    G<<'\n';
}