Cod sursa(job #1956589)

Utilizator Liviu_Ionut_MoantaMoanta Ionut Liviu Liviu_Ionut_Moanta Data 6 aprilie 2017 21:01:10
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
using namespace std;
ifstream fin("radixsort.in");
ofstream fout("radixsort.out");
long long i,n,a,b,c,e,ok,x;
int f[15],s[15];
int v[10000003],w[10000003];
int main(){
    fin>>n>>a>>b>>c;
    v[1]=b;
    e=1;
    for(i=2;i<=n;i++){
        v[i]=(a*v[i-1]+b)%c;
        if(v[i]>e){
            e*=10;
        }
    }
    ok=1;
    while(ok<=e){
        for(i=0;i<=9;i++){
            f[i]=0;
        }
        for(i=1;i<=n;i++){
            x=(v[i]/ok)%10;
            f[x]++;
        }
        s[0]=f[0];
        for(i=1;i<=9;i++){
            s[i]=s[i-1]+f[i];
        }
        for(i=n;i>=1;i--){
            x=(v[i]/ok)%10;
            w[s[x]]=v[i];
            s[x]--;
        }
        for(i=1;i<=n;i++){
            v[i]=w[i];
        }
        ok*=10;
    }
    for(i=1;i<=n;i+=10){
        fout<<v[i]<<" ";
    }
    return 0;
}