Cod sursa(job #1159148)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 29 martie 2014 13:04:26
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <cstdio>
#include <queue>
using namespace std;
const int MAXN=10000005;
int n,a,b,c;
unsigned int v[MAXN];

queue<int> buckets[256];
void radix_sort()
{
	int i,j,k;
	unsigned int mask=(1<<8)-1;
	for (k=1; k<=4; ++k)
	{
        for (i=1; i<=n; ++i)
			buckets[v[i]&mask].push(v[i]);
		i=0;
		for (j=0; j<256; ++j)
		{
			while (!buckets[j].empty())
			{
				int x=buckets[j].front();
				buckets[j].pop();
				v[++i]=x;
			}
		}
		mask<<=8;
	}
}
int main()
{
	FILE* fin = fopen("radixsort.in", "r");
	FILE* fout = fopen("radixsort.out", "w");
	fscanf(fin,"%d %d %d %d",&n, &a, &b, &c);
	v[1]=b;
	for (int i=2; i<=n; ++i)
		v[i]=(a*v[i-1]+b)%c;

	radix_sort();
	for (int i=1; i<=n; i+=10)
		fprintf(fout, "%d ",v[i]);
	fclose(fin);
	fclose(fout);
    return 0;
}