Cod sursa(job #2911121)

Utilizator proflaurianPanaete Adrian proflaurian Data 27 iunie 2022 10:04:28
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
const int N = 10000001;
int n,poz[256];
unsigned a,b,c,V[N],W[N],*v,*w;

inline unsigned func(unsigned x)
{
    x=1LL*a*x%c;
    x=(x+b)%c;
    return x;
}
inline unsigned rot(unsigned x)
{
    unsigned pref = x>>8;
    unsigned suff = x&255;
    unsigned ret = (suff<<24)|pref;
    return ret;
}

int main()
{
    f>>n>>a>>b>>c;
    int x=b,k=0;
    v=V;w=W;
    /// se generaza sirul initial
    for(int i=1;i<=n;i++)
    {
        v[++k]=x;
        x=func(x);
    }

    for(int t=0;t<4;t++)/// de 4 ori
    {
        /// se costruieste sirul contoarelor pentru cele 256 prefixe

        for(int i=1;i<=n;i++)
            poz[v[i]&255]++;
        /// se realizeaza sirul sumelor partiale pentru contoare
        for(int i=1;i<256;i++)
            poz[i]+=poz[i-1];
        /// se aseaza pe w sirul pe cele 255 buchete
        for(int i=n;i>=1;i--)
        {
            int buchet=v[i]&255;
            w[poz[buchet]]=rot(v[i]);
            poz[buchet]--;
            /// pe noul sir valoare se pune cu ultimul octet deja mutat in fata
        }
        swap(v,w);
        /// se resetaza contoarele la 0 pentru urmatoarea parcurgere
        for(int i=0;i<256;i++)
            poz[i]=0;
    }
    for(int i=1;i<=n;i+=10)
        g<<v[i]<<' ';
    return 0;
}