Cod sursa(job #1317932)

Utilizator mariusn01Marius Nicoli mariusn01 Data 15 ianuarie 2015 13:27:44
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>

using namespace std;

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

int v[10000010], w[10000010];
int n, i, A, C, B, m, p;
int f[256];

inline int cif(int x, long long p) {
    //return x/p%10;

    return ((x >> p)&255);
}

int main() {
    fin>>n>>A>>B>>C;
    v[1] = B;
    for (i=2;i<=n;i++) {
        v[i] = (A * 1LL * v[i-1] + B) % C;
        if (v[i] > m)
            m = v[i];
    }

    long long p = 0;
    for (int t = 1; t<= 4; t++) {
        // cifra curenta a lui v[i] este v[i]/p%10;

        for (i=0;i<=255;i++)
            f[i] = 0;

        for (i=1;i<=n;i++)
            f[ cif(v[i], p) ] ++;

        for (i=1;i<=255;i++)
            f[i] += f[i-1];

        for (i=n;i>=1;i--) {
            w[  f[ cif(v[i], p) ] --  ] = v[i];
        }

        for (i=1;i<=n;i++)
            v[i] = w[i];

        p+=8;
    }

    for (i=1;i<=n;i+=10)
        fout<<v[i]<<" ";

    return 0;
}