Cod sursa(job #1481099)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 3 septembrie 2015 20:15:52
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <cctype>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <vector>
#include <list>
#include <bitset>
#include <iomanip>
#define MAX 5000001LL
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define RADIX 8

using namespace std;

ifstream fin("radixsort.in");
ofstream fout("radixsort.out");

int n;
int v[10000000], aux[10000000];

void radixSort();
void countSort(int a[], int b[], int byte);
inline int getByte(int nr, int byte) { return (nr >> (byte * 8)) & 0xFF; };

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

	fin >> n >> a >> b >> c;

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

	radixSort();

	for (i = 0; i < n; i += 10)
		fout << v[i] << ' ';

	return 0;
}

void radixSort() { // 8 bits
	for (int i = 0; i < 4; ++i) {
		if (i % 2 == 0)
			countSort(v, aux, i);
		else
			countSort(aux, v, i);
	}
}

void countSort(int a[], int b[], int byte) {
	int i;
	int fr[1 << RADIX];
	int inc[1 << RADIX];

	memset(fr, 0, sizeof(fr));
	for (i = 0; i < n; ++i) // frecventa fiecarui byte
		++fr[getByte(a[i], byte)];

	inc[0] = 0;
	for (i = 1; i < (1 << RADIX); ++i) // pozitia finala a fiecarui byte
		inc[i] = inc[i - 1] + fr[i - 1];

	for (i = 0; i < n; ++i)
		b[inc[getByte(a[i], byte)]++] = a[i];
}