Cod sursa(job #2356645)

Utilizator NoemikulcsarKulcsar Noemi Noemikulcsar Data 26 februarie 2019 20:30:51
Problema Radix Sort Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f ("radixsort.in");
ofstream g ("radixsort.out");
const int nmax=1e7+5;
int base,n,a,b,c,v[nmax],k[nmax],p[257];
inline int rest(int k)
{
    return (k>>(8*base))&255;
}
void generare()
{
    f>>n>>a>>b>>c;
    v[1]=b;
    for(int i=2;i<=n;++i) v[i]=(1ll*a*v[i-1]+b)%c;
}
int main()
{
    generare();
    while(base<4)
    {
        for(int i=0;i<=255;++i) p[i]=0;
        for(int i=1;i<=n;++i) ++p[rest(v[i])];
        for(int i=1;i<=255;++i) p[i]+=p[i-1];
        for(int i=n;i>=1;--i) k[p[rest(v[i])]--]=v[i];
        for(int i=1;i<=n;++i) v[i]=k[i];
        ++base;
    }
    for(int i=1;i<=n;i+=10) g<<v[i]<<' ';
    return 0;
}