Cod sursa(job #1241015)

Utilizator ArkinyStoica Alex Arkiny Data 12 octombrie 2014 14:38:09
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<fstream>
#include<vector>
using namespace std;

#define byte 0x000000ff

ifstream in("radixsort.in");
ofstream out("radixsort.out");



vector<unsigned long> vec[2][byte+1];


int main()
{
	unsigned long N,A,B,C,D;

	in>>N>>A>>B>>C;
	D=B;
	  for(int i=0;i<N;i++)
	  {

		  vec[0][D&byte].push_back(D);
		  D=(A * D + B) % C;
	  }

	 for(int i=0;i<=byte;i++)
		  while(vec[0][i].size())
		  {
			  unsigned long c=vec[0][i].at(vec[0][i].size()-1);
			  vec[1][(c&0x0000ff00)>>8].push_back(c);
			  vec[0][i].pop_back();
		  }
	 for(int i=0;i<=byte;i++)
		  while(vec[1][i].size())
		  {
			   unsigned long c=vec[1][i].at(vec[1][i].size()-1);
			  vec[0][(c&0x00ff0000)>>16].push_back(c);
			  vec[1][i].pop_back();
		  }
	   for(int i=0;i<=byte;i++)
		  while(vec[0][i].size())
		  {
			   unsigned long c=vec[0][i].at(vec[0][i].size()-1);
			  vec[1][(c&0xff000000)>>24].push_back(c);
			  vec[0][i].pop_back();
		  }
	  unsigned long j=0;
	  unsigned long *v=new unsigned long[N+1];
	 for(int i=0;i<=byte;i++)
	 {
		  while(vec[1][i].size())
		  {
			  unsigned long c=vec[1][i].at(vec[1][i].size()-1);
			  vec[1][i].pop_back();
			  v[N-j]=c;
			  j++;
		  }
	 }

	 for(unsigned long j=1;j<=N;j+=10)
		 out<<v[j]<<" ";

	 delete[] v;


	in.close();
	out.close();
	return 0;
}