Cod sursa(job #1108620)

Utilizator tudorv96Tudor Varan tudorv96 Data 15 februarie 2014 21:24:11
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
using namespace std;

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

const int N = 1e7 + 5, Pow = 8, P = (1 << Pow) - 1;

#define get_byte(x) ((x>>(byte * Pow)) & P)

unsigned n, v[N], w[N], A, B, C;

void count_sort(unsigned *a, unsigned *b, int byte) {
    unsigned k[P+1], sp[P+1];
    for (int i = 0; i <= P; ++i)
        k[i] = sp[i] = 0;
    for (int i = 0; i < n; ++i)
        k[get_byte(a[i])]++;
    for (int i = 1; i <= P; ++i)
        sp[i] = sp[i-1] + k[i-1];
    for (int i = 0; i < n; ++i)
        b[sp[get_byte(a[i])]++] = a[i];
}

void radix_sort() {
    count_sort(v, w, 0);
    count_sort(w, v, 1);
    count_sort(v, w, 2);
    count_sort(w, v, 3);
}

int main() {
    fin >> n >> A >> B >> C;
    v[0] = B;
    for (unsigned i = 1; i < n; ++i)
        v[i] = (1LL * A * v[i-1] + B) % C;
    radix_sort();
    for (unsigned i = 0; i < n; i += 10)
        fout << v[i] << " ";
}