Cod sursa(job #2434999)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 2 iulie 2019 18:27:49
Problema Radix Sort Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>
#include <fstream>
#define MAXN 10000003
using namespace std;

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

int arr[MAXN], helper[MAXN];
int cnt[256], byteNo=0;
int N, A, B, C;

int valueOfByte(int x)
{
    return (x>>(byteNo*8))&255;
}

void countingSort()
{
  memset(cnt, 0, sizeof cnt);
  for (int i=0; i<N; i++) cnt[valueOfByte(arr[i])]++;
  for (int i = 1; i < 256; i++) cnt[i] += cnt[i - 1];
  for (int i = N - 1; i >= 0; i--) helper[--cnt[valueOfByte(arr[i])]] = arr[i];
  for (int i=0; i<N ;i++) arr[i]=helper[i];
}

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

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

  arr[0]= B%C;

  for (int i = 1; i < N; i++)
  {
    arr[i] = ((1LL * A*arr[i-1] + B) % C);
  }

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