Cod sursa(job #2945098)

Utilizator andiRTanasescu Andrei-Rares andiR Data 23 noiembrie 2022 14:32:01
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb
///radixsort-LSD variant
/*#include <iostream>
#include <fstream>

#define Nmax 10000000
#define MaxBit 32
#define BitsPerStep 8
#define Mask ((1<<BitsPerStep)-1)
using namespace std;
ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");

int n,a,b,c;
int v1[Nmax], v2[Nmax], ind[Mask+1], fr[Mask+1];

void radixsort(int v[], int aux[], int bit){
    if (bit==MaxBit)
        return;
    for (int i=0;i<=Mask;i++)
        fr[i]=0;
    for (int i=0;i<n;i++)
        fr[(v[i]>>bit)%Mask]++;
    ind[0]=0;
    for (int i=1;i<=Mask;i++)
        ind[i]=ind[i-1]+fr[i-1];
    for (int i=0;i<n;i++)
        aux[ind[(v[i]>>bit)%Mask]++]=v[i];
    radixsort(aux, v, bit+BitsPerStep);
}
int main()
{
    fin>>n>>a>>b>>c;
    v1[0]=b;
    for (int i=1;i<n;i++){
        v1[i]=((long long)a*v1[i-1]+b)%c;
    }
    radixsort(v1, v2, 0);
    for (int i=0;i<n;i+=10)
        fout<<v1[i]<<' ';
    return 0;
}*/
#include <iostream>
#include <fstream>
#include <cstring>

#define MAX_N 10000000
#define MAX_BITS 32      // Numerele au maxim 32 biti
#define BITS_PER_STEP 8  // Impartim pe perechi de 8 biti
#define BASE (1 << BITS_PER_STEP)
#define MASK (BASE - 1)
using namespace std;
ifstream fin ("radixsort.in");
ofstream fout ("radixsort.out");
// Avem nevoie de un array auxiliar, pentru a aranja numerele dupa fiecare pas al algoritmului
int v1[MAX_N], v2[MAX_N];
int freq[BASE], ind[BASE];

void sort(int v[], int aux[], int n, int bits) {
  if (bits == MAX_BITS)
    return;

  // Resetam vectorul de frecventa la fiecare pas nou
  memset(freq, 0, sizeof(freq));

  int i;
  for (i = 0; i < n; ++i)
    ++freq[v[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[v[i] >> bits & MASK]++] = v[i];

  // Interschimbare intre vectorul aux si v
  sort(aux, v, n, bits + BITS_PER_STEP);
}

int main() {
  int n,a,b,c;
  fin>>n>>a>>b>>c;
  v1[0]=b;
  for (int i = 1; i < n; ++i)
    v1[i]=((long long)v1[i-1]*a+b)%c;
  sort(v1, v2, n, 0);
  for (int i = 0; i < n; i+=10)
    fout<<v1[i]<<' ';
  return 0;
}