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

Envío 6763

Problema 0xde - Ordenar un arreglo grande

  • Autor: danidiaztech
  • Fecha: 2022-11-14 21:54:14 UTC (Hace 16 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
Tiempo límite excedido
1.057 s 2 KBi
#8
Tiempo límite excedido
1.092 s 3 KBi
#9
Tiempo límite excedido
1.078 s 2 KBi
#10
Correcto
0.338 s 3 KBi
#11
Tiempo límite excedido
1.094 s 2 KBi
#12
Tiempo límite excedido
1.084 s 2 KBi
#13
Tiempo límite excedido
1.091 s 2 KBi
#14
Tiempo límite excedido
1.067 s 2 KBi
#15
Tiempo límite excedido
1.068 s 2 KBi
#16
Correcto
0.053 s 3 KBi
#17
Correcto
0.054 s 3 KBi
#18
Tiempo límite excedido
1.092 s 2 KBi
#19
Tiempo límite excedido
1.079 s 2 KBi
#20
Tiempo límite excedido
1.033 s 3 KBi
#21
Tiempo límite excedido
1.084 s 2 KBi
#22
Tiempo límite excedido
1.044 s 2 KBi
#23
Tiempo límite excedido
1.067 s 2 KBi
#24
Tiempo límite excedido
1.013 s 2 KBi
#25
Tiempo límite excedido
1.012 s 2 KBi
#26
Tiempo límite excedido
1.077 s 2 KBi
#27
Tiempo límite excedido
1.076 s 2 KBi
Puntos totales: 34 / 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);
  }
}

// function to swap elements
void customswap(int *a, int *b) {
  int t = *a;
  *a = *b;
  *b = t;
}

int partition(int l, int r ){
  int in = l - 1;
  int pivot = a[r];
  if (l < r){
    for (int i = l; i < r; i++){
      if (a[i] < pivot){
        in++;
        customswap(&a[i], &a[in]);
      }
    }
  }
  customswap(&a[r], &a[in + 1]);
  return in + 1;
}

void quicksort(int l, int r){
  if (l < r){
    int pivot = partition(l, r);
    quicksort(l, pivot - 1);
    quicksort(pivot + 1, r);
  }
}

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(0, n - 1);
  // mergesort(0, n - 1);

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

  return 0;
}