Cod sursa(job #1099199)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 5 februarie 2014 17:14:09
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <iostream>
#include <cstring>
#include <algorithm>
#define Nmax 10100100
#define Bmax (1 << 8)
#define Byte(x) ((x >> Step) & (Bmax - 1))
using namespace std;

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

void RadixSort(int Left, int Right, int Step) {

    int i, Size[Bmax], Index[Bmax];

    if(!Step || Left >= Right)
        return;

    memset(Size, 0, sizeof(Size));

    for(i = Left; i <= Right; i++) {
        Tmp[i] = V[i];
        Size[Byte(V[i])]++;
        }

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

    for(i = Left; i <= Right; i++)
        V[Index[Byte(Tmp[i])]++] = Tmp[i];

    RadixSort(Left, Index[0] - 1, Step - 8);
    for(i = 1; i < Bmax; i++)
        RadixSort(Index[i-1], Index[i] - 1, Step - 8);

}
void Solve() {

    int i;

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

    RadixSort(1, N, 24);

}
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;

}