Cod sursa(job #3327492)

Utilizator Andrei_PanaAndrei Pana Andrei_Pana Data 4 decembrie 2025 10:37:03
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;

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

#define MAXN 10000000
#define BASE 16

int v[MAXN],output[MAXN];
int frecv[BASE];

void radixSort(int arr[],int n){
  if(n==0){
    return;
  }

  int maxval = arr[0];
  for(int i=1;i<n;i++){
    if(arr[i]>maxval){
      maxval=arr[i];
    }
  }

  for(int exp=0;(maxval>>exp)>0;exp+=4){
    memset(frecv,0,sizeof(frecv));

    for(int i=0;i<n;i++){
      frecv[(arr[i]>>exp)&(BASE-1)]++;
    }

    for(int i=1;i<BASE;i++) {
      frecv[i]+=frecv[i-1];
    }

    for(int i=n-1;i>=0;i--){
      output[--frecv[(arr[i]>>exp)&(BASE-1)]]=arr[i];
    }

    for(int i=0;i<n;i++){
      arr[i]=output[i];
    }
  }
}

int main(){
  int n,a,b,c;
  cin>>n>>a>>b>>c;

  v[0]=b;
  for(int i=1;i<n;i++){
    v[i]=(1LL*a*v[i-1]+b)%c;
  }

  radixSort(v,n);

  for(int i=0;i<n;i+=10) {
    cout<<v[i]<<" ";
  }
  cout << endl;

  return 0;
}