Cod sursa(job #1741405)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 13 august 2016 20:25:46
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <algorithm>
#include <string>
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
using namespace std;

#ifdef INFOARENA
#define TEST 0
#else
#define TEST 1
#endif

class RadixSort {
public:
  RadixSort(int N, int A, int B, int C)
      : N_(N), A_(A), B_(B), C_(C), already_sorted(false) {
    sorted_numbers.resize(N);
    sorted_numbers[0] = B;
    for (int i = 2; i <= N; ++i) {
      sorted_numbers[i - 1] = (A * sorted_numbers[i - 2] + B) % C;
    }
  }
  void Sort() {
    sort(sorted_numbers.begin(), sorted_numbers.end());
  }
  const vector<int>& GetSortedNubmers() {
    if (!already_sorted) {
      Sort();
    }
    return sorted_numbers;
  }
private:
  int N_, A_, B_, C_;
  vector<int> sorted_numbers;
  bool already_sorted;
};

int main() {
  RadixSort *instance;
  if (TEST) {
    instance = new RadixSort(100, 12, 38, 123);
  } else {
    freopen("radixsort.in","r",stdin);
    freopen("radixsort.out","w",stdout);
    int N, A, B, C;
    scanf("%d %d %d %d", &N, &A, &B, &C);
    instance = new RadixSort(N, A, B, C);
  }

  vector<int> nums = instance->GetSortedNubmers();
  for (int i = 0; i < nums.size(); ++i) {
    if (i % 10 == 0) {
      printf("%d ", nums[i]);
    }
  }

  return 0;
}