Cod sursa(job #1755591)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 10 septembrie 2016 17:15:04
Problema Radix Sort Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.85 kb
#include <algorithm>
#include <string>
#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <queue>
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) {
    long long x = 0;
    // Put numbers into buckets by their less significant digit
    for (int i = 1; i <= N; ++i) {
      x = (x * A_ + B_) % C_;
      bucket_[0][x % 10].push(x); // push numbers in order
    }
  }
  void Sort() {
    int i = 1;
    int source = 1, dest = 0;
    do {
      i *= 10;
      source ^= 1;
      dest ^= 1;
      for (int j = 0; j < 10; ++j) {
        while (!bucket_[source][j].empty()) {
          // Extract one number and move it into other bucket
          int x = bucket_[source][j].front();
          bucket_[source][j].pop();
          int r = x / i;
          if (r > 0) {
            bucket_[dest][r % 10].push(x);
          } else {
            sorted_numbers_.push_back(x);
          }
        }
      }
    } while (i != 1000000000);
  }
  const vector<int>& GetSortedNubmers() {
    if (!already_sorted_) {
      Sort();
      already_sorted_ = 1;
    }
    return sorted_numbers_;
  }
private:
  int N_, A_, B_, C_;
  vector<int> sorted_numbers_;
  queue<int> bucket_[2][10]; // a queue for every digit
  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;
}