Cod sursa(job #1152141)

Utilizator ArmandNMArmand Nicolicioiu ArmandNM Data 24 martie 2014 16:05:06
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>
#include <cstring>

const int NMAX = 10000001;
const int mask = 0xff;

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

int N,A,B,C,v[NMAX],pos;

void radix(int part)
{
    vector <int> bucket[mask+2];
    memset(bucket, 0, sizeof(bucket));

    for (int i = 1; i <= N; ++i)
    {
        bucket[ (v[i] >> part) % mask ].push_back(v[i]);
    }

    pos = 0;

    for (int i = 0; i <= mask; ++i)
    {
        for (int j = 0; j < bucket[i].size(); ++j)
        {
            v[++pos] = bucket[i][j];
        }
    }

}

void solve()
{
    for (int i = 0; i < 4; ++i)
    {
        radix( i * 8 );
    }
}

int main()
{
    f >> N >> A >> B >> C;
    v[1] = B;
    for (int i = 2; i <= N; ++i)
    {
        v[i] = (1LL * A * v[i-1] + B) % C;
    }

    solve();

    for (int i = 1; i <= N; i+=10)
    {
        g << v[i] << " ";
    }

    f.close();
    g.close();
    return 0;
}