Cod sursa(job #1250057)

Utilizator danielmaxim95FMI Maxim Daniel danielmaxim95 Data 27 octombrie 2014 19:38:37
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include<fstream>

using namespace std;

ifstream f ("radixsort.in");
ofstream g ("radixsort.out");

int v[10000005], pr[10000005];

int numarcifre(int x)
{
    int k=0;
    do
    {
        x>>=1;
        k++;
    }
    while(x);
    return k;
}

int main()
{
    int i,h,nc,m,n,a,b,c;

    f >> n >> a >> b >> c;

    m=0;
    v[0]=b;
    for(i=0 ;i<n; i++)
    {
        v[i]=(1LL*a*v[i-1]+b)%c;
        if(v[i]>m) m=v[i];
    }

    nc=numarcifre(m);

    for(h=0; h<nc; h+=8)
    {
        int g[256]={0};

        for (i=0; i<n; i++) //numararea elementelor fiecarei "galeti"
            g[(v[i]>>h)&255]++;

        for (i=1; i<=255; i++) //calcularea indicelui fiecarui element
            g[i]+=g[i-1];

        for (i=n-1; i>=0; i--) //salvarea numerelor provizoriu in vectorul pr
            pr[--g[(v[i]>>h)&255]]=v[i];

        for (i=0; i<n; i++) //reintroducerea elementelor in vectorul v
            v[i]=pr[i];
    }

    for(i=0; i<n; i+=10)
        g << v[i] << " ";

    return 0;
}