Cod sursa(job #1240955)

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


ifstream in("radixsort.in");
ofstream out("radixsort.out");
unsigned long v[10000001];
vector<unsigned long> vec[2][0x000000ff+1];

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

	in>>N>>A>>B>>C;
	v[1]=B;
	  for(unsigned long i=2;i<=N;i++)
	  {
		 v[i]=(A*v[i-1]+B)%C;
	  }
  
	  for(int i=1;i<=N;i++)
		  vec[0][v[i]&0x000000ff].push_back(v[i]);

	 for(int i=0;i<0x000000ff;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<0x000000ff;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<0x000000ff;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();
		  }
	  int j=0;
	 for(int i=0;i<0x000000ff;i++)
		  while(vec[1][i].size())
		  {
			  unsigned long c=vec[1][i].at(vec[1][i].size()-1);
			  v[N-j]=c;
			  vec[1][i].pop_back();
			  j++;
		  }

	  for(int i=1;i<=N;i+=10)
		  out<<v[i]<<" ";

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