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

Envío 2565

Problema 0xde - Ordenar un arreglo grande

  • Autor: pipelin1010
  • Fecha: 2021-01-05 06:07:13 UTC (Hace alrededor de 3 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.006 s 1 KBi
#2
Correcto
0.006 s 1 KBi
#3
Correcto
0.008 s 1 KBi
#4
Correcto
0.006 s 1 KBi
#5
Correcto
0.005 s 2 KBi
#6
Correcto
0.007 s 1 KBi
#7
Correcto
0.153 s 3 KBi
#8
Correcto
0.156 s 3 KBi
#9
Correcto
0.153 s 3 KBi
#10
Correcto
0.203 s 2 KBi
#11
Correcto
0.18 s 3 KBi
#12
Correcto
0.149 s 2 KBi
#13
Correcto
0.156 s 3 KBi
#14
Correcto
0.15 s 2 KBi
#15
Correcto
0.156 s 3 KBi
#16
Correcto
0.185 s 3 KBi
#17
Correcto
0.203 s 3 KBi
#18
Correcto
0.144 s 3 KBi
#19
Correcto
0.209 s 3 KBi
#20
Correcto
0.197 s 2 KBi
#21
Correcto
0.156 s 2 KBi
#22
Correcto
0.169 s 3 KBi
#23
Correcto
0.152 s 3 KBi
#24
Correcto
0.15 s 3 KBi
#25
Correcto
0.193 s 3 KBi
#26
Correcto
0.152 s 2 KBi
#27
Correcto
0.153 s 3 KBi
Puntos totales: 100 / 100

Código

//
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define MOD 1000000007
#define PI 3.14159265
#define EPS 1e-9
#define Pi acos(-1.0)
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
#define forr(i,a,b) for(int i=(a); i<(b); i++)
#define clean(arr,val) memset(arr,val,sizeof(arr))
#define forn(i,n) forr(i,0,n)
#define PB push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vpll;

/*CODE START HERE*/

int n;
vi a, sol;

//Quick sort
void quick(int l, int r){
    bool equal = true;
    forr(i,l,r){
        if(a[i] != a[i+1]){
            equal = false;
        }
    }
    if(equal) return;
    if(l >= r)
        return;
    int indPivot = (rand()%(r-l+1))+l;
    swap(a[l],a[indPivot]);
    int pivot = a[l];
    int p = l;
    for(int i = l+1; i <= r; i++){
        if(pivot >= a[i]){
            swap(a[++p],a[i]);
        }
    }
    swap(a[p],a[l]);
    quick(l,p-1);
    quick(p+1,r);
}

vi merge(int l, int r){
    // cout << "NOW ON L " << l << " R " << r << "\n"; 

    int mid = (l+r)/2;
    int size = (r-l+1);
    vi arrL, arrR, arr;
    if (l == r){
        arr.assign(1,a[l]);
        // cout << "AFTER MERGE L " << l << " R " << r << "\n";
        // forn(i,(int)arr.size()) cout << arr[i] << " ";
        // cout << "\n";
        return arr;
    }
    arrL = merge(l,mid);
    arrR = merge(mid+1,r);
    arr.assign(size,0);

    for(int i = 0, j = 0, k = 0; k < size; k++){
        if(i >= (int)arrL.size()){
            arr[k] = arrR[j];
            j++;
        }else if(j >= (int)arrR.size()){
            arr[k] = arrL[i];
            i++;
        }else if(arrL[i] < arrR[j]){
            arr[k] = arrL[i];
            i++;
        }else{
            arr[k] = arrR[j];
            j++;
        }
    }

    // cout << "AFTER MERGE L " << l << " R " << r << "\n";
    // forn(i,(int)arr.size()) cout << arr[i] << " ";
    // cout << "\n";
    return arr;
}

int main(){
    //freopen("out","w",stdout);
    ios::sync_with_stdio(0);
    cin >> n;
    a.assign(n,0);
    forn(i,n) cin >> a[i];
    //quick(0,n-1);
    a = merge(0,n-1);
    cout << a[0];
    forr(i,1,n){
        cout << " " << a[i];
    }
    cout << "\n";
    return 0;
}