Cod sursa(job #2672538)

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

using namespace std;

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

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

int main()
{
    f>>n>>A>>B>>C;

    v[1]=B;
    maxim=v[1];
    for(i=2;i<=n;i++)
    {
        v[i]=(A*1LL*v[i-1]+B)%C;
        maxim=max(maxim,v[i]);
    }

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

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

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

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

            new_v[d[bucket]]=v[j];
            d[bucket]--;
        }

        for(j=1;j<=n;j++)v[j]=new_v[j];
        for(j=0;j<=256;j++)d[j]=0;

        p+=8;
    }

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