Cod sursa(job #3154683)

Utilizator proflaurianPanaete Adrian proflaurian Data 5 octombrie 2023 16:59:46
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
const unsigned N= 10000010;
unsigned n,v[N],aux[N];
void generareSir()
{
    unsigned a,b,c;
    f>>n>>a>>b>>c;
    v[1]=b;
    for(unsigned i=2;i<=n;i++)
        v[i]=(1LL*a*v[i-1]%c+b)%c;;

}
void sorteaza()
{
    vector<unsigned> sz(300,0),start(300,0);
    /// calculez dimensiunea fiecarul "bucket"
    /// si mut pe un auxiliar valorile din sir
    for(unsigned i=1;i<=n;i++)
    {
        sz[v[i]&255]++;
        aux[i]=v[i];
    }

    /// calculez pozitia de star pentru fiecare buchet
    start[0]=1;
    for(unsigned i=1;i<256;i++)
        start[i]=start[i-1]+sz[i-1];

    ///
    for(unsigned i=1;i<=n;i++)
    {
        unsigned val=aux[i]; /// imi iau valoare
        unsigned sufix=val&255;/// imi determin in ce buchet unsignedra <ultimii 8 biti>
        unsigned prefix=val>>8;/// ceilalti 24 de biti
        unsigned poz=start[sufix];
        start[sufix]=start[sufix]+1; /// vad in ce pozitie am ajuns in buchet <si incrementez apoi>
        v[poz]=(sufix<<24)|prefix;/// pun la pozitia determinata valoarea rotita cu 8 pozitii
    }


}
void afisare()
{
    for(unsigned i=1;i<=n;i+=10,g<<' ')
        g<<v[i];
}
int main()
{
    generareSir();
    for(unsigned i=1;i<=4;i++)
        sorteaza();
    afisare();
    return 0;
}