#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
 
using namespace std;
 
// 检查数组是否已排序
bool isSorted(const vector<int>& arr) {
    for (size_t i = 0; i < arr.size() - 1; ++i) {
        if (arr[i] > arr[i + 1]) {
            return false;
        }
    }
    return true;
}
 
// 猴子排序实现
void bogoSort(vector<int>& arr) {
    // 使用时间作为随机种子
    unsigned seed = chrono::system_clock::now().time_since_epoch().count();
    default_random_engine engine(seed);
 
    int attempts = 0; // 记录尝试次数
 
    // 当数组未排序时继续打乱
    while (!isSorted(arr)) {
        // 随机打乱数组
        shuffle(arr.begin(), arr.end(), engine);
        attempts++;
 
        // 每10000次尝试打印一次进度（可选）
        if (attempts % 10000 == 0) {
            cout << "已尝试 " << attempts << " 次..." << endl;
        }
    }
 
    cout << "排序完成！总共尝试了 " << attempts << " 次。" << endl;
}
 
int main() {
    vector<int> arr = {5, 2, 9, 1, 5, 6,5699,16,63,47};
 
    cout << "排序前: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
 
    bogoSort(arr);
 
    cout << "排序后: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
 
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8cmFuZG9tPgojaW5jbHVkZSA8Y2hyb25vPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIOajgOafpeaVsOe7hOaYr+WQpuW3suaOkuW6jwpib29sIGlzU29ydGVkKGNvbnN0IHZlY3RvcjxpbnQ+JiBhcnIpIHsKICAgIGZvciAoc2l6ZV90IGkgPSAwOyBpIDwgYXJyLnNpemUoKSAtIDE7ICsraSkgewogICAgICAgIGlmIChhcnJbaV0gPiBhcnJbaSArIDFdKSB7CiAgICAgICAgICAgIHJldHVybiBmYWxzZTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gdHJ1ZTsKfQoKLy8g54y05a2Q5o6S5bqP5a6e546wCnZvaWQgYm9nb1NvcnQodmVjdG9yPGludD4mIGFycikgewogICAgLy8g5L2/55So5pe26Ze05L2c5Li66ZqP5py656eN5a2QCiAgICB1bnNpZ25lZCBzZWVkID0gY2hyb25vOjpzeXN0ZW1fY2xvY2s6Om5vdygpLnRpbWVfc2luY2VfZXBvY2goKS5jb3VudCgpOwogICAgZGVmYXVsdF9yYW5kb21fZW5naW5lIGVuZ2luZShzZWVkKTsKICAgIAogICAgaW50IGF0dGVtcHRzID0gMDsgLy8g6K6w5b2V5bCd6K+V5qyh5pWwCiAgICAKICAgIC8vIOW9k+aVsOe7hOacquaOkuW6j+aXtue7p+e7reaJk+S5sQogICAgd2hpbGUgKCFpc1NvcnRlZChhcnIpKSB7CiAgICAgICAgLy8g6ZqP5py65omT5Lmx5pWw57uECiAgICAgICAgc2h1ZmZsZShhcnIuYmVnaW4oKSwgYXJyLmVuZCgpLCBlbmdpbmUpOwogICAgICAgIGF0dGVtcHRzKys7CiAgICAgICAgCiAgICAgICAgLy8g5q+PMTAwMDDmrKHlsJ3or5XmiZPljbDkuIDmrKHov5vluqbvvIjlj6/pgInvvIkKICAgICAgICBpZiAoYXR0ZW1wdHMgJSAxMDAwMCA9PSAwKSB7CiAgICAgICAgICAgIGNvdXQgPDwgIuW3suWwneivlSAiIDw8IGF0dGVtcHRzIDw8ICIg5qyhLi4uIiA8PCBlbmRsOwogICAgICAgIH0KICAgIH0KICAgIAogICAgY291dCA8PCAi5o6S5bqP5a6M5oiQ77yB5oC75YWx5bCd6K+V5LqGICIgPDwgYXR0ZW1wdHMgPDwgIiDmrKHjgIIiIDw8IGVuZGw7Cn0KCmludCBtYWluKCkgewogICAgdmVjdG9yPGludD4gYXJyID0gezUsIDIsIDksIDEsIDUsIDYsNTY5OSwxNiw2Myw0N307CiAgICAKICAgIGNvdXQgPDwgIuaOkuW6j+WJjTogIjsKICAgIGZvciAoaW50IG51bSA6IGFycikgewogICAgICAgIGNvdXQgPDwgbnVtIDw8ICIgIjsKICAgIH0KICAgIGNvdXQgPDwgZW5kbDsKICAgIAogICAgYm9nb1NvcnQoYXJyKTsKICAgIAogICAgY291dCA8PCAi5o6S5bqP5ZCOOiAiOwogICAgZm9yIChpbnQgbnVtIDogYXJyKSB7CiAgICAgICAgY291dCA8PCBudW0gPDwgIiAiOwogICAgfQogICAgY291dCA8PCBlbmRsOwogICAgCiAgICByZXR1cm4gMDsKfQ==