Cod sursa(job #2191061)

Utilizator Narvik13Razvan Roatis Narvik13 Data 1 aprilie 2018 15:20:47
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
///RADIX SORT PE CIFRE
#include <iostream>
#include <fstream>
#include <queue>
#define NMAX 10000002

using namespace std;

ifstream f("radixsort.in");
ofstream o("radixsort.out");

int n,a,b,c;
int v[NMAX];
const int an[] = {255, 255 << 8, 255 << 16, 255 << 24};
queue <int> q[256];

void input()
{
    f >> n >> a >> b >> c;
    v[1] = b;
    for(int i = 2; i <= n; ++i)
            v[i] = (1LL * a * v[i-1] + b) % c;
}

void radix_sort()
{
    for(int i = 0; i < 4; ++i)
    {
        for(int j = 1; j <= n; ++j)
            q[(v[j] & an[i]) >> (8 * i)].push(v[j]);

        int p = 0;
        for(int i = 0; i <= 255; ++i)
            while(not q[i].empty())
            {
                v[++p] = q[i].front();
                q[i].pop();
            }


    }
}

void output()
{
    for(int i = 1; i <= n; i += 10)
        o << v[i] << ' ';
}

int main()
{
    input();
    radix_sort();
    output();
    return 0;
}