Cod sursa(job #1233643)

Utilizator Vally77FMI Calinescu Valentin Gelu Vally77 Data 25 septembrie 2014 20:12:42
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream ka("radixsort.in");
ofstream ki("radixsort.out");

const int N_MAX = 10000000;
unsigned long v[N_MAX + 1];
queue <unsigned long> coada[1 << 8];

unsigned long trans_nr(int i, int j)
{
    if(v[i] >= (1 << (8 * j)))
        return v[i] >> (8 * j);
    else
        return 0;
}

int n, a, b, c;
int main()
{
    ka >> n >> a >> b >> c;
    v[1] = b;
    for(int i = 2; i <= n; i++)
    {
        v[i] = (a * v[i-1] + b) % c;
    }
    for(int j = 0; j <= 3; j++)
    {
        for(int i = 1; i <= n; i++)
        {
            coada[trans_nr(i, j) % (1 << 8)].push(v[i]);
        }
        int k = 0;
        for(int i = 0; i < (1 << 8); i++)
        {
            while(!coada[i].empty())
            {
                v[++k] = coada[i].front();
                coada[i].pop();
            }
        }
    }
    for(int i = 1; i <= n; i += 10)
        ki << v[i] << " ";
    ki << '\n';
}