Cod sursa(job #1180953)

Utilizator misinoonisim necula misino Data 1 mai 2014 15:08:38
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<fstream>
#include<cstring>

#define N 10000010

using namespace std;

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

int n,a,b,c,i,ce,v[N],pas,nr[500],v2[N];

int main()
{
    f >> n >> a >> b >> c;

    v[1] = b;

    for(i = 1 ; i <= n ; ++ i)
        v[i] = (1LL * v[i - 1] * a + b) % c;


    ///radix sort

    for(pas = 0 ; pas <= 3 ; ++pas)
    {
        for(i = 1 ; i <= n ; ++ i)
        {
            ++ nr [ (v[i] >> (pas * 8) ) & 255 ];
        }

        for(i = 1 ; i <= 255 ; ++ i)
            nr[i] += nr[i - 1];

        for(i = n ; i ; -- i)
        {
            ce = (v[i] >> (pas * 8) ) & 255 ;

            v2[ nr [ce] ] = v[i];

            -- nr[ce];
        }

        memcpy(v,v2,sizeof(v2));
        memset(nr,0,sizeof(nr));
    }

    for(i = 1 ; i <= n ; i += 10)
        g << v[i] << ' ';

    return 0;
}