Cod sursa(job #2553606)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 22 februarie 2020 10:27:38
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>

using namespace std;

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

long long n,A,B,C,i,maxim,k,p,j,bucket,d[256],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*v[i-1]+B)%C;
        maxim=max(maxim,v[i]);
    }

    /// e ca si cand as face pe ultima cifra, doar ca nu e ultima cifra sunt puteri ale lui 2 (2^8)
    while(maxim)
    {
        k++;
        maxim/=256;
    }

    p=1;
    for(i=1;i<=k;i++) /// fac operatia de k ori
    {
        for(j=1;j<=n;j++)
        {
            /// in loc sa merg in functie de bucket-uri dupa ultima cifra, merg dupa bucket-uri in functie de configuratii de 8 biti => numarul e maxim 255 (1111 1111)
            bucket=v[j]/p;
            bucket=(bucket&255); /// e ca si cand fac number/p%p pentru a afla valoarea cifrei, respectiv bucket-ului pentru pozitia care ma intereseaza
                                 /// 255 = 1111 1111
            d[bucket]++;
        }

        /// vezi counting sort aici
        for(j=1;j<=255;j++)d[j]+=d[j-1];

        for(j=1;j<=n;j++)
        {
            /// din nou aflu bucket-ul respectiv
            bucket=v[j]/p;
            bucket=(bucket&255);

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

        /// dam update la vectorul v
        for(j=1;j<=n;j++)v[j]=new_v[j];

        /// golim bucket-urile
        for(j=0;j<=255;j++)d[j]=0;

        p=p*256;
    }

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