Cod sursa(job #3264968)

Utilizator divadddDavid Curca divaddd Data 26 decembrie 2024 03:29:45
Problema Radix Sort Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e7+2;
const int BASE = 1024;
int n,a,b,c,v[NMAX],aux[NMAX],cnt[BASE];

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

int main() {
  fin >> n >> a >> b >> c;
  v[1] = b;
  int maxi = 0;
  for(int i = 2; i <= n; i++){
    v[i] = (1ll*a*v[i-1]+b)%c;
    maxi = max(maxi, v[i]);
  }
  int nr_op = 0;
  while(maxi > 0){
    maxi /= BASE;
    nr_op++;
  }

  int pwr = 1;
  for(int k = 1; k <= nr_op; k++){
    for(int i = 1; i <= n; i++){
      int digit = (v[i] / pwr)%BASE;
      cnt[digit]++;
    }
    for(int i = 0; i < BASE; i++){
      cnt[i] += cnt[i-1];
    }
    for(int i = n; i >= 1; i--){
      int digit = (v[i] / pwr)%BASE;
      int pos = cnt[digit];
      aux[pos] = v[i];
      cnt[digit]--;
    }
    memcpy(v, aux, sizeof(v));
    memset(cnt, 0, sizeof(cnt));
    pwr *= BASE;
  }
  for(int i = 1; i <= n; i += 10){
    fout << v[i] << " ";
  }
  return 0;
}