Cod sursa(job #1681841)

Utilizator gabib97Gabriel Boroghina gabib97 Data 9 aprilie 2016 19:15:58
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <algorithm>
#define h 100000
using namespace std;
int n,i,v[10000001],b[1000001],c[100001],k,x,y,z,a[1000001],t;
int main()
{
    ifstream fin ("radixsort.in");
    ofstream fout ("radixsort.out");
    fin>>n>>x>>y>>z;
    a[1]=y;
    for (i=1;i<=n;i++)
    {
        a[i]=(x*a[i-1]+y)%z;
        //if (i%10==1) a[++t]=v[i];
    }

    for (i=1;i<=n;i++) c[a[i]%h]++;   //bucket 1 - ultimele 5 cifre
    for (i=1;i<h;i++) c[i]+=c[i-1];
    for (i=n;i>=1;i--)
    {
        b[c[a[i]%h]]=a[i];
        c[a[i]%h]--;
    }

    for (i=1;i<=n;i++) c[b[i]/h]++;   //bucket 2 - primele 5 cifre
    for (i=1;i<h;i++) c[i]+=c[i-1];
    for (i=n;i>=1;i--)
    {
        a[c[b[i]/h]]=b[i];
        c[a[i]/h]--;
    }
    for (i=1;i<=n;i++)
        if (i%10==1) fout<<a[i]<<" ";
    return 0;
}