Cod sursa(job #1226360)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 5 septembrie 2014 12:05:34
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <sstream>
#include <fstream>
using namespace std;
#define MAX 10000010
#define DIG 256
ifstream f("radixsort.in");
ofstream g("radixsort.out");

int N, A, B, C, K;
unsigned int X[2][MAX], R[MAX], Count[2][DIG], Start[2][DIG], Used[DIG];
stringstream ss;

void RadixSort() {
	int S = 1, D = 0, ps, pd;
	unsigned int Z = 0xFF, p = 0;
	for (int i = 1; i <= N; i++) {
		X[1][i] = ((long long)X[1][i-1] * A + B) % C;
		R[i] = X[1][i] & Z;
		Count[0][R[i]]++;
	}
	for (int i = 1; i < DIG; i++) {
		Start[0][i] = Start[0][i-1] + Count[0][i-1];
	}
	for (int i = 1; i <= N; i++) {
		X[0][Start[0][R[i]] + Used[R[i]]] = X[1][i];
		Used[R[i]]++;
	}
	for (int q = 1; q <= 4; q++) {
		S ^= 1;
		D ^= 1;
		memset(Count[D], 0, sizeof(Count[D]));
		memset(Start[D], 0, sizeof(Start[D]));
		memset(Used, 0, sizeof(Used));
		for (int j = 0; j < DIG; j++) {
			for (int k = 0; k < Count[S][j]; k++) {
				ps = Start[S][j] + k;
				A = X[S][ps];
				B = A >> p;
				if (B > 0) {
					R[ps] = B & Z;
					Count[D][R[ps]]++;
				} else {
					R[ps] = -1;
					if (K % 10 == 0) {
						ss << A << " ";
					}
					K++;
				}
			}
		}
		for (int i = 1; i < DIG; i++) {
			Start[D][i] = Start[D][i-1] + Count[D][i-1];
		}
		for (int j = 0; j < DIG; j++) {
			for (int k = 0; k < Count[S][j]; k++) {
				ps = Start[S][j] + k;
				if (R[ps] == -1) continue;
				X[D][Start[D][R[ps]] + Used[R[ps]]] = X[S][ps];
				Used[R[ps]]++;
			}
		}
		p += 8;
	}
	for (int j = 0; j < DIG; j++) {
			for (int k = 0; k < Count[D][j]; k++) {
				pd = Start[D][j] + k;
				if (K % 10 == 0) {
					ss << X[D][pd] << " ";
				}
				K++;
			}
		}
}

int main(){

    f >> N >> A >> B >> C;
    RadixSort();
	g << ss.str();

    return 0;
}