Cod sursa(job #1107674)

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

using namespace std;

int N, A, B, C;
int *v;

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

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

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

void radix(int rank) {
  vector<int> b[256];
  for(int i = 0; i < N; ++i) {
    int x = v[i];
    b[(x >> (rank * 8)) & 0x000000FF].push_back(x);
  }

  int vi = 0;
  for(int i = 0; i < 256; ++i) {
    for(int x : b[i]) {
      v[vi++] = x;
    }
  }
}

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

  read();
  generate();

  for(int i = 0; i < 4; ++i) {
    radix(i);
  }

  write();

  return 0;
}