#include <algorithm>
#include <cassert>
#include <chrono>
#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>

template <typename T>
void reserve(std::set<T>&, size_t) {}
template <typename T>
void reserve(std::unordered_set<T>& s, size_t n) { s.reserve(n); }

template<bool Sorted, class Rng>
std::vector<unsigned int> draw_select(unsigned int k, unsigned int n, Rng& rng)
{
  std::vector<unsigned> v;
  if (6*k > n) { // Experimentell bestimmt!
    v.reserve(n); for (unsigned i=0; i<n; ++i) v.push_back(i); // iota_n
    for (unsigned i=k; i<n; ++i) {
      auto del=std::uniform_int_distribution<unsigned>(0, v.size())(rng);
      std::swap(v[del], v.back());
      v.pop_back();
    }
    if (Sorted) std::sort(v.begin(), v.end());
  } else {
    typename std::conditional<Sorted, std::set<unsigned>, std::unordered_set<unsigned> >::type set;
    reserve(set, k);
    std::uniform_int_distribution<unsigned> dis(0, n-1);
    while (set.size() != k)
      set.insert(dis(rng));
    v.reserve(n); v.assign(set.begin(), set.end());
  }
  return v;
}

template<class Rng>
std::vector<unsigned int> drawUniqueSubset(unsigned int k, unsigned int n, Rng& rng)
{
  return draw_select<true>(k, n, rng);
}

template<class Rng>
std::vector<unsigned int> drawUniqueSubsetOrdered(unsigned int k, unsigned int n, Rng& rng)
{
  return draw_select<false>(k, n, rng);
}

template <typename C, typename F>
void measure(C& c, const char *msg, F&& f)
{
  auto start = c.now();
  std::forward<F>(f)();
  auto end = c.now();
  std::cout << msg << ": "
            << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count()
            << "ms\n";
}

int main()
{
  std::minstd_rand rng;
  const unsigned n=1000000;
  std::chrono::high_resolution_clock c;

  for (unsigned k=0; k<=100; k+=5) {
    std::cout << k << "%\n";
    std::vector<unsigned> v;

    measure(c, "  unsorted: ", [&](){v=drawUniqueSubset(k*n/100, n, rng);});
    assert(v.size() == k*n/100);
    std::sort(v.begin(), v.end());
    assert(std::unique(v.begin(), v.end())==v.end());
    for (auto i : v) assert(i < n);
    std::vector<unsigned>().swap(v);
    measure(c, "  sorted:   ", [&](){v=drawUniqueSubset(k*n/100, n, rng);});
    assert(v.size() == k*n/100);
    assert(std::is_sorted(v.begin(), v.end()));
    assert(std::unique(v.begin(), v.end())==v.end());
    for (auto i : v) assert(i < n);
    std::vector<unsigned>().swap(v);
  }
}