█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 5423

Problema 0xde - Ordenar un arreglo grande

  • Autor: slash
  • Fecha: 2021-12-16 00:44:00 UTC (Hace más de 2 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.004 s 1 KBi
#2
Correcto
0.005 s 0 KBi
#3
Correcto
0.006 s 1 KBi
#4
Correcto
0.005 s 11 KBi
#5
Correcto
0.001 s 0 KBi
#6
Correcto
0.001 s 0 KBi
#7
Tiempo límite excedido
1.077 s 1 KBi
#8
Tiempo límite excedido
1.074 s 1 KBi
#9
Tiempo límite excedido
1.073 s 1 KBi
#10
Tiempo límite excedido
1.1 s 1 KBi
#11
Tiempo límite excedido
1.077 s 1 KBi
#12
Tiempo límite excedido
1.068 s 1 KBi
#13
Correcto
0.023 s 1 KBi
#14
Correcto
0.069 s 11 KBi
#15
Correcto
0.068 s 1 KBi
#16
Correcto
0.072 s 2 KBi
#17
Correcto
0.024 s 2 KBi
#18
Correcto
0.023 s 1 KBi
#19
Correcto
0.066 s 1 KBi
#20
Tiempo límite excedido
1.081 s 1 KBi
#21
Correcto
0.083 s 1 KBi
#22
Correcto
0.083 s 1 KBi
#23
Correcto
0.057 s 1 KBi
#24
Correcto
0.091 s 1 KBi
#25
Correcto
0.024 s 1 KBi
#26
Correcto
0.074 s 1 KBi
#27
Correcto
0.084 s 2 KBi
Puntos totales: 75 / 100

Código

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

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

#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';
    }
    shuffle(numbers.begin(), numbers.end(), rand_gen);
    quicksort(numbers,0,n - 1);
    for (int num: numbers) cout<<num<<' ';
}