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

Envío 6759

Problema 0xde - Ordenar un arreglo grande

  • Autor: danidiaztech
  • Fecha: 2022-11-14 21:33:10 UTC (Hace 11 días)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.005 s 1 KBi
#2
Correcto
0.005 s 1 KBi
#3
Correcto
0.005 s 1 KBi
#4
Correcto
0.004 s 1 KBi
#5
Correcto
0.005 s 1 KBi
#6
Correcto
0.006 s 1 KBi
#7
Correcto
0.036 s 2 KBi
#8
Correcto
0.038 s 3 KBi
#9
Correcto
0.021 s 3 KBi
#10
Correcto
0.04 s 3 KBi
#11
Correcto
0.033 s 4 KBi
#12
Correcto
0.031 s 4 KBi
#13
Correcto
0.041 s 3 KBi
#14
Correcto
0.044 s 3 KBi
#15
Correcto
0.041 s 3 KBi
#16
Correcto
0.041 s 4 KBi
#17
Correcto
0.041 s 4 KBi
#18
Correcto
0.028 s 3 KBi
#19
Correcto
0.04 s 3 KBi
#20
Correcto
0.04 s 3 KBi
#21
Correcto
0.023 s 3 KBi
#22
Correcto
0.028 s 3 KBi
#23
Correcto
0.025 s 3 KBi
#24
Correcto
0.027 s 3 KBi
#25
Correcto
0.027 s 3 KBi
#26
Correcto
0.027 s 3 KBi
#27
Correcto
0.036 s 3 KBi
Puntos totales: 100 / 100

Código

// Made by Daniel Diaz (@Danidiaztech)
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define forn(i, n) for (int i = 0; i < n; i++) // for in range in python
#define FOR(i, a, b) for (int i = a; i < b; i++) // for in range in python
#define int long long int
#define double long double
#define pb push_back
#define ff first
#define ss second
#define mk make_pair

typedef pair<int, int> pii;

const int MAX = 1e5 + 10;
const int MIN = -MAX;
const int INF = LLONG_MAX;
const int MINF = LLONG_MIN;
const int MOD = 1e9 + 7;

int a[MAX];

// p -> start, q -> middle,r -> end
void merge(int p, int q, int r){
  int n1 = q - p + 1;
  int n2 = r - q;

  int L[n1], M[n2];
  /// From start to middle
  for (int i = 0; i < n1; i++){
    L[i] = a[p + i];
  }

  // From middle to end
  for (int j = 0 ; j < n2; j++){
    M[j] = a[q + j + 1];
  }

  int i,j,k;
  i = j  = 0;
  k = p;

  while (i < n1 && j < n2){
    if (L[i] <=  M[j]){
      a[k]= L[i];
      i++;
    }
    else{
      a[k]= M[j];
      j++;
    }
    k++;
  }

  // Pick remaining elements and put them in the array
  while (i < n1){
    a[k] = L[i];
    i++;
    k++;
  }

  while (j < n2){
    a[k]= M[j];
    j++;
    k++;
  }
}

void mergesort(int l, int r){
  // Sort the array by halving it recursively
  // until we have parts of two elements, then, we sort these elements
  // and merge them again to form the sorted array
  if (l < r){
    int mid = l + (r - l) / 2;
    mergesort(l, mid);
    mergesort(mid + 1, r);

    // Merge the sorted arrays
    merge(l, mid, r);
  }
}

void quicksort(){

}

void heapsort(){

}

int32_t main() {
  fastInp;
  #if LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  #endif

  int n; cin >> n;
  forn(i, n) cin >> a[i];
  // heapsort();
  // quicksort();
  mergesort(0, n - 1);

  forn(i, n){
    if (i != 0){
      cout << " ";
    }
    cout << a[i];
  }

  return 0;
}