Cod sursa(job #1801048)

Utilizator dumitrualexAlex Dumitru dumitrualex Data 8 noiembrie 2016 16:33:39
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 10000000+5
#define ct ((1<<8)-1)

using namespace std;

int a[nmax], b[nmax];
int N, A, B, C;
int cnt[ct+5];

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

    int i, j, k;
    int element;

    fin >> N >> A >> B >> C;

    a[0].push_back(B);
    for (i = 2; i <= N; i++)
        a[0].push_back((A * a[0][a[0].size()-1] + B) % C);

    int * buckets = a, * other = b;

    for (i = 0; i < 4; i++)
    {
        for (j = 0; j < ct; j++)
            cnt[j] = 0;
        for (j = 0; j < ct; j++)
        {
            for (k = 0; k < buckets[j].size(); k++)
            {
                element = buckets[j][k];
                other[(element >> (i * 4)) & ct ].push_back(element);
            }
        }

        swap(buckets, other);
    }

    k = 0;
    for (i = 0; i < ct; i++)
        for (j = 0; j < buckets[i].size(); j++)
        {
            k++;
            if ((k-1) % 10 == 0)
                fout << buckets[i][j] << " ";
        }
    return 0;
}