Cod sursa(job #2057887)

Utilizator neth------ neth Data 4 noiembrie 2017 20:55:13
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize "O3"
ifstream fi("radixsort.in");
ofstream fo("radixsort.out");

#define BUFMAX 11000000
int bufcnt = BUFMAX; char buf[BUFMAX];
inline void write(int x) {
  buf[--bufcnt] = ' ';
  do buf[--bufcnt] = x % 10 + '0', x /= 10; while (x);
}
inline void flush() { fo.write(buf + bufcnt, BUFMAX - bufcnt - 1); }

#define MAX 10000000
int v[MAX];

#define BITS 5
#define MASK 0x1f
#define TINY 0x3f

inline void insertion(int lef, int rig) {
  for (int i = lef; i < rig; ++i) {
    int t, j; for (t = v[i], j = i - 1; j >= lef; --j)
      if (t < v[j]) v[j + 1] = v[j]; else break;
    v[j + 1] = t;
  }
}

void radix(int lef, int rig, int bit) {
  int x[MASK + 1], y[MASK + 1];
  memset(y, 0, sizeof y); y[0] = lef;
  for (int i = lef; i < rig; ++i) ++y[v[i] >> bit & MASK];
  for (int i = 1; i <= MASK; ++i) y[i] += y[i - 1];
  for (int i = 1; i <= MASK; ++i) x[i] = y[i - 1]; x[0] = lef;
  for (int i = 0; i <= MASK; ++i)
    for (int xi = x[i], yi = y[i]; xi < yi; ++xi) {
      int t = v[xi];
      for (int j = t >> bit & MASK; j != i; j = t >> bit & MASK) {
        //int xj = x[j]; for (; (v[xj] >> bit & MASK) == j; ++xj); x[j] = xj + 1;
        //int tmp = t; t = v[xj]; v[xj] = tmp;
        int tmp = t; t = v[x[j]]; v[x[j]++] = tmp;
      }
      v[xi] = t;
    }
  if (bit <= 0) return;
  for (int i = 1; i <= MASK; ++i) x[i] = y[i - 1]; x[0] = lef;
  for (int i = 0; i <= MASK; ++i)
    if (y[i] - x[i] < TINY) insertion(x[i], y[i]);
    else radix(x[i], y[i], bit - BITS);
}

int main() {
  int n, b, c; unsigned long long a; fi >> n >> a >> b >> c;
  v[0] = b; a %= c, b %= c;
  for (int i = 1; i < n; ++i) {
    unsigned long long t = a * v[i - 1] + b;
    int thi = t >> 32, tlo = t; int aux;
    asm("divl %4" : "=a"(aux), "=d"(v[i]) : "0"(tlo), "1"(thi), "r"(c));
  }
  radix(0, n, 31 - 31 % BITS);
  for (int i = n - 1 - (n - 1) % 10; i >= 0; i -= 10) write(v[i]); flush();
}