Cod sursa(job #1241040)

Utilizator ArkinyStoica Alex Arkiny Data 12 octombrie 2014 15:20:22
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include<fstream>
#include<deque>
#include<vector>
using namespace std;

#define byte 0x000000ff

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


deque<unsigned long > bucket[2][256];

void rsort(vector<unsigned long>& v) {
  unsigned long  i, j, k;
  for (i = 0; i < v.size(); ++i)
    bucket[0][v[i]&0x000000ff].push_back(v[i]);
  for (i = 0; i < 256; ++i) {
    while (!bucket[0][i].empty()) {
      unsigned long  &e = bucket[0][i].front();
      bucket[1][(e&0x0000ff00)>>8].push_back(e);
      bucket[0][i].pop_front();
    }
  }
  for (i = 0; i < 256; ++i) {
    while (!bucket[1][i].empty()) {
      unsigned long  &e = bucket[1][i].front();
      bucket[0][(e&0x00ff0000)>>16].push_back(e);
      bucket[1][i].pop_front();
    }
  }
  for (i = 0; i < 256; ++i) {
    while (!bucket[0][i].empty()) {
      unsigned long  &e = bucket[0][i].front();
      bucket[1][(e&0xff000000)>>8].push_back(e);
      bucket[0][i].pop_front();
    }
  }
  k = 0;
  for (i = 0; i < 256; ++i) {
    while (!bucket[1][i].empty()) {
        v[k++] = bucket[1][i].front();
		if((k-1)%10==0)
			 out<<v[k-1]<<" ";
      bucket[1][i].pop_front();
    }
  }
}


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

	in>>N>>A>>B>>C;
	vector<unsigned long> v;

	D=B;

	for(unsigned long  i=1;i<=N;i++)
	{
		v.push_back(D);

		D=(A * D + B) % C;
	}

	rsort(v);

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