Cod sursa(job #2138895)

Utilizator inquisitorAnders inquisitor Data 21 februarie 2018 22:46:21
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fi("radixsort.in");
ofstream fo("radixsort.out");

#define BUFMAX 11000000
int bufcnt = BUFMAX; char buf[BUFMAX];
inline void write(uint 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
#define MASK 0xff
uint v[MAX], w[MAX]; int x[MASK + 1];

inline void radix(int n, uint v[], uint w[], int bit) {
  memset(x, 0, sizeof x);
  for (int i = 0; i < n; ++i) ++x[v[i] >> bit & MASK];
  for (int i = MASK; i > 0; --i) x[i] = x[i - 1]; x[0] = -1;
  for (int i = 1; i <= MASK; ++i) x[i] += x[i - 1];
  for (int i = 0; i < n; ++i) w[++x[v[i] >> bit & MASK]] = v[i];
}

int main() {
  int n; unsigned long long a; uint b, c; fi >> n >> a >> b >> c;

  v[0] = b;

  for(int i = 1; i != n; i++)
  {
      long long j = 1LL * v[i-1] * a + b;

      v[i] = j < c ? j : j - j / c * c;
  }


  radix(n, v, w, 0);
  radix(n, w, v, 8);
  radix(n, v, w, 16);
  radix(n, w, v, 24);
  for (int i = n - 1 - (n - 1) % 10; i >= 0; i -= 10) write(v[i]); flush();
}