Cod sursa(job #1279293)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 30 noiembrie 2014 01:32:33
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <cstring>
#include <vector>
#define dim 10000002
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
vector <long long> v;
vector <long long> w;
int 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(((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=0;i<n;i++){
            w[f[(v[i]>>d[it])&mask]--]=v[i];
        }
        for(i=0;i<n;i++)
            v[i]=w[i];
    }
    for(i=n-1;i>=0;i-=10)
        fout<<v[i]<<" ";
    fin.close();fout.close();
    return 0;
}