Cod sursa(job #1697869)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 3 mai 2016 01:29:14
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <fstream>
#include <vector>

using namespace std;

int n, a, b, c;
int v[10000050];

void CountingSort(int bit) {
   vector<int> cnt[256];

   for(int i = 1; i <= n; i++)
      cnt[(v[i] >> bit) & 255].push_back(v[i]);
   for(int i = 0, n = 0; i < 256; i++)
      for(auto x : cnt[i])
         v[++n] = x;
}

void RadixSort() {
   for(int i = 0; i < 32; i += 8)
      CountingSort(i);
}

int main() {
   ifstream f("radixsort.in");
   ofstream g("radixsort.out");

   f >> n >> a >> b >> c;

   v[1] = b;
   for(int i = 2; i <= n; i++)
      v[i] = (a * v[i - 1] + b) % c;

   RadixSort();

   for(int i = 1; i <= n; i += 10)
      g << v[i] << ' ';

   return 0;
}