Cod sursa(job #1681908)

Utilizator gabib97Gabriel Boroghina gabib97 Data 9 aprilie 2016 20:08:03
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <stdio.h>
#include <algorithm>
#define h 100000
using namespace std;
int n,i,b[10000001],c[100010],k,x,y,z,a[10000001],t;
long long aux;
char r[20000001];
void in(int n)
{
    int k,aux;
    long long inv=1;
    aux=n;
    while (aux>0)
    {
        k=aux%10;
        aux/=10;
        inv=inv*10+k;
    }
    while (inv>9)
    {
        k=inv%10;
        inv/=10;
        r[++t]=(char)(k+'0');
    }
    r[++t]=' ';
}
int main()
{
    ifstream fin ("radixsort.in");
    freopen ("radixsort.out","w",stdout);
    fin>>n>>x>>y>>z;
    a[1]=y; t=-1;
    for (i=1;i<=n;i++)
    {
        aux=(x*(long long)a[i-1])%z;
        aux=(aux+y)%z;
        a[i]=aux;
    }
    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<=h;i++) c[i]=0;
    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[b[i]/h]--;
    }
    for (i=1;i<=n;i++)
        if (i%10==1) in(a[i]);
    fwrite(r,t,sizeof(char),stdout);
    return 0;
}