Cod sursa(job #1117733)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 23 februarie 2014 19:22:18
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<fstream>
#include<queue>
#define maxn 10000007
using namespace std;
ifstream fi("radixsort.in");
ofstream fo("radixsort.out");

long long i,n,a,b,c;
long long maxv,p=1;
queue <int> q[10];
int v[maxn];

//Radix-Sort, (LSD) Least Significant Digit
void radix_sort(int p){
     int i,j=0;
     
     for(i=1;i<=n;i++) q[(v[i]/p)%10].push(v[i]);
     
     for(i=0;i<=9;i++)
       while(q[i].size()){
                          v[++j]=q[i].front();
                          q[i].pop();
                         }     
}

int main(){
    fi>>n>>a>>b>>c;
    
    v[1]=b; maxv=v[1];
    for(i=2;i<=n;i++){
                      v[i]=(a*v[i-1]+b)%c;
                      if(v[i]>maxv) maxv=v[i];
                     } 
    
    while(maxv){
                radix_sort(p);
                p*=10;
                maxv/=10;
               }
    
    for(i=1;i<=n;i+=10) fo<<v[i]<<" ";
    
    fi.close();
    fo.close();
    return 0;
}