Cod sursa(job #2043702)

Utilizator juniorOvidiu Rosca junior Data 20 octombrie 2017 13:22:20
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
//#include <iostream>
#include <cstring>

using namespace std;

ifstream fin("radixsort.in");
//ifstream fin("grader_test7.in");
ofstream fout("radixsort.out");
int n, byte, v[10000001], w[10000001];

void repartizare (int a[], int b[]) {
  int d, c, cc[256], i, l[256], cif;
  memset (cc, 0, sizeof cc);
  for (i = 1; i <= n; i++) {
    c = a[i] >> (byte * 8) & 255; // cifra in baza 256
    cc[c]++; // contor pentru fiecare cifra
  }
  l[0] = 1;
  for (cif = 1; cif <= 255; cif++)
    l[cif] = l[cif - 1] + cc[cif - 1];
  for (i = 1; i <= n; i++) {
    c = a[i] >> (byte * 8) & 255; // cifra in baza 256
    d = l[c]++; // Destinatia urmatoare va fi mai mare cu 1.
    b[d] = a[i];
  }
}

int main() {
  int a, b, c, i;
  fin >> n >> a >> b >> c;
  v[1] = b;
  for (i = 2; i <= n; i++)
    v[i] = (((long long)a * v[i-1]) % c + b) % c;
  for (byte = 0; byte <= 3; byte++)
    if (byte % 2 == 0)
      repartizare(v, w);
    else
      repartizare(w, v);
  for (i = 1; i <= n; i += 10)
    fout << v[i] << ' '; // se cere sa afisam elemente din 10 in 10
}