Спринт 6. Улучшаем сложность.

#include <algorithm>
#include <iostream>
#include <vector>
#include <random>

using namespace std;

bool TestPermut(const vector<int>& v1, const vector<int>& v2) {
    if (v1.size() != v2.size()) {
        return false;
    }
    vector<int> v11 = v1;
    vector<int> v22 = v2;
    sort(v11.begin(), v11.end());
    sort(v22.begin(), v22.end());
    return v11 == v22;
}

int main() {
    std::mt19937 g;

    int n;
    cin >> n;
    vector<int> v1, v2;
    v1.reserve(n);
    v2.reserve(n);

    for (int i = 0; i < n; ++i) {
        v1.push_back(rand());
        v2.push_back(rand());
    }

    cout << "Random vectors match? "s << flush;
    cout << (TestPermut(v1, v2) ? "Yes"s : "No"s) << endl;

    v2 = v1;
    shuffle(v2.begin(), v2.end(), g);
    cout << "Permuted vectors match? "s << flush;
    cout << (TestPermut(v1, v2) ? "Yes"s : "No"s) << endl;
}