Cod sursa(job #1332021)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 1 februarie 2015 15:44:45
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <fstream>
#include <cstring>

#define Nmax 10000100
#define Bmax (1 << 8)
#define Byte(x, step) ((x >> step) & ((1 << 8) - 1))

using namespace std;

int N, A, B, C, V[Nmax], Tmp[Nmax], Count[Bmax], Index[Bmax];

void RadixSort() {

    int i, step;

    for(step = 0; step < 32; step += 8) {

        if(step != 0)
            memset(Count, 0, sizeof(Count));

        for(i = 1; i <= N; i++) {
            Tmp[i] = V[i];
            Count[Byte(V[i], step)]++;
        }

        Index[0] = 1;
        for(i = 1; i < Bmax; i++)
            Index[i] = Index[i - 1] + Count[i - 1];

        for(i = 1; i <= N; i++)
            V[Index[Byte(Tmp[i], step)]++] = Tmp[i];
    }

}
void Solve() {

    V[1] = B;

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

    RadixSort();

}
void Read() {

    ifstream in("radixsort.in");
    in >> N >> A >> B >> C;
    in.close();
}
void Write() {

    ofstream out("radixsort.out");

    for(int i = 1; i <= N; i += 10)
        out << V[i] << ' ';
    out << '\n';

    out.close();

}
int main() {

    Read();
    Solve();
    Write();

    return 0;

}