#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;
}
I2luY2x1ZGUgPHJhbmRvbT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHVub3JkZXJlZF9tYXA+Cgp0ZW1wbGF0ZTxjbGFzcyBJbnQsIGNsYXNzIEdlbmVyYXRvcj4Kc3RkOjp2ZWN0b3I8SW50PiByYW5kb21TYW1wbGUoSW50IGFtdCwgSW50IGxpbSwgR2VuZXJhdG9yJiBnKSB7CiAgc3RkOjp1bm9yZGVyZWRfbWFwPEludCwgSW50PiBzaHVmZmxlOyAgLy8gTm90ZTogdGhlcmUgYXJlIG11Y2ggYmV0dGVyIGhhc2ggdGFibGUgaW1wbGVtZW50YXRpb25zIHRoYW4gc3RkJ3MKICBmb3IgKEludCBpPTE7IGk8PWFtdDsgKytpKSB7CiAgICBJbnQgYyA9IHN0ZDo6dW5pZm9ybV9pbnRfZGlzdHJpYnV0aW9uPEludD4oaSwgbGltKShnKTsKICAgIGlmICghc2h1ZmZsZS5jb3VudChjKSkKICAgICAgc2h1ZmZsZVtjXSA9IGM7CiAgICBpZiAoIXNodWZmbGUuY291bnQoaSkpCiAgICAgIHNodWZmbGVbaV0gPSBpOwogICAgc3RkOjpzd2FwKHNodWZmbGVbaV0sIHNodWZmbGVbY10pOwogIH0KICBzdGQ6OnZlY3RvcjxJbnQ+IGFuczsKICBmb3IgKEludCBpPTE7IGk8PWFtdDsgKytpKQogICAgYW5zLnB1c2hfYmFjayhzaHVmZmxlW2ldKTsKICByZXR1cm4gYW5zOwp9CgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxhbGdvcml0aG0+CgppbnQgbWFpbigpIHsKICBzdGQ6OnJhbmRvbV9kZXZpY2UgcmQ7CiAgc3RkOjptdDE5OTM3IGdlbihyZCgpKTsKICBzdGQ6OnZlY3RvcjxpbnQ+IHNhbXBsZSA9IHJhbmRvbVNhbXBsZSgxMDAsIDMwMDAsIGdlbik7CiAgZm9yIChpbnQgaT0wOyBpPHNhbXBsZS5zaXplKCk7ICsraSkKICAgIHN0ZDo6Y291dCA8PCBzYW1wbGVbaV0gPDwgJyAnOwogIHN0ZDo6Y291dCA8PCBzdGQ6OmVuZGw7CiAgc3RkOjpzb3J0KHNhbXBsZS5iZWdpbigpLCBzYW1wbGUuZW5kKCkpOwogIGZvciAoaW50IGk9MDsgaTxzYW1wbGUuc2l6ZSgpOyArK2kpCiAgICBzdGQ6OmNvdXQgPDwgc2FtcGxlW2ldIDw8ICcgJzsKICBzdGQ6OmNvdXQgPDwgc3RkOjplbmRsOwp9