Cod sursa(job #2757176)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 4 iunie 2021 11:46:14
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
#include <vector>
#include <memory.h>
 
using namespace std;
vector<int> v, aux;
 
const int MASK = 255;
int bucketFrequency[MASK + 1];
 
void radix(int N, int step) {
  memset(bucketFrequency, 0, sizeof(bucketFrequency));
  for (int i = 1; i <= N; ++i)
    ++bucketFrequency[(v[i] >> (8 * step)) & MASK];
  for (int i = 1; i <= MASK; ++i)
    bucketFrequency[i] += bucketFrequency[i - 1];
  for (int i = N; i >= 1; --i)
    aux[bucketFrequency[(v[i] >> (8 * step)) & MASK]--] = v[i];
  swap(aux, v);
}
 
 
int main()
{
  freopen("radixsort.in", "r", stdin);
  freopen("radixsort.out", "w", stdout);
 
  int N, A, B, C;
  scanf("%d%d%d%d", &N, &A, &B, &C);
  v.resize(N + 1);
  aux.resize(N + 1);
 
  v[1] = B;
  for (int i = 2; i <= N; ++i)
    v[i] = ( ((long long)A) * ((long long)v[i-1]) + ((long long)B) ) % C;
 
  for (int i = 0; i < 4; ++i)
    radix(N, i);
 
  for (int i = 1; i <= N; i += 10)
    printf("%d ", v[i]);
  printf("\n");
 
  return 0;
}