Cod sursa(job #1119655)

Utilizator addy01adrian dumitrache addy01 Data 24 februarie 2014 19:13:53
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <cstring>
#define maxn 10000010
using namespace std;

ifstream in("radixsort.in");
ofstream out("radixsort.out");

int N,A,B,C;
int v[maxn],b[maxn];
int mask=(1<<8)-1;

void radix(int *A,int *B,int byte)
{
    int i,buket[mask+1],ind[mask+1];
    memset(buket,0,sizeof(buket));
    for(i=1;i<=N;i++)
        ++buket[(A[i]>>byte)&mask];
    ind[0]=1;
    for(i=1;i<=mask;i++)
        ind[i]=ind[i-1]+buket[i-1];
    for(i=1;i<=N;i++)
        B[ind[(A[i]>>byte)&mask]++]=A[i];

}


void radixsort()
{
radix(v,b,0);
radix(b,v,8);
radix(v,b,16);
radix(b,v,24);
}

int main()
{
    in>>N>>A>>B>>C;

    int i;
    v[1]=B;
    for(i=2;i<=N;i++)
    {
        v[i]=((long long)A*v[i-1]+B)%C;
    }
    radixsort();

    for(i=1;i<=N;i+=10)
        out<<v[i]<<" ";

    return 0;
}