Cod sursa(job #1253375)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 1 noiembrie 2014 10:47:56
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#include <algorithm>
#include <queue>
#define BASE 10
using namespace std;
FILE *f=fopen("radixsort.in","r");
FILE *g=fopen("radixsort.out","w");
int n,a,b,c,put=1,maxim,nr;
bool ok;
int v[10000005];


void radix(int length){
	queue<int> bucket[BASE];
	int i;long long ma;

	// iterate through each radix until n>max
    for (int ma=1;maxim>=ma;ma*=BASE) {
		// sort list of numbers into buckets
		for (i=0; i<length; i++)
			bucket[(v[i]/ma)%BASE].push(v[i]);

		// merge buckets back to list
		for (int k=i=0; i<BASE;i++)
			while (!bucket[i].empty()) {v[k++]=bucket[i].front();
                                         bucket[i].pop();}
	}
}
int main()
{int i;
long long ll;
fscanf(f,"%d %d %d %d",&n,&a,&b,&c);
v[1]=b;
for (i=2;i<=n;i++) {ll=1LL*(1LL*a*(v[i-1])+b)%c;
                    v[i]=ll;
                    maxim=max(maxim,v[i]);}
radix(n);
for (i=1;i<=n;i+=10) fprintf(g,"%d ",v[i]);
return 0;
}