Cod sursa(job #1111542)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 18 februarie 2014 22:28:21
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <vector>
#include <list>

int main(){
	std::ifstream fin("radixsort.in");
	std::ofstream fout("radixsort.out");

	unsigned N,A,B,C;
	fin>>N>>A>>B>>C;

	std::vector<unsigned> num(N);
	std::vector<std::list<unsigned> > v(256);

	num[0]=B;
	for(unsigned i=1;i<N;++i){
		num[i]=(A*num[i-1]+B)%C;
	}

	unsigned c=0xFF;
	for(unsigned i=0;i<4;++i){
		for(unsigned k=0;k<N;++k)
			v[ (num[k]&c)>>(8*i) ].push_back(num[k]);

		unsigned k=0;
		for(unsigned j=0;j<256;++j){
			if(v[j].size())
				for(auto it=v[j].begin();it!=v[j].end();++it)
					num[k++]=*it;
		}

		c<<=8;
		for(unsigned j=0;j<256;++j) v[j].clear();
	}


	for(unsigned i=0;i<N;i+=10)	fout<<num[i]<<' ';

	fout<<'\n';
}