Cod sursa(job #1279308)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 30 noiembrie 2014 02:01:09
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
vector <int> v;
vector <int> w;
long long n,i,a,b,c,f[256];
short d[]={0,8,16,24},it,mask;
int main(){
    fin>>n>>a>>b>>c;
    v.push_back(b);
    w.push_back(0);
    for(i=1;i<n;i++){
        v.push_back(((1LL*a*v[i-1]+b)%c));
        w.push_back(0);
    }
    for(it=0;it<4;it++){
        mask=0xff;
        memset(f,0,sizeof(f));
        for(i=0;i<n;i++)
            f[(v[i]>>d[it])&mask]++;
        for(i=1;i<=mask;i++)
            f[i]+=f[i-1];
        for(i=n-1;i>=0;i--){
            w[f[(v[i]>>d[it])&mask]--]=v[i];
        }
        for(i=0;i<n;i++)
            v[i]=w[i];
    }
    for(i=0;i<n;i+10)
        fout<<v[i]<<" ";
    fin.close();fout.close();
    return 0;
}