Envío 5421

Código

//
// Created by danie on 12/11/2021.
//

#include "iostream"
#include "random"
#include "chrono"

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL);


using namespace std;

mt19937 rand_gen(chrono::steady_clock::now().time_since_epoch().count());

void swap(int &a, int &b){
//    a = b + a;
//    b = a - b;
//    a = a - b;
    int temp = b;
    b = a;
    a = temp;
}

int partition(vector<int> &cards, int from, int to){
    int x = cards[to];
//    cout<<x<<' ';
    int i = from;
    for (int j = from; j < to; j++){
        if (cards[j] <= x){
            swap(cards[i++], cards[j]);
//            i++;
        }
    }
    swap(cards[i], cards[to]);
    return i;
}

void quicksort(vector<int> &cards, int from, int to){
    if (to > from){
        int part = partition(cards, from, to);
        quicksort(cards,from, part  -1);
        quicksort(cards, part + 1, to);
    }
}

int randomized_partition(vector<int> &cards, int from, int to){
//    int k = rand();

//    int i =  (rand_gen() % (to - from)) + from;
    int i =  uniform_int_distribution<long long>(from, to)(rand_gen) % (to - from) + from;
    swap(cards[to], cards[i]);
    return partition(cards,from,to);
}

int randomized_select(vector<int> &cards, int from, int to, int ith){ // este es el bueno
    if(to == from) return cards[from];
    int ordered_item = randomized_partition(cards, from, to);
//    int distance = ordered_item - from;
    if (ith == ordered_item) return cards[ordered_item];
    if (ith < ordered_item) return randomized_select(cards, from, ordered_item - 1, ith);
    return randomized_select(cards, ordered_item + 1, to, ith);
}

//int randomized_select(vector<int> &cards, int from, int to, int ith){
//    if(to == from) return cards[from];
//    int ordered_item = randomized_partition(cards, from, to);
//    int elements_on_left_array = (ordered_item - from) ;
//    if (ith == elements_on_left_array) return cards[ordered_item];
//    if (ith < ordered_item) return randomized_select(cards, from, ordered_item - 1, ith);
//    return randomized_select(cards, ordered_item + 1, to, ith - elements_on_left_array);
//}

void randomized_quicksort(vector<int> &cards,int from,int to){
    if (to > from){
        int part = randomized_partition(cards, from, to);
        randomized_quicksort(cards,from, part - 1);
        randomized_quicksort(cards, part + 1, to);
    }
}

//void tests(){
//    vector<int> cards = {25,45,38,19,9,4,14}; // 0 1 3 5 5 7 7 8 sorted
//
//    quicksort(cards,0,cards.size() - 1);
////    for(int card:cards)cout<<card<<' ';
//
////    cout<<'\n'<<randomized_select(copy_cards,0,cards.size() - 1, 7)<<'\n';
////    for(int card:copy_cards)cout<<card<<' ';
//
//
//}

int main(){
    fast_io
    int n; cin>>n;
//    rand_gen.seed(n);
    vector<int> numbers(n);
    for(int i = 0; i < n; i++) {
        cin>>numbers[i];
//        cout<<rand_gen()<<'\n';
    }
    randomized_quicksort(numbers,0,n - 1);
    for (int num: numbers) cout<<num<<' ';
}