Cod sursa(job #2672653)

Utilizator DesertChuStefan Andrei DesertChu Data 14 noiembrie 2020 12:45:59
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;

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

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

int main()
{
    f>>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=i+10)g<<v[i]<<" ";
    return 0;
}