Cod sursa(job #2482616)

Utilizator AndreiStrAndrei Stroici AndreiStr Data 28 octombrie 2019 17:46:49
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
const int N = 10000001;
int n,X[N],Y[N],p[256],*x,*y,buket;
int64_t A,B,C;
int main()
{
    f>>n>>A>>B>>C;
    x=X;y=Y;
    x[1]=B;
    for(int i=2;i<=n;i++)
        x[i]=(A*x[i-1]+B)%C;
    for(int step = 0;step<4;step++)
    {
        int shift=8*step;
        for(int i=0;i<256;i++)
            p[i]=0;
        for(int i=1;i<=n;i++)
        {
            buket = (x[i]>>shift)&255;
            p[buket]++;
        }
        for(int i=1;i<256;i++)
            p[i]+=p[i-1];
        for(int i=n;i>=1;i--)
        {
            buket=(x[i]>>shift)&255;
            y[p[buket]]=x[i];
            p[buket]--;
        }
        int *aux=x;x=y;y=aux;
    }
    for(int i=1;i<=n;i+=10)
        g<<x[i]<<' ';
    return 0;
}