Cod sursa(job #1527555)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 18 noiembrie 2015 12:33:17
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<fstream>
#include<cstring>
#define DIM 10000005
using namespace std;
int n, i, a, b, c, maxim;
long long t, x;
int v[DIM], w[DIM], f[270];
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
int main(){
    fin>> n >> a >> b >> c;
    v[1] = b;
    for(i = 2; i <= n; i++){
        x = (a * 1LL * v[i - 1] % c + b) % c;
        v[i] = x;
        maxim = max(maxim, v[i]);
    }
    t = 1;
    while(t < maxim){
        memset(f, 0, sizeof(f));
        for(i = 1; i <= n; i++){
            f[ v[i] / t % 256]++;
        }
        for(i = 1; i < 256; i++){
            f[i] += f[i - 1];
        }
        for(i = n; i >= 1; i--){
            w[ f[v[i] / t % 256] ] = v[i];
            f[v[i] / t % 256]--;
        }
        for(i = 1; i <= n; i++){
            v[i] = w[i];
        }
        t *= 256LL;
    }
    for(i = 1; i <= n; i+= 10){
        fout<< v[i] <<" ";
    }
    return 0;
}