Cod sursa(job #1229619)

Utilizator mika17Mihai Alex Ionescu mika17 Data 17 septembrie 2014 20:19:30
Problema Radix Sort Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.37 kb
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>

void radixSort(int *v, int N) {

	int bytes[256];
	
	int i, j;
	int *v_tmp = malloc(N *sizeof(int));
	
	for(i = 0; i < sizeof(int);i ++) {

		memset(bytes,0,sizeof(bytes));
		for(j=0;j < N;j++) {
			bytes[(v[j] >> (8*i)) & 0xFF] ++;
		}
		
		for(j=1;j<256;j++) {
			bytes[j] += bytes[j - 1];
		}
		
		memcpy(v_tmp, v, N*sizeof(int));
		
		for(j=N-1;j>=0;j--) {
			v[--bytes[(v_tmp[j] >> (8*i)) & 0xFF]] = v_tmp[j];
		}
	}
	free(v_tmp);
} 

int main(void) {
	
	assert(freopen("radixsort.in","r",stdin) != NULL);
	assert(freopen("radixsort.out","w",stdout) != NULL);
	
	int N,A,B,C;
	assert(scanf("%d%d%d%d",&N,&A,&B,&C) == 4);
	
	int * v = malloc(N * sizeof(int));
	
	v[0] = B;
	int i;
	for(i=1;i<N;i++) {
		v[i] = (1ll* A * v[i - 1] + B) % C;
	}
	
	radixSort(v,N);
	
	// for(i=0;i<N;i+=10) {
		// printf("%d ",v[i]);
	// }
	
	#define MAX_SIZE (100000)
	#define NUM_SIZE (10)
	char buf[MAX_SIZE + 1], tmp[NUM_SIZE + 1];
	int pos = 0;
	
	for(i=0;i<N;i+=10) {
	
		memset(tmp,'\0',sizeof tmp);
		sprintf(tmp,"%d",v[i]);
		if (pos + strlen(tmp) + 1 > MAX_SIZE) {
			fwrite(buf, 1, pos, stdout);
			memset(buf,'\0',sizeof buf);
			pos = 0;
		}
		strcat(buf + pos, tmp);
		pos += strlen(tmp);
		strcat(buf + pos, " ");
		pos += 1;
	}

	fwrite(buf, 1, pos, stdout);
	memset(buf,'\0',sizeof buf);
	pos = 0;
	
	free(v);

	return 0;
}