Cod sursa(job #2829402)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 8 ianuarie 2022 16:21:07
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>

unsigned tablou1[10*1000*1000];
unsigned tablou2[10*1000*1000];

inline void countsort(unsigned n, unsigned from[], 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<n;++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<n;++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 -- tablou1
	// b -- tablou2

	tablou1[0]=B;

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

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

	}

	countsort(N, tablou1,tablou2,0);
	countsort(N, tablou2,tablou1,1);
	countsort(N, tablou1,tablou2,2);
	countsort(N, tablou2,tablou1,3);

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

	fout<<'\n';

}