Cod sursa(job #1801550)

Utilizator OFY4Ahmed Hamza Aydin OFY4 Data 9 noiembrie 2016 10:21:16
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>

#define nMax 10000007

using namespace std;

const int bucket = 8, lim = (1 << bucket) - 1;
int vaz[lim], v1[nMax], v2[nMax], n;
int a, b, c;

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

int getNum(int x, int ind)
{
    return (x >> (ind * bucket)) & lim;
}

int countSort(int ind)
{
    for(int i = 0; i <= lim; ++i)
        vaz[i] = 0;
    for(int i = 1; i <= n; ++i)
        vaz[getNum(v1[i], ind)]++;
    for(int i = 1; i <= lim; ++i)
        vaz[i]+= vaz[i - 1];
    for(int i = n; i; --i)
        v2[vaz[getNum(v1[i], ind)]--] = v1[i];
    for(int i = 1; i <= n; ++i)
        v1[i] = v2[i];
}

int main()
{
    in >> n >> a >> b >> c;
    v1[1] = b;
    for(int i = 2; i <= n; ++i)
        v1[i] = (1LL * a * v1[i - 1] + b) % c;

    for(int i = 0; i < 32 / bucket; ++i)
        countSort(i);

    for(int i =1; i <= n; i+= 10)
        out << v1[i] << " ";
}