Cod sursa(job #1959840)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 9 aprilie 2017 23:10:15
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define BucketSize 4
#define MaxN 10005
using namespace std;
 
FILE*IN,*OUT;

int N,Bucket[1<<BucketSize];
long long B,A,C,v[MaxN],aux[MaxN];
void Radix(long long *a,int Start,int End)
{
	for(int p=0;p<32;p+=BucketSize)
	{
		memset(Bucket,0,sizeof Bucket);

		for(int i=Start;i<=End;i++)
			Bucket[(a[i]>>p)&((1<<BucketSize)-1)]++;
		
		for(int i=1;i<1<<BucketSize;i++)
			Bucket[i]+=Bucket[i-1];
		
		for(int i=End;i>=Start;i--)
			aux[Bucket[(a[i]>>p)&((1<<BucketSize)-1)]--]=a[i];
		
		memcpy(v,aux,sizeof aux);
	}
}
int main()
{
    IN=fopen("radixsort.in","r");
    OUT=fopen("radixsort.out","w");

	fscanf(IN,"%d%d%d%d",&N,&A,&B,&C);
	v[1]=B%C;
	for(int i=1;i<=N;i++)
		v[i]=(A*v[i-1]+B)%C;
	Radix(v,1,N);
	for(int i=1;i<=N;i+=10)
		fprintf(OUT,"%d ",v[i]);
    return 0;
}