Cod sursa(job #3176193)

Utilizator MemeComan Mihai Matei Meme Data 26 noiembrie 2023 20:15:46
Problema Radix Sort Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;
const int N_MAX = 1e7;
int n;
int v[N_MAX];
int f[10];
int newv[N_MAX];
int radixStep(int power){
  for(int i = 0; i < 10; i++){
    f[i] = 0;
  }

  for(int i = 0; i < n; i ++){
    f[(v[i] / power) % 10]++;
  }

  for(int i = 0; i < 10; i++){
    f[i] += f[i - 1];
  }

  for(int i = n - 1; i >= 0; i--){
    newv[f[(v[i] / power) % 10] - 1] = v[i];
    f[(v[i] / power) % 10]--;
  }

  for(int i = 0; i < n; i++){
    v[i] = newv[i];
  }
}
void radixsort(){
  int valmax;
  for(int i = 0; i < n; i++){
    valmax = max(valmax, v[i]);
  }
  for(int power = 1; power <= valmax; power *= 10){
    radixStep(power);
  }
}
int main()
{
    ifstream in("radixsort.in");
    ofstream out("radixsort.out");
    int a, b, c;
    in >> n >> a >> b >> c;
    v[0] = b;
    for(int i = 1; i < n; i++){
      v[i] = ((long long) a * v[i - 1] + b) % c;
    }
    radixsort();
    for(int i = 0; i < n; i += 10){
      out << v[i] << " ";
    }
    return 0;
}