Cod sursa(job #1823425)

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

#define MAX_N 10000000
#define MASK 255

typedef struct {
  int v, next;
} list;

int N, buff, ptr, ss;
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;
}

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++) {
      for (pos = adj[i]; pos; pos = l[pos].next) {
        stack[ss++] = l[pos].v;
      }
      while (ss) {
        val[++ptr] = stack[--ss];
      }
      adj[i] = 0;
    }
  }

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