Cod sursa(job #1456638)

Utilizator CollermanAndrei Amariei Collerman Data 1 iulie 2015 14:14:34
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
using namespace std;
ofstream fout("radixsort.out");
ifstream fin("radixsort.in");
const int NMAX = 10000005;
const int MASK = (1 << 8) - 1; // 255

int n, A, B, C, key;
int v[NMAX], aux[NMAX], bucket[MASK + 2];

void citire()
{
    fin >> n >> A >> B >> C;
    v[1] = B;
    for(int i=2; i<=n; i++) {
        v[i] = (1LL * A * v[i-1] + B) % C; // 1LL = conversie in long long
    }
}

void radix_sort()
{
    for(int shift = 0; shift < 32; shift += 8) { // 4 pași
        for(int i = 1; i <= n; i++) {
            key = (v[i] >> shift) & MASK; // mascare binară
            bucket[key]++;
        }

        for(int i = 0; i <= MASK; i++) {
            bucket[i] += bucket[i - 1];
        }

        for(int i = n; i; i--) {
            key = (v[i] >> shift) & MASK; // mascare binară
            aux[bucket[key]--] = v[i];
        }

        for(int i = 1; i <= n; i++) {
            v[i] = aux[i];
        }

        for(int i = 1; i <= MASK; i++) {
            bucket[i] = 0;
        }
    }
}

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

int main()
{
    citire();
    radix_sort();
    afis();

    fout.close();
    fin.close();
    return 0;
}