Cod sursa(job #1097704)

Utilizator Theorytheo .c Theory Data 3 februarie 2014 20:59:32
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <cstring>

using namespace std;

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

int N;

class Radixsort {

    static const int NMAX = 10000009;
    static const int MASK = (1 << 8) - 1;


    public:

    int V[NMAX]; int A; int B; int C; int T[NMAX];

    void generate () {

        V[1] = B;
        for(int i = 2; i <= N; ++i)
            V[i] = (1ll * V[i - 1] * A + 1ll * B) % C;
    }

    void thesort() {

        int count[MASK + 3];

        for(int shift = 0, step = 1; step <= 4; shift += 8, step++) {

            memset(count, 0, sizeof(count));
            for(int i = 1; i <= N; ++i) count[(V[i] >> shift) & MASK]++;
            for(int i = 0 ;i <= MASK; ++i) count[i] += count[i - 1];
            for(int i = N; i ; --i) T[count[(V[i] >> shift) & MASK]--] = V[i];

            memcpy(V, T, sizeof(V));
        }
    }

    void print() {

        for(int i = 1; i <= N; i += 10)
            fout << V[i] <<" ";
    }

} Rads;

int main() {

    fin >> N >> Rads.A >> Rads.B >> Rads.C;

    Rads.generate();
    Rads.thesort();
    Rads.print();
    return 0;
}