Cod sursa(job #1095230)

Utilizator marius135Dumitran Adrian Marius marius135 Data 30 ianuarie 2014 16:19:10
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>

using namespace std;
#define maxn 10000001

int N;
int aux[maxn];
long long v[maxn];

void radix( long long *v) {
	
	long long mod = (1<<8);
	int last_mod = 0;
	int count[256], sum[256];
	memset(count, 0, sizeof(count));
	
	for( int i = 1; i <= 4; ++i) {
		
		for( int j = 0; j < N; ++j) {
			int unde = ((v[j]&(mod-1)) >>last_mod);
			if( unde < 0 || unde >= 256)
				while(1);
			count[ unde ]++;
		}			
		sum[0] = 0;
		for( int i = 1; i < 256; ++i)
			sum[i] = sum[i-1] + count[i-1];
		
		for( int j = 0; j < N; ++j)
			aux[ sum[ (v[j]&(mod-1)) >> last_mod]++] = v[j];
		for( int j = 0; j < N; ++j)
			v[j] = aux[j];
		
		
		last_mod += 8;
		mod = (mod<<8);
	}
	
}

int main() {

	freopen("radixsort.in", "r", stdin);
	freopen("radixsort.out", "w" ,stdout);
	
	int a = 49, b = 42, c = 1000;

	N = 100000;

	scanf("%d %d %d %d", &N, &a, &b, &c);
	
	v[0] = b;
	for( int i = 1; i < N; ++i)
		v[i] = ((long long)a * v[i-1] + b) % c;
	
	//radix(v);
	sort(v, v+N);
	
	for( int i = 0; i < N; i+= 10)
		cout<<v[i]<<" ";
	
	return 0;
}