Cod sursa(job #1474361)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 21 august 2015 20:27:49
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
using namespace std;

int x[10000010],n,a,b,c,temp[10000010];
int compute=255;

void read()
{
    int i;
    scanf("%d%d%d%d",&n,&a,&b,&c);
    x[1]=b;
    for(i=2;i<=n;i++)
        x[i]=(a*x[i-1]+b)%c;
}

void count_sort(int v[],int u[],int group)
{
    long long f[258]={0};
    int p,i;

    p=8*group;

    for(i=1;i<=n;i++) f[(v[i]<<p)&compute]++;

    for(i=1;i<256;i++) f[i]+=f[i-1];

    for(i=n;i>=1;i--)
    {
        int poz=(v[i]<<p)&compute;
        u[f[poz]]=v[i];
        f[poz]--;
    }
}

void radixsort()
{
    for(int i=0;i<4;i++)
        if(i%2==0) count_sort(x,temp,i);
        else count_sort(temp,x,i);
}

int main()
{
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);

    read();
    radixsort();

    for(int i=1;i<=n;i+=10) printf("%d ",x[i]);

    fclose(stdin);
    fclose(stdout);
    return 0;
}