Cod sursa(job #1239589)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 9 octombrie 2014 12:46:58
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <vector>
#define DIM 10000011
#define G 4
#define biti 8
#define cif (v[i]>>(p*biti))&(num-1)
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
int n,A,B,C;
int fr[1<<biti];

vector<long long> v,w;

int main(void){
    register int i,j,p;

    f>>n>>A>>B>>C;
    v.push_back(0);
    v.push_back(B),w.push_back(0),w.push_back(0);
    for(i=2;i<=n;i++)
        v.push_back((A*v[i-1]+B)%C),w.push_back(0);

    int num=1<<biti;
    for(p=0;p<G;p++){
        for(i=0;i<num;i++) fr[i]=0;
        for(i=1;i<=n;i++) fr[cif]++;
        for(i=1;i<num;i++) fr[i]+=fr[i-1];
        for(i=n;i>0;i--) w[fr[cif]]=v[i],fr[cif]--;
        v.clear(),v.push_back(0);
        for(i=1;i<=n;i++) v.push_back(w[i]);

    }

    for(i=1;i<=n;i+=10) g<<v[i]<<" ";
    f.close();
    g.close();
    return 0;
}