Cod sursa(job #1477264)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 25 august 2015 19:51:28
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int v[10000023];
int n,a,b,c;
void radixsort(int s,int e,int bit)
{
    if(bit==-1) return;
    if(s>=e) return;
    int mt=s;
    for(int i=s;i<=e;i++)
    {
        if((v[i]&(1<<bit))==0)
        {
            swap(v[i],v[mt]);
            mt++;
        }
    }
    radixsort(s,mt-1,bit-1);
    radixsort(mt,e,bit-1);
}
int main()
{
    freopen ("radixsort.in","r",stdin);
    freopen ("radixsort.out","w",stdout);
    scanf("%d%d%d%d",&n,&a,&b,&c);
    v[1]=b;
    int maxim=log2(b);
    for(int i=2;i<=n;i++)
    {
        v[i]=(1LL*a*v[i-1]+b)%c;
        if(maxim<log2(v[i])) maxim=log2(v[i]);
    }
    radixsort(1,n,maxim);
    for(int i=1;i<=n;i+=10)
    {
        printf("%d ",v[i]);
    }
}