Cod sursa(job #1501126)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 13 octombrie 2015 00:03:51
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <queue>

using namespace std;

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

const int NMAX = 10000001;

int N; int A; int B; int C;

int v[NMAX];

int bucket[4][NMAX];


const int byte = (1 << 8) - 1;

queue<int> Q[byte + 1];
queue<int> Qnew[byte + 1];


void read() {

	fin >> N >> A >> B >> C;

	v[1] = B;
	//C < 2 ^ 31
	for(int i = 2 ; i <= N; ++i)
		v[i] = (A * v[i - 1] + B) % C;
}

void radix_sort() {


	for(int i = 1; i <= N; ++i)
		Q[ v[i] & byte ].push(v[i]);

	int mask = byte;

	for(int k = 0 ; k < 3; ++k)  {

		mask = mask << 8 ;

		if(k % 2 == 0) {

			for(int i = 0; i < byte + 1; ++i)
				while( Q[i].empty() == false ) {

					int x = Q[i].front();
					Q[i].pop();

					Qnew[x & mask].push(x);

				}
		} else {

			for(int i = 0; i < byte + 1; ++i)
				while( Qnew[i].empty() == false ) {

					int x = Qnew[i].front();
					Qnew[i].pop();

					Q[x & mask].push(x);

				}

		}
	}
	
}

int main() {


	read();

	radix_sort();

	int cnt = 0;

	for(int i = 0 ; i < byte + 1; ++i)
		while(Qnew[i].empty() == false) {
			
			cnt++;
			if(cnt % 10 == 1)
				fout << Qnew[i].front() << " ";
			Qnew[i].pop();

		}

	return 0;
}