Cod sursa(job #1111516)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 18 februarie 2014 22:04:15
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 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<std::list<unsigned> > v(256),v2(256);
	unsigned x=B;
	v[x&0xFF].push_back(x);

	for(unsigned i=2;i<=N;++i){
		x=(A*x+B)%C;
		v[x&0xFF].push_back(x);  //first byte
	}


	//second byte
	for(unsigned i=0;i<256;++i){
		for(auto it=v[i].begin();it!=v[i].end();++it)
			v2[(*it)&0xFF00].push_back(*it);
	}
	//third byte
	v=std::vector<std::list<unsigned> >(256);
	for(unsigned i=0;i<256;++i){
		for(auto it=v2[i].begin();it!=v2[i].end();++it)
			v[(*it)&0xFF0000].push_back(*it);
	}
	//fourth byte
	v2=std::vector<std::list<unsigned> >(256);
	for(unsigned i=0;i<256;++i){
		for(auto it=v[i].begin();it!=v[i].end();++it)
			v2[(*it)&0xFF000000].push_back(*it);
	}

	unsigned c=0;
	for(unsigned i=0;i<256;++i){
		for(auto it=v2[i].begin();it!=v2[i].end();++it){
			if(c%10==0) fout<<(*it)<<' ';
			++c;
		}

	}
	fout<<'\n';
}