Cod sursa(job #2434973)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 2 iulie 2019 17:21:13
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
#include <fstream>
using namespace std;

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

vector<int> countingSort(vector<int> arr, int digitIndex)
{
  int count[10];
  memset(count, 0, sizeof count);
  vector<int> result = arr;

  for (int num : arr)
  {
    count[(num / digitIndex) % 10]++;
  }
  for (int i = 1; i < 10; i++)
  {
    count[i] += count[i - 1];
  }
  for (int i = arr.size() - 1; i >= 0; i--)
  {
    result[count[(arr[i] / digitIndex) % 10] - 1] = arr[i];
    count[(arr[i] / digitIndex) % 10]--;
  }
  return result;
}

vector<int> radixSort(vector<int> arr)
{
  int maxElem = *max_element(arr.begin(), arr.end());
  for (int exp = 1; maxElem / exp > 0; exp *= 10)
  {
    arr = countingSort(arr, exp);
  }
  return arr;
}

int main()
{
  int N, A, B, C;
  fin >> N >> A >> B >> C;

  vector<int> arr;
  arr.push_back(B);
  for (int i = 1; i < N; i++)
  {
    arr.push_back((arr.back() * A + B) % C);
  }
  arr = radixSort(arr);
  for (int i = 0; i < N; i += 10)
  {
    fout << arr[i] << " ";
  }
  return 0;
}