Cod sursa(job #1905146)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 5 martie 2017 22:15:35
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.79 kb
#include <stdio.h>
 
#define MAX_N 10000000
#define BITS 8
#define MASK ((1 << BITS) - 1)
#define THRESHOLD 64
 
#define MAX_DIG 10
#define BUFF_SIZE (1 << 17)
 
int v[MAX_N];
 
char buff[BUFF_SIZE], dig[MAX_DIG];
int pos;
 
inline void fasterLLDivMod(unsigned long long x, unsigned y, unsigned &out_d, unsigned &out_m) {
    unsigned xh = (unsigned)(x >> 32), xl = (unsigned)x, d, m;
#ifdef __GNUC__
    asm(
        "divl %4; \n\t"
        : "=a" (d), "=d" (m)
        : "d" (xh), "a" (xl), "r" (y)
    );
#else
    __asm {
        mov edx, dword ptr[xh];
        mov eax, dword ptr[xl];
        div dword ptr[y];
        mov dword ptr[d], eax;
        mov dword ptr[m], edx;
    };
#endif
    out_d = d; out_m = m;
}
   
//x / y < 2^32 !
inline unsigned fasterLLMod(unsigned long long x, unsigned y) {
    unsigned dummy, r;
    fasterLLDivMod(x, y, dummy, r);
    return r;
}

inline void insertionSort(int lo, int hi) {
  for (int i = lo; i < hi; i++) {
    // insereaza v[i] in v[lo..i]
    int x = v[i];
    int j = i;
    while ((j > lo) && (v[j - 1] > x)) {
      v[j] = v[j - 1];
      j--;
    }
    v[j] = x;
  }
}
void radixSort(int lo, int hi, int bits) {
  int ptr[1 << BITS], end[1 << BITS] = { };
 
  for (int i = lo; i < hi; i++) {
    end[(v[i] >> bits) & MASK]++;
  }
  // deplasement
  ptr[0] = lo;
  end[0] += lo;
  for (int i = 1; i < (1 << BITS); i++) {
    ptr[i] = end[i - 1];
    end[i] += end[i - 1];
  }
  for (int i = 0; i < (1 << BITS); i++) {
    while (ptr[i] != end[i]) {
      int elem = v[ptr[i]];
      int bucket = (elem >> bits) & MASK;
      while (bucket != i) {
        int tmp = v[ptr[bucket]];
        v[ptr[bucket]++] = elem;
        elem = tmp;
        bucket = (elem >> bits) & MASK;
      }
      v[ptr[i]++] = elem;
    }
  }
  if (bits) {
    for (int i = 0; i < (1 << BITS); i++) {
      int size = end[i] - (i ? end[i - 1] : lo);
      if (size > THRESHOLD) {
        radixSort(end[i] - size, end[i], bits - BITS);
      } else if (size > 1) {
        insertionSort(end[i] - size, end[i]);
      }
    }
  }
}
inline void put(FILE *f, char c) {
  buff[pos++] = c;
 
  if (pos == BUFF_SIZE) {
    fwrite(buff, 1, BUFF_SIZE, f);
    pos = 0;
  }
}
inline void write(FILE *f, int x) {
  int nDig = 0;
 
  do {
    int q = x / 10;
    dig[nDig++] = x - (q << 1) - (q << 3) + '0';
    x = q;
  } while (x);
 
  while (nDig--) {
    put(f, dig[nDig]);
  }
}
int main(void) {
  FILE *f;
  int n;
  int a, b, c;
 
  f = fopen("radixsort.in", "r");
  fscanf(f, "%d%d%d%d", &n, &a, &b, &c);
  fclose(f);
 
  v[0] = b;
  for (int i = 1; i < n; i++) {
    v[i] = fasterLLMod(1ULL * v[i - 1] * a + b, c);
  }
 
  radixSort(0, n, 24);
 
  f = fopen("radixsort.out", "w");
  for (int i = 0; i < n; i += 10) {
    write(f, v[i]);
    put(f, ' ');
  }
  if (pos) {
    fwrite(buff, 1, pos, f);
  }
  fclose(f);
  return 0;
}