Cod sursa(job #1192721)

Utilizator misinozzz zzz misino Data 29 mai 2014 16:56:47
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream>
#include<cstring>

#define N 10000010

using namespace std;

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

int n,a,b,c,v[N],v2[N],nr[300],pas,buchet,i;

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

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

    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)
        {
            buchet = (v[i] >> pas * 8) & 255;

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

            -- nr[buchet];
        }

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

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

    g << '\n';

    return 0;
}