Cod sursa(job #1313551)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 10 ianuarie 2015 20:24:46
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAXN 10000001

struct node {
	int key;
	node* next;
};

node* V[MAXN];
node* Prim[256], *Last[256];
int N, A, B, C;

int main()
{
	freopen("radixsort.in", "r", stdin);
	freopen("radixsort.out", "w", stdout);

	scanf("%d %d %d %d", &N, &A, &B, &C);
	for (int i = 0; i <= N; ++i)
		V[i] = new node;
	V[0]->key = 0;
	for (int i = 1; i <= N; ++i)
		V[i]->key = (1LL * V[i-1]->key * A + B) % C;

	for (int pow = 0; pow <= 31; pow += 8) {
		for (int i = 0; i < 256; ++i)
			Prim[i] = Last[i] = NULL;
		for (int i = 1; i <= N; ++i) {
			V[i]->next = NULL;
			int Bucket = (V[i]->key >> pow) & 255;
			if (Prim[Bucket] == NULL)
				Prim[Bucket] = Last[Bucket] = V[i];
			else {
				Last[Bucket]->next = V[i];
				Last[Bucket] = V[i];
			}
		}

		int Nr = 0;
		for (int i = 0; i < 256; ++i)
			while (Prim[i] != NULL) {
				V[++Nr] = Prim[i];
				Prim[i] = Prim[i]->next;
			}
	}

	for (int i = 1; i <= N; i+=10)
		printf("%d ", V[i]->key);

	return 0;
}