Cod sursa(job #1226247)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 4 septembrie 2014 22:20:19
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 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;
ifstream f("radixsort.in");
ofstream g("radixsort.out");

int N, A, B, C, K;
queue<int> Bucket[2][1000];
stringstream ss;

void RadixSort() {
	int S = 1, D = 0;
	long long X = 0;
	for (int i = 1; i <= N; i++) {
		X = (X * A + (long long)B) % C;
		Bucket[0][X % 1000].push(X); 		
	}
	X = 1;
	do {
		X *= 1000;
		S ^= 1;
		D ^= 1;
		for (int j = 0; j < 1000; j++) {
			while (!Bucket[S][j].empty()) {
				A = Bucket[S][j].front();
				Bucket[S][j].pop();
				B = A / X;
				if (B > 0) {
					Bucket[D][B % 1000].push(A);
				} else {
					if (K % 10 == 0) {
						ss << A << " ";
					}
					K++;
				}
			}
		}
	} while (X < 1000000000000LL);
}

int main(){

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

    return 0;
}