Cod sursa(job #1800316)

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

using namespace std;

vector<int> a[ct+5], b[ct+5];
int N, A, B, C;

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);

    vector<int> * buckets = a, * other = b;

    for (i = 0; i < 4; i++)
    {
        for (j = 0; j < ct; j++)
            other[j].clear();
        for (j = 0; j < ct; j++)
        {
            for (k = 0; k < buckets[j].size(); k++)
            {
                element = buckets[j][k];
                other[(element & (ct << (i * 4))) >> (i * 4)].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;
}