Cod sursa(job #1164287)

Utilizator SRaduRadu Szasz SRadu Data 1 aprilie 2014 23:19:29
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>

using namespace std;

const int MAX = 10000050;

int N, A, B, C;
int V[MAX], Aux[MAX];

void Sort(int L, int R, int bit) {
    if(L >= R || bit == -1) return;
    int zero = 0;
    for(int i = L, start = L, stop = R; i <= R; i++)
        if(V[i] & (1 << bit)) {
            Aux[stop--] = V[i];
        } else {
            Aux[start++] = V[i];
            zero++;
        }
    for(int i = L; i <= R; i++)
        V[i] = Aux[i];
    Sort(L, L + zero - 1, bit - 1);
    Sort(L + zero, R, bit - 1);
}

int main() {
    ifstream in("radixsort.in");
    in >> N >> A >> B >> C;
    in.close();

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

    Sort(1, N, 30);

    ofstream out("radixsort.out");
    for(int i = 1; i <= N; i += 10)
        out << V[i] << " ";
    out.close();
}