Cod sursa(job #2672533)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 14 noiembrie 2020 10:27:39
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

FILE *f = fopen("radixsort.in", "r");
FILE *g = fopen("radixsort.out", "w");

int n,A,B,C,maxim,bucket,i,k,p,pas,d[260],v[10000010],v_nou[10000010];

int main()
{
    fscanf(f, "%d%d%d%d", &n, &A, &B, &C);
    v[1]=B;
    maxim=v[1];
    for(i=2;i<=n;i++)
    {
        v[i]=(1LL*A*v[i-1]+B)%C;
        maxim=max(maxim,v[i]);
    }

    while(maxim)
    {
        maxim/=256;
        k++;
    }

    for(pas=1;pas<=k;pas++)
    {
        for(i=1;i<=n;i++)
        {
            bucket=(v[i]>>p);
            bucket=(bucket&255);
            d[bucket]++;
        }

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

        for(i=n;i>=1;i--)
        {
            bucket=(v[i]>>p);
            bucket=(bucket&255);

            v_nou[d[bucket]]=v[i];
            d[bucket]--;
        }

        for(i=1;i<=n;i++)v[i]=v_nou[i];
        for(i=0;i<=255;i++)d[i]=0;

        p+=8;
    }

    for(i=1;i<=n;i+=10)fprintf(g, "%d ", v[i]);
    return 0;
}