Cod sursa(job #2013644)

Utilizator Vlad3108Tir Vlad Ioan Vlad3108 Data 21 august 2017 22:52:06
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <bits/stdc++.h>
using namespace std;
#define LMAX 10000005
int v[LMAX],aux[LMAX],Max=0;
inline void CountSort(int *v,int n,int byte){
    int count[2]={0};
    for(int i=1;i<=n;++i)
        ++count[(v[i]&byte)>0];
    count[1]+=count[0];
    for(int i=n;i;--i)
        aux[count[(v[i]&byte)>0]--]=v[i];
    for(int i=1;i<=n;++i)
        v[i]=aux[i];
}
inline void RadixSort(int *v,int n){
    for(int i=1;i<=min( (1<<30),Max );i<<=1){
        CountSort(v,n,i);
        if( i==(1<<30) ) break;
    }
}
int main(){
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    int n,a,b,c;
    scanf("%d %d %d %d",&n,&a,&b,&c);
    for(int i=1;i<=n;++i){
        v[i]=(a*v[i-1]+b)%c;
        if(v[i]>Max) Max=v[i];
    }
    RadixSort(v,n);
    for(int i=1;i<=n;i+=10)
        printf("%d ",v[i]);
    fclose(stdin);fclose(stdout);
    return 0;
}