Cod sursa(job #1435517)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 13 mai 2015 17:58:08
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <cstring>
#define DIM 10000100
using namespace std;

FILE *fin = fopen("radixsort.in" ,"r");
FILE *fout= fopen("radixsort.out","w");

int N, Sum[(1<<16)], V[DIM], W[DIM], A, B, C;

void SetUp(){
    fscanf(fin, "%d %d %d %d ", &N, &A, &B, &C);
    V[1] = B;
    for(int i = 1; i <= N; i ++)
        V[i] = (A * 1LL * V[i-1] + B) % C;
    return;
}

inline int cif(int val, int base, int exp){
    return ((val >> base) & ((1 << exp) - 1));
}

void Radix(int A[], int B[], int Sum[], int N, int base){
    for(int t = 0; t <= 32; t += base){
        for(int i = 0; i < (1<<base); i ++)
            Sum[i] = 0;
        for(int i = 1; i <= N; i ++)
            Sum[cif(A[i], t, base)] ++;
        for(int i = 1; i < (1<<base); i ++)
            Sum[i] += Sum[i-1];
        for(int i = N; i >= 1; i --)
            B[Sum[cif(A[i], t, base)]--] = A[i];
        for(int i = 1; i <= N; i ++)
            A[i] = B[i];
    }
    return;
}

void Finish(){
    for(int i = 1; i <= N; i += 10)
        fprintf(fout, "%d ", V[i]);
    return;
}

int main(){
    SetUp();
    Radix(V, W, Sum, N, 16);
    Finish();
    return 0;
}