Cod sursa(job #2076849)

Utilizator belgun_adrianBelgun Dimitri Adrian belgun_adrian Data 27 noiembrie 2017 11:26:24
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
// VS workaround
#define _CRT_SECURE_NO_WARNINGS

#include <cmath>
#include <cstdio>
#include <vector>
#include <list>
#include <iostream>
#include <algorithm>

#include <cstdio>

using namespace std;

void sort(std::vector<int>& v, int byte) {
	int mask = 0xFF;

	std::vector<std::vector<int>> buckets(256);

	int shift = byte * 8;

	for (int x : v) {
		int key = (x >> shift) & 0xFF;
		buckets[key].push_back(x);
	}

	int i = 0;

	for (const std::vector<int>& bucket : buckets) {
		for (int x : bucket) {
			v[i++] = x;
		}
	}
}


void print(const std::vector<int>& v) {
	for (int x : v)
		printf("%d ", x);
}

int main() {
	int n, a, b, c;

	FILE *f = fopen("radixsort.in", "r");
	fscanf(f, "%d %d %d %d", &n, &a, &b, &c);
	fclose(f);

	std::vector<int> v(n);
	v[0] = b;
	for (int i = 1; i < n; i++)
		v[i] = (1LL * a * v[i - 1] + b) % c;

	for (int i = 0; i < 4; i++)
		sort(v, i);

	f = fopen("radixsort.out", "w");
	for (int i = 0; i < n; i += 10)
		fprintf(f, "%d ", v[i]);
	fclose(f);


	return 0;
}