Cod sursa(job #1108567)

Utilizator tudorv96Tudor Varan tudorv96 Data 15 februarie 2014 20:10:30
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
using namespace std;

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

const int N = 1e7 + 5;

unsigned a[2][N], n, v[N], A, B, C, MAX, bp;

void Radix_sort(int p) {
    unsigned crt = 1LL << p;
    for (unsigned i = 0; i < n; ++i)
        if (v[i] & crt)
            a[1][++a[1][0]] = v[i];
        else
            a[0][++a[0][0]] = v[i];
    unsigned k = 0;
    for (int i = 0; i < 2; ++i)
        for (unsigned j = 1; j <= a[i][0]; ++j)
            v[k++] = a[i][j];
    a[1][0] = a[0][0] = 0;
    if (p < bp)
        Radix_sort(p+1);
}

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