Cod sursa(job #1823421)

Utilizator stoianmihailStoian Mihail stoianmihail Data 6 decembrie 2016 12:30:31
Problema Radix Sort Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>

#define MAX_N 10000000
#define MASK 255

typedef struct {
  int v, next;
} list;

int N, buff, ptr;
int adj[MASK + 1];
list l[MAX_N + 1];
int val[MAX_N + 1];
int stack[MAX_N + 1];

void add(int v, int put) {
  buff++;
  l[buff].v = put;
  l[buff].next = adj[v];
  adj[v] = buff;
}

void fill(int curr) {
  if (curr) {
    fill(l[curr].next);
    val[++ptr] = l[curr].v;
  }
}

int main(void) {
  int A, B, C, i, k, shl, pos;
  FILE *f = fopen("radixsort.in", "r");

  fscanf(f, "%d %d %d %d", &N, &A, &B, &C);
  fclose(f);

  val[1] = B;
  for (i = 2; i <= N; i++) {
    val[i] = ((long long)A * val[i - 1] + B) % C;
  }

  for (k = 0; k < 4; k++) {
    shl = k << 3;
    for (i = 1; i <= N; i++) {
      add((val[i] >> shl) & MASK, val[i]);
    }

    buff = ptr = 0;
    for (i = 0; i <= MASK; i++) {
      fill(adj[i]);
      adj[i] = 0;
    }
  }

  freopen("radixsort.out", "w", stdout);
  for (i = 1; i <= N; i += 10) {
    fprintf(stdout, "%d ", val[i]);
  }
  fclose(stdout);
  return 0;
}