Cod sursa(job #1115940)

Utilizator mariusn01Marius Nicoli mariusn01 Data 22 februarie 2014 10:59:48
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#define DIM 10000005
using namespace std;

int v[DIM], w[DIM];
int f[256];

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

int n, a, b, c, i, p;

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

    int mask = 0xff;   // mask = 255;

    int a[] = {0, 8, 16, 24};


    for (p = 0; p<=3; p++) {
        // sortam dupa al p-lea grup de 8 biti numarat de la dreapta
        for (i=0;i<=255;i++)
            f[i] = 0;
        for (i=1;i<=n;i++)
            f[  (v[i]>>a[p]) & mask   ]++;
        for (i=1;i<=255;i++)
            f[i] += f[i-1];
        for (i=n;i>=1;i--) {
            w[  f[  (v[i]>>a[p]) & mask  ]   ] = v[i];
            f[  (v[i]>>a[p]) & mask  ] --;
        }
        for (i=1;i<=n;i++)
            v[i] = w[i];
    }
    for (i=1;i<=n;i+=10)
        fout<<v[i]<<" ";
    return 0;
}