Cod sursa(job #1107669)

Utilizator andrei.sfrentSfrent Andrei andrei.sfrent Data 14 februarie 2014 03:31:18
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <cstdio>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int N, A, B, C;
int *v, *d;
unordered_map<int, int> counts;

void read() {
  scanf("%d%d%d%d", &N, &A, &B, &C);
}

void generate() {
  v = new int[N];
  v[0] = B;
  for(int i = 1; i < N; ++i) {
    v[i] = (A * v[i - 1] + B) % C;
  }
}

void count() {
  for(int i = 0; i < N; ++i) {
    counts[v[i]]++;
  }
}

void distinct() {
  d = new int[counts.size()];
  int i = 0;
  for(const auto& p : counts) {
    d[i++] = p.first;
  }
}

void sort_distinct() {
  sort(d, d + counts.size());
}

void sort_all() {
  int vi = 0;
  for(int i = 0; i < (int) counts.size(); ++i) {
    int x = d[i];
    int c = counts[x];
    while(c--) {
      v[vi++] = x;
    }
  }
}

void write() {
  for(int i = 0; i < N; i += 10) {
    printf("%d ", v[i]);
  }
  printf("\n");
}

int main(int argc, char *argv[]) {
  freopen("radixsort.in", "r", stdin);
  freopen("radixsort.out", "w", stdout);

  read();
  generate();
  count();
  distinct();
  sort_distinct();
  sort_all();
  write();

  return 0;
}