Cod sursa(job #1435500)

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

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

int N, Sum[(1<<16)+10], 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 * 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){
        memset(Sum, 0, sizeof(Sum));
        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;
}