Seminar8

#include <algorithm>
#include <ctime>
#include <iostream>
#include <optional>
#include <random>
#include <string>

const std::optional<int> GetSeedFromConfig() {
  return {};
}

int main1() {
  int seed = 0;
  auto seed_from_config = GetSeedFromConfig();
  if (seed_from_config) {
    seed = *seed_from_config;
  } else {
    seed = clock();
  }
  std::cout << seed;
  srand(seed);
  int n; std::cin >> n;
  for (int i = 0; i < n; ++i) {
    std::cout << rand() << " ";
  }
  return 0;
}

int gen_random_in_segment(int a, int b, std::mt19937& gen) {
  uint32_t rand = gen();
  std::uniform_int_distribution<> distrib(a, b);
//  return rand % (b - a + 1) + a;
  return distrib(gen);
}

int main2() {
  int seed = clock();
  std::mt19937 gen(seed);

  std::cout << gen_random_in_segment(6, 10, gen);
  return 0;
}

void CountingSort(std::vector<int>& v) {
  if (v.empty()) return;
  int v_max = *std::max_element(v.begin(), v.end());
  std::vector<int> counts(v_max + 1);
  for (int i = 0; i < v.size(); ++i)
    ++counts[v[i]];
  int j = 0;
  for (int i = 0; i <= v_max; ++i) {
    while (counts[i] != 0) {
      v[j++] = i;
      --counts[i];
    }
  }
}

void CountingSort2(std::vector<int>& v) {
  if (v.empty()) return;
  int v_max = *std::max_element(v.begin(), v.end());
  std::vector<int> counts(v_max + 1);
  for (int i = 0; i < v.size(); ++i)
    ++counts[v[i]];
  for (int i = 1; i <= v_max; ++i)
    counts[i] += counts[i - 1];
  std::vector<int> result(v.size());
  for (int i = v.size() - 1; i >= 0; --i)
    result[--counts[v[i]]] = v[i];

  // std::swap(v, result);
  v = std::move(result);
}

int main3() {
  try {
    int n = 0;
    std::cin >> n;
    std::vector<int> v(n);
    for (int &x: v) std::cin >> x;
    CountingSort2(v);
    for (int x: v) std::cout << x << " ";
  } catch(std::exception& e) {
    std::cerr << e.what() << std::endl;
  }
  return 0;
}

// 255.255.255.0
// 11111111.11111111.11111111.00000000

// r-ая четверка бит
// r = 1
// 0101010010111101
//         1011
// x             0101010010111101
// x >> r * 4 =  0000010101001011
// mask =        0000000000001111
// mask & prev = 0000000000001011
int Radix(int x, int r) {
  const int mask = 0b1111;
  return mask & (x >> r * 4);
}

void LSDSort(std::vector<int>& v) {
  int r = 0;
//  for (int r = 0; r < 8; ++r) {
    for (int x : v) {
      std::cout << Radix(x, r);
    }
//  }
}

int main4() {
  int n = 0;
  std::cin >> n;
  std::vector<int> v(n);
  for (int &x: v) std::cin >> x;
  LSDSort(v);
  for (int x: v) std::cout << x << " ";
  return 0;
}

int main() {
  std::cout << sizeof(long) << std::endl;
  std::cout << 045 << std::endl;
}

void MSDSort(std::vector<std::string>& v, int l, int r) {
  std::vector<int> counts(256);
  for (int i = 0; i < v.size(); ++i) ++counts[v[i][3]];
  for (int i = 1; i < 256; ++i) counts[i] += counts[i + 1];
  std::vector<std::string> result;
  for (int i = r - 1; i >= l; --i) result[--counts[v[i][3]]] = v[i];
  // Сортируем не все группы – начинаем с 1ой.
  for (int g = 1; g < 256; ++g) {
    MSDSort(v, counts[g], counts[g + 1]); // Кроме последней
  }
}