Cod sursa(job #2434991)

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

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

vector<int> arr, helper;
int cnt[256], byteNo=0;

int valueOfByte(int x)
{
    return (x>>(byteNo*8))&255;
}
void countingSort()
{
  memset(cnt, 0, sizeof cnt);

  for (int num : arr)
  {
    cnt[valueOfByte(num)]++;
  }
  for (int i = 1; i < 256; i++)
  {
    cnt[i] += cnt[i - 1];
  }
  for (int i = arr.size() - 1; i >= 0; i--)
  {
    helper[--cnt[valueOfByte(arr[i])]] = arr[i];
  }

  arr = helper;
}

void radixSort()
{
  for (byteNo = 0; byteNo<4; byteNo++)
  {
    countingSort();
  }
}

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

  arr.push_back(B%C);

  for (int i = 1; i < N; i++)
  {
    arr.push_back((1LL * A*arr.back() + B) % C);
  }
  helper = arr;

  radixSort();
  for (int i = 0; i < N; i +=10)
  {
    fout << arr[i] << " ";
  }
  return 0;
}