Cod sursa(job #2902059)

Utilizator ctimburCristina T ctimbur Data 15 mai 2022 12:29:11
Problema Radix Sort Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>
 
unsigned unu[10*1000*1000];
unsigned doi[10*1000*1000];
 
inline void countsort(unsigned n, unsigned from[], unsigned to[], unsigned byte){
 
	unsigned k[256], a[256];
	a[0]=0;
	for (unsigned i=0;i<256;++i)
        k[i] = 0;
 
	for (unsigned i=0;i<n;++i)
        k[(from[i]>>(8*byte))&0xFF]++;
 
	for (unsigned i=1;i<256;++i)
        a[i] = a[i-1] + k[i-1];
 
	for (unsigned i=0;i<n;++i)
        to[a[(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 -- unu
	// b -- doi
 
	unu[0]=B;
 
	for(unsigned i=1;i<N;++i){
 
		unu[i]=(1LL*A*unu[i-1]+B)%C;
 
	}
 
	countsort(N, unu, doi,0);
	countsort(N, doi, unu,1);
	countsort(N, unu, doi,2);
	countsort(N, doi, unu,3);
 
	for(unsigned i=0;i<N;i+=10)	fout<<unu[i]<<' ';
 
	fout<<'\n';
 
}