Cod sursa(job #2677812)

Utilizator Antonia_onisoruantonia onisoru Antonia_onisoru Data 27 noiembrie 2020 16:08:27
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <string.h>
#include <fstream>

using namespace std;

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

const int MAXN = 100;
const int MAX_BIT = 32;
const int BITS_STEP = 8;

const int BASE = ( 1 << BITS_STEP );
const int MASK = BASE - 1;

int v[ MAXN ], a[ MAXN ];
int freq[BASE];
int ind[BASE];

void radix_sort(int v2[], int aux[], int n, int bits){
  if( bits == MAX_BIT )
    return;

  memset(freq, 0, sizeof(freq));

  int i;
  for( i = 0; i < n; i++ )
    freq[v2[i] >> bits & MASK]++;

  ind[0] = 0;
  for( i = 1; i < BASE; i++ )
    ind[i] = ind[i - 1] + freq[i - 1];

  for( i = 0; i < n; i++ )
    aux[ind[v2[i] >> bits & MASK]++] = v2[i];
  radix_sort(aux, v2, n, bits + BITS_STEP );
}
int main()
{
    int n, i;
    long long x, b, c;
    in>>n>>x>>b>>c;
    v[0] = b;
    for( i = 1; i < n; i++ )
      v[i] = ( x * v[i - 1] + b ) % c;
    radix_sort(v, a, n, 0);
    for( i = 0; i < n;  i++ ){
      if( i % 10 == 0 )
        out<<v[i]<<" ";
    }
    return 0;
}