Cod sursa(job #1151576)

Utilizator Ionut228Ionut Calofir Ionut228 Data 24 martie 2014 11:16:13
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

const int mask = 0xff;

int N, A, B, C;
int V[10000001];

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

    for (int i = 1; i <= N; ++i)
        bucket[(V[i] >> part) & mask].push_back(V[i]);

    for (int i = 0; i <= mask; ++i)
        for (vector<int>::iterator it = bucket[i].begin(); it != bucket[i].end(); ++it)
            V[++pos] = *it;
}

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

int main()
{
    fin >> N >> A >> B >> C;
    V[1] = B;
    for (int i = 2; i <= N; ++i)
        V[i] = (A * V[i - 1] + B) % C;

    solve();

    for (int i = 1; i <= N; i += 10)
        fout << V[i] << ' ';

    fin.close();
    fout.close();
    return 0;
}