Cod sursa(job #1989928)

Utilizator rebecca0312Andrei Rebecca rebecca0312 Data 9 iunie 2017 17:12:51
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<cstdio>
using namespace std;
const int NMAX=10000005;
int v[NMAX],aux[NMAX];
int f[15],n;
bool sortare(long long p){
    bool ok=0;
    for(int i=0;i<=10;i++)
        f[i]=0;
    for(int i=1;i<=n;i++)
        f[v[i]/p%10+1]++;
    for(int i=1;i<=10;i++)
        f[i]+=f[i-1];
    if(f[10]-f[1]>0)
        ok=1;
    for(int i=1;i<=n;i++){
        aux[f[v[i]/p%10]+1]=v[i];
        f[v[i]/p%10]++;
    }
    for(int i=1;i<=n;i++)
        v[i]=aux[i];
    return ok;
}
void radixsort(long long p){
    bool ok=sortare(p);
    if(!ok)
        return ;
    p*=10;
    radixsort(p);
}
int main(){
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    int a,b,c;
    scanf("%d%d%d%d", &n, &a, &b, &c);
    v[1]=b;
    for(int i=2;i<=n;i++)
        v[i]=(a*v[i-1]+b)%c;
    radixsort(1);
    for(int i=1;i<=n;i+=10)
        printf("%lld ", v[i]);
    return 0;
}