Cod sursa(job #2387146)

Utilizator DovlecelBostan Andrei Dovlecel Data 24 martie 2019 13:07:17
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>

using namespace std;
ifstream in("radixsort.in");
ofstream out("radixsort.out");
const int N=10000005;
const int L=255;
int n,a,b,c,v[N];

void citire()
{
    in>>n>>a>>b>>c;
    v[1]=b;
    for(int i=2;i<=n;i++)
        v[i]=(1LL*a*v[i-1]+1LL*b)%c;
}

int frecv[L+1];
void cntsort(int biti)
{
    for(int i=0;i<=L;i++)
        frecv[i]=0;
    for(int i=1;i<=n;i++)
        frecv[(v[i]>>biti)&L]++;
    for(int i=1;i<=L;i++)
        frecv[i]=frecv[i]+frecv[i-1];
    for(int i=L;i>0;i--)
        frecv[i]=frecv[i-1];
    frecv[0]=0;
    int aux[n+1];
    for(int i=1;i<=n;i++)
        aux[++frecv[(v[i]>>biti)&L]]=v[i];
    for(int i=1;i<=n;i++)
        v[i]=aux[i];
}
void radix()
{
    for(int i=0;i<=24;i=i+8)
        cntsort(i);
}

int main()
{
    ios::sync_with_stdio(false);
    citire();
    radix();
    /*for(int i=1;i<=n/2;i++)
        swap(v[i],v[n-i+1]);*/
    for(int i=1;i<=n;i=i+10)
        out<<v[i]<<' ';
    return 0;
}