Cod sursa(job #2829359)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 8 ianuarie 2022 15:51:57
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>

#include <vector>



inline void countsort(const std::vector<unsigned> &from, std::vector<unsigned> &to, unsigned byte){

	unsigned k[256],kc[256];

	kc[0]=0;

	for(unsigned i=0;i<256;++i){ k[i]=0; }

	for(unsigned i=0;i<from.size();++i) k[(from[i]>>(8*byte))&0xFF]++;

	for(unsigned i=1;i<256;++i) kc[i]=kc[i-1]+k[i-1];



	for(unsigned i=0;i<from.size();++i) to[kc[(from[i]>>(8*byte))&0xFF]++]=from[i];

}





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> a(N),b(N);



	a[0]=B;

	for(unsigned i=1;i<N;++i){

		a[i]=(1LL*A*a[i-1]+B)%C;

	}



	countsort(a,b,0);

	countsort(b,a,1);

	countsort(a,b,2);

	countsort(b,a,3);



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



	fout<<'\n';

}