Cod sursa(job #1097533)

Utilizator sunt_emoSunt emo sunt_emo Data 3 februarie 2014 15:59:50
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <fstream>
#include <queue>

#define NMAX 10000010

int v[NMAX];

int main()
{
    std::ifstream in("radixsort.in");
    std::ofstream out("radixsort.out");
    int N, A, B, C;
    std::queue<int> nums[256];
    int size[256];

    in >> N >> A >> B >> C;

    v[1] = B;
    nums[B & 0xFF].push(B);
    for (int i = 2; i <= N; i++)
    {
        v[i] = (A * v[i - 1] + B) % C;
        nums[v[i] & 0xFF].push(v[i]);
    }
    for (int i = 0; i < 256; i++)
        size[i] = nums[i].size();

    for (int i = 0; i < 256; i++)
        for (int j = 0; j < size[i]; j++)
        {
            int k = nums[i].front();
            nums[i].pop();
            nums[(k >> 4) & 0xFF].push(k);
        }
    for (int i = 0; i < 256; i++)
        size[i] = nums[i].size();

    for (int i = 0; i < 256; i++)
        for (int j = 0; j < size[i]; j++)
        {
            int k = nums[i].front();
            nums[i].pop();
            nums[(k >> 8) & 0xFF].push(k);
        }
    for (int i = 0; i < 256; i++)
        size[i] = nums[i].size();

    for (int i = 0; i < 256; i++)
        for (int j = 0; j < size[i]; j++)
        {
            int k = nums[i].front();
            nums[i].pop();
            nums[(k >> 12) & 0xFF].push(k);
        }
    for (int i = 0; i < 256; i++)
        size[i] = nums[i].size();

    int k = 0;
    for (int i = 0; i < 256; i++)
        for (int j = 0; j < size[i]; j++)
        {
            if (k % 10 == 0)
                out << nums[i].front() << " ";
            nums[i].pop();
            k++;
        }
    out << std::endl;

    in.close();
    out.close();
}