Cod sursa(job #1916794)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 9 martie 2017 10:23:19
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
#include <vector>
#include <cstring>
#define Nmax 10000002
#define LL long long
using namespace std;

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

int n,a,b,c,v[Nmax],v2[Nmax],nr,BUK[301];

void _sort(int mask,int k)
{
    memset(BUK,0,sizeof(BUK));
    for (int i=1;i<=n;i++)
        BUK[(v[i]&mask)>>(8*k)]++;
    for (int i=0;i<=256;i++)
        BUK[i] += BUK[i-1];

    for (int i=n;i>=1;i--)
        v2[BUK[((v[i]&mask)>>(8*k))]--] = v[i];

    memcpy(v,v2,sizeof(v2));
}

int main()
{
    f>>n>>a>>b>>c;
    v[1] = b;
    for (int i=2;i<=n;i++)
        v[i] = ((LL)a*v[i-1] + b)%c;


    int mask = (1<<8)-1;

    for (int i=1;i<=4;i++)
    {
        _sort(mask,i-1);
        if (i<3)
            mask<<=8;
        else if (i==3)
            mask<<=7;
    }
    for (int i=1;i<=n;i+=10)
        g<<v[i]<<' ';

    return 0;
}