Cod sursa(job #2677693)

Utilizator Antonia_onisoruantonia onisoru Antonia_onisoru Data 27 noiembrie 2020 10:47:30
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

#define MAXN 10000000
#define MAX_BITES 32
#define BITS_PER_STEP 4

const int BASE = 1 << BITS_PER_STEP;
const int MASK = BASE - 1;

int v[MAXN];
vector<int> buket[ 1 << BITS_PER_STEP ];

void radix_sort( int v[], int n, int bits ){
  if( bits == MAX_BITES )
    return;

  int i, b;
  unsigned int j;

  for( i = 0; i < n; i++ )
    buket[v[i] >> bits & MASK].push_back(v[i]);

  i = 0;
  for( b = 0; b < BASE; b++ ){
    for( j = 0; j < buket[b].size(); j++)
      v[i++] = buket[b][j];
    buket[b].clear();
  }
  radix_sort(v, n, bits + BITS_PER_STEP);
}

int main()
{
    int n, a, b, c, i;
    in>>n>>a>>b>>c;
    v[0] = b;
    for( i = 1; i < n; i++ )
      v[i] = ( a * v[i - 1] + b ) % c;
    //out<<'\n'
    radix_sort(v, n, 0);
    for( i = 0; i < n;  i++ ){
      if( i % 10 == 0 )
        out<<v[i]<<" ";
    }
    return 0;
}