#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);
  }
}

I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGNhc3NlcnQ+CiNpbmNsdWRlIDxjaHJvbm8+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPHVub3JkZXJlZF9zZXQ+CiNpbmNsdWRlIDx2ZWN0b3I+Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgVD4Kdm9pZCByZXNlcnZlKHN0ZDo6c2V0PFQ+Jiwgc2l6ZV90KSB7fQp0ZW1wbGF0ZSA8dHlwZW5hbWUgVD4Kdm9pZCByZXNlcnZlKHN0ZDo6dW5vcmRlcmVkX3NldDxUPiYgcywgc2l6ZV90IG4pIHsgcy5yZXNlcnZlKG4pOyB9Cgp0ZW1wbGF0ZTxib29sIFNvcnRlZCwgY2xhc3MgUm5nPgpzdGQ6OnZlY3Rvcjx1bnNpZ25lZCBpbnQ+IGRyYXdfc2VsZWN0KHVuc2lnbmVkIGludCBrLCB1bnNpZ25lZCBpbnQgbiwgUm5nJiBybmcpCnsKICBzdGQ6OnZlY3Rvcjx1bnNpZ25lZD4gdjsKICBpZiAoNiprID4gbikgeyAvLyBFeHBlcmltZW50ZWxsIGJlc3RpbW10IQogICAgdi5yZXNlcnZlKG4pOyBmb3IgKHVuc2lnbmVkIGk9MDsgaTxuOyArK2kpIHYucHVzaF9iYWNrKGkpOyAvLyBpb3RhX24KICAgIGZvciAodW5zaWduZWQgaT1rOyBpPG47ICsraSkgewogICAgICBhdXRvIGRlbD1zdGQ6OnVuaWZvcm1faW50X2Rpc3RyaWJ1dGlvbjx1bnNpZ25lZD4oMCwgdi5zaXplKCkpKHJuZyk7CiAgICAgIHN0ZDo6c3dhcCh2W2RlbF0sIHYuYmFjaygpKTsKICAgICAgdi5wb3BfYmFjaygpOwogICAgfQogICAgaWYgKFNvcnRlZCkgc3RkOjpzb3J0KHYuYmVnaW4oKSwgdi5lbmQoKSk7CiAgfSBlbHNlIHsKICAgIHR5cGVuYW1lIHN0ZDo6Y29uZGl0aW9uYWw8U29ydGVkLCBzdGQ6OnNldDx1bnNpZ25lZD4sIHN0ZDo6dW5vcmRlcmVkX3NldDx1bnNpZ25lZD4gPjo6dHlwZSBzZXQ7CiAgICByZXNlcnZlKHNldCwgayk7CiAgICBzdGQ6OnVuaWZvcm1faW50X2Rpc3RyaWJ1dGlvbjx1bnNpZ25lZD4gZGlzKDAsIG4tMSk7CiAgICB3aGlsZSAoc2V0LnNpemUoKSAhPSBrKQogICAgICBzZXQuaW5zZXJ0KGRpcyhybmcpKTsKICAgIHYucmVzZXJ2ZShuKTsgdi5hc3NpZ24oc2V0LmJlZ2luKCksIHNldC5lbmQoKSk7CiAgfQogIHJldHVybiB2Owp9Cgp0ZW1wbGF0ZTxjbGFzcyBSbmc+CnN0ZDo6dmVjdG9yPHVuc2lnbmVkIGludD4gZHJhd1VuaXF1ZVN1YnNldCh1bnNpZ25lZCBpbnQgaywgdW5zaWduZWQgaW50IG4sIFJuZyYgcm5nKQp7CiAgcmV0dXJuIGRyYXdfc2VsZWN0PHRydWU+KGssIG4sIHJuZyk7Cn0KCnRlbXBsYXRlPGNsYXNzIFJuZz4Kc3RkOjp2ZWN0b3I8dW5zaWduZWQgaW50PiBkcmF3VW5pcXVlU3Vic2V0T3JkZXJlZCh1bnNpZ25lZCBpbnQgaywgdW5zaWduZWQgaW50IG4sIFJuZyYgcm5nKQp7CiAgcmV0dXJuIGRyYXdfc2VsZWN0PGZhbHNlPihrLCBuLCBybmcpOwp9Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgQywgdHlwZW5hbWUgRj4Kdm9pZCBtZWFzdXJlKEMmIGMsIGNvbnN0IGNoYXIgKm1zZywgRiYmIGYpCnsKICBhdXRvIHN0YXJ0ID0gYy5ub3coKTsKICBzdGQ6OmZvcndhcmQ8Rj4oZikoKTsKICBhdXRvIGVuZCA9IGMubm93KCk7CiAgc3RkOjpjb3V0IDw8IG1zZyA8PCAiOiAiCiAgICAgICAgICAgIDw8IHN0ZDo6Y2hyb25vOjpkdXJhdGlvbl9jYXN0PHN0ZDo6Y2hyb25vOjptaWxsaXNlY29uZHM+KGVuZC1zdGFydCkuY291bnQoKQogICAgICAgICAgICA8PCAibXNcbiI7Cn0KCmludCBtYWluKCkKewogIHN0ZDo6bWluc3RkX3JhbmQgcm5nOwogIGNvbnN0IHVuc2lnbmVkIG49MTAwMDAwMDsKICBzdGQ6OmNocm9ubzo6aGlnaF9yZXNvbHV0aW9uX2Nsb2NrIGM7CgogIGZvciAodW5zaWduZWQgaz0wOyBrPD0xMDA7IGsrPTUpIHsKICAgIHN0ZDo6Y291dCA8PCBrIDw8ICIlXG4iOwogICAgc3RkOjp2ZWN0b3I8dW5zaWduZWQ+IHY7CgogICAgbWVhc3VyZShjLCAiICB1bnNvcnRlZDogIiwgWyZdKCl7dj1kcmF3VW5pcXVlU3Vic2V0KGsqbi8xMDAsIG4sIHJuZyk7fSk7CiAgICBhc3NlcnQodi5zaXplKCkgPT0gaypuLzEwMCk7CiAgICBzdGQ6OnNvcnQodi5iZWdpbigpLCB2LmVuZCgpKTsKICAgIGFzc2VydChzdGQ6OnVuaXF1ZSh2LmJlZ2luKCksIHYuZW5kKCkpPT12LmVuZCgpKTsKICAgIGZvciAoYXV0byBpIDogdikgYXNzZXJ0KGkgPCBuKTsKICAgIHN0ZDo6dmVjdG9yPHVuc2lnbmVkPigpLnN3YXAodik7CiAgICBtZWFzdXJlKGMsICIgIHNvcnRlZDogICAiLCBbJl0oKXt2PWRyYXdVbmlxdWVTdWJzZXQoaypuLzEwMCwgbiwgcm5nKTt9KTsKICAgIGFzc2VydCh2LnNpemUoKSA9PSBrKm4vMTAwKTsKICAgIGFzc2VydChzdGQ6OmlzX3NvcnRlZCh2LmJlZ2luKCksIHYuZW5kKCkpKTsKICAgIGFzc2VydChzdGQ6OnVuaXF1ZSh2LmJlZ2luKCksIHYuZW5kKCkpPT12LmVuZCgpKTsKICAgIGZvciAoYXV0byBpIDogdikgYXNzZXJ0KGkgPCBuKTsKICAgIHN0ZDo6dmVjdG9yPHVuc2lnbmVkPigpLnN3YXAodik7CiAgfQp9