Cod sursa(job #1879930)

Utilizator ionut98Bejenariu Ionut Daniel ionut98 Data 15 februarie 2017 11:41:53
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream f("radixsort.in");
ofstream g("radixsort.out");
const int lg=1e7+14;
int cnt[270];
int aux[lg];
int v[lg];
void RadixSort(int n)
{
    for(int bucket=0;bucket<32;bucket+=8)
    {
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;++i)
          cnt[((v[i]>>bucket)&255)]+=1;
        memset(aux,0,sizeof(aux));
        for(int i=1;i<256;++i)
          cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;--i)
          aux[cnt[((v[i]>>bucket)&255)]--]=v[i];
        memcpy(v,aux,sizeof(aux));
    }
}
int main()
{
    int n,a,b,c;
    f>>n>>a>>b>>c;
    v[1]=b;
    for(int i=2;i<=n;++i)
    v[i]=(a*v[i-1]+b)%c;
    RadixSort(n);
    for(int i=1;i<=n;i+=10)
      g<<v[i]<<" ";
    return 0;
}