Cod sursa(job #1226241)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 4 septembrie 2014 22:01:59
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
using namespace std;

int N, A, B, C;
queue<int> Bucket[2][1000];
vector<int> Sol;

void RadixSort() {
	int S = 1, D = 0;
	long long X = 0;
	for (int i = 1; i <= N; i++) {
		X = (X * A + B) % C;
		Bucket[0][X % 1000].push(X); 		
	}
	int Y = 1;
	do {
		Y *= 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 / Y;
				if (B > 0) {
					Bucket[D][B % 1000].push(A);
				} else {
					Sol.push_back(A);
				}
			}
		}
	} while (Y < 1000000000LL);
}

int main(){
	int x;
	
	freopen("radixsort.in","r",stdin);
	freopen("radixsort.out","w",stdout);
    
    scanf("%d %d %d %d", &N, &A, &B, &C);
    RadixSort();
    for (int i = 0; i < N; i++) {
    	if (i % 10 == 0) {
    		printf("%d ", Sol[i]);
    	}
    }
    
    return 0;
}