Cod sursa(job #1155490)

Utilizator adireusadireus adireus Data 26 martie 2014 22:36:46
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int N, A, B, C;
int work[10000000];

void
readData ()
{
  ifstream in ("radixsort.in");

  in >> N >> A >> B >> C;
  int temp = B;

  work[0] = B;
  for (int i = 1; i < N; i++)
    {
      temp = (A * temp + B) % C;
      work[i] = temp;
    }
}

void
solve ()
{
  vector < int >buckets[256];
  int mask = 0x000000ff;
  for (int i = 0; i <= 3; i++)
    {
      int offset = 8 * i;
      for (int i = 0; i < N; i++)
	{
	  buckets[(work[i] & mask) >> offset].push_back (work[i]);
	}

      mask = mask << 8;
      int idx = 0;
      for (int i = 0; i <= 255; i++)
	{
	  for (vector<int>::iterator it = buckets[i].begin (); it != buckets[i].end (); it++)
	    {
	      work[idx++] = (*it);
	    }
	  buckets[i].clear ();
	}
    }
}

void
print ()
{
  ofstream of ("radixsort.out");
  for (int i = 0; i < N; i = i + 10)
    of << work[i] << ' ';

}

int
main ()
{
  readData ();
  solve ();
  print ();
  return 0;
}