Cod sursa(job #2092082)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 20 decembrie 2017 22:10:02
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <fstream>
#include <vector>

using namespace std;

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

void R_Sort(int n, vector < int > &v, vector < int > &frecv, vector < int > &aux) {

  for (int bits = 0; bits < 31; bits += 8) {
      
    fill(frecv.begin(), frecv.end(), 0);
    for (int i = 1; i <= n; i ++) {
      frecv[(v[i] >> bits) & 255] ++;
    }

    for (int i = 1; i <= 255; i ++) {
      frecv[i] += frecv[i - 1];
    }

    fill(aux.begin(), aux.end(), 0);
    for (int i = n; i >= 1; i --) {
      aux[frecv[(v[i] >> bits) & 255] --] = v[i];
    }

    v = aux;
  }
}
    
int main() {

  int n, a, b, c;
  cin >> n >> a >> b >> c;

  vector < int > v(n + 1);
  v[1] = b;

  for (int i = 2; i <= n; i ++) {
    v[i] = (1ll * a * v[i - 1] + b) % c;
  }
  
  vector < int > frecv(256);
  vector < int > aux(n + 1);
  R_Sort(n, v, frecv, aux);

  for (int i = 1; i <= n; i += 10) {
    cout << v[i] << ' ';
  }
  cout << '\n';
}