Cod sursa(job #2055215)

Utilizator neth------ neth Data 2 noiembrie 2017 22:50:16
Problema Radix Sort Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
ifstream fi("radixsort.in");
ofstream fo("radixsort.out");

#define MAX 10000000
int v[MAX], w[MAX];

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

int main() {
  int n, a, b, c; fi >> n >> a >> b >> c;
  v[0] = b;
  for (int i = 1; i < n; i++) v[i] = (1LL * a * v[i - 1] + b) % c;
  radix(n, v, w, 0);
  radix(n, w, v, 8);
  radix(n, v, w, 16);
  radix(n, w, v, 24);
  for (int i = 0; i < n; i += 10) fo << v[i] << ' ';
}