#include <random>
#include <vector>
#include <unordered_map>

template<class Int, class Generator>
std::vector<Int> randomSample(Int amt, Int lim, Generator& g) {
  std::unordered_map<Int, Int> shuffle;  // Note: there are much better hash table implementations than std's
  for (Int i=1; i<=amt; ++i) {
    Int c = std::uniform_int_distribution<Int>(i, lim)(g);
    if (!shuffle.count(c))
      shuffle[c] = c;
    if (!shuffle.count(i))
      shuffle[i] = i;
    std::swap(shuffle[i], shuffle[c]);
  }
  std::vector<Int> ans;
  for (Int i=1; i<=amt; ++i)
    ans.push_back(shuffle[i]);
  return ans;
}

#include <iostream>
#include <algorithm>

int main() {
  std::random_device rd;
  std::mt19937 gen(rd());
  std::vector<int> sample = randomSample(100, 3000, gen);
  for (int i=0; i<sample.size(); ++i)
    std::cout << sample[i] << ' ';
  std::cout << std::endl;
  std::sort(sample.begin(), sample.end());
  for (int i=0; i<sample.size(); ++i)
    std::cout << sample[i] << ' ';
  std::cout << std::endl;
}