Envío 1508

Problema 0xde - Ordenar un arreglo grande

Autor: d4vsanchez
Fecha: 2020-11-02 04:39:32 UTC (Hace alrededor de 4 años)

Caso #	Resultado	Tiempo	Memoria
#1	Correcto	0.023 s	3 KBi
#2	Correcto	0.021 s	4 KBi
#3	Correcto	0.024 s	3 KBi
#4	Correcto	0.022 s	3 KBi
#5	Correcto	0.02 s	3 KBi
#6	Correcto	0.022 s	3 KBi
#7	Tiempo límite excedido	0.855 s	5 KBi
#8	Tiempo límite excedido	0.538 s	7 KBi
#9	Tiempo límite excedido	0.525 s	5 KBi
#10	Tiempo límite excedido	0.766 s	9 KBi
#11	Tiempo límite excedido	1.045 s	14 KBi
#12	Tiempo límite excedido	1.015 s	14 KBi
#13	Tiempo límite excedido	0.54 s	14 KBi
#14	Tiempo límite excedido	1.073 s	14 KBi
#15	Tiempo límite excedido	0.547 s	14 KBi
#16	Correcto	0.621 s	14 KBi
#17	Correcto	0.555 s	14 KBi
#18	Tiempo límite excedido	0.544 s	15 KBi
#19	Tiempo límite excedido	0.747 s	14 KBi
#20	Tiempo límite excedido	0.942 s	5 KBi
#21	Tiempo límite excedido	0.641 s	14 KBi
#22	Error en tiempo de ejecución (NZEC) Exited with error status 1 Traceback (most recent call last): File "script.py", line 25, in <module> sort(arr, 0, n - 1) File "script.py", line 21, in sort sort(arr, p + 1, h) File "script.py", line 21, in sort sort(arr, p + 1, h) File "script.py", line 21, in sort sort(arr, p + 1, h) [Previous line repeated 9 more times] File "script.py", line 20, in sort sort(arr, l, p - 1) File "script.py", line 20, in sort sort(arr, l, p - 1) File "script.py", line 20, in sort sort(arr, l, p - 1) [Previous line repeated 981 more times] File "script.py", line 19, in sort p = generate_partition(arr, l, h) File "script.py", line 8, in generate_partition for j in range(l, h): RecursionError: maximum recursion depth exceeded in comparison	0.519 s	14 KBi
#23	Error en tiempo de ejecución (NZEC) Exited with error status 1 Traceback (most recent call last): File "script.py", line 25, in <module> sort(arr, 0, n - 1) File "script.py", line 21, in sort sort(arr, p + 1, h) File "script.py", line 21, in sort sort(arr, p + 1, h) File "script.py", line 21, in sort sort(arr, p + 1, h) [Previous line repeated 9 more times] File "script.py", line 20, in sort sort(arr, l, p - 1) File "script.py", line 20, in sort sort(arr, l, p - 1) File "script.py", line 20, in sort sort(arr, l, p - 1) [Previous line repeated 981 more times] File "script.py", line 19, in sort p = generate_partition(arr, l, h) File "script.py", line 8, in generate_partition for j in range(l, h): RecursionError: maximum recursion depth exceeded in comparison	0.56 s	14 KBi
#24	Error en tiempo de ejecución (NZEC) Exited with error status 1 Traceback (most recent call last): File "script.py", line 25, in <module> sort(arr, 0, n - 1) File "script.py", line 21, in sort sort(arr, p + 1, h) File "script.py", line 21, in sort sort(arr, p + 1, h) File "script.py", line 21, in sort sort(arr, p + 1, h) [Previous line repeated 9 more times] File "script.py", line 20, in sort sort(arr, l, p - 1) File "script.py", line 20, in sort sort(arr, l, p - 1) File "script.py", line 20, in sort sort(arr, l, p - 1) [Previous line repeated 981 more times] File "script.py", line 19, in sort p = generate_partition(arr, l, h) File "script.py", line 8, in generate_partition for j in range(l, h): RecursionError: maximum recursion depth exceeded in comparison	0.49 s	15 KBi
#25	Error en tiempo de ejecución (NZEC) Exited with error status 1 Traceback (most recent call last): File "script.py", line 25, in <module> sort(arr, 0, n - 1) File "script.py", line 21, in sort sort(arr, p + 1, h) File "script.py", line 21, in sort sort(arr, p + 1, h) File "script.py", line 21, in sort sort(arr, p + 1, h) [Previous line repeated 9 more times] File "script.py", line 20, in sort sort(arr, l, p - 1) File "script.py", line 20, in sort sort(arr, l, p - 1) File "script.py", line 20, in sort sort(arr, l, p - 1) [Previous line repeated 981 more times] File "script.py", line 19, in sort p = generate_partition(arr, l, h) File "script.py", line 8, in generate_partition for j in range(l, h): RecursionError: maximum recursion depth exceeded in comparison	0.506 s	15 KBi
#26	Tiempo límite excedido	0.687 s	14 KBi
#27	Tiempo límite excedido	0.648 s	14 KBi

Puntos totales: 30 / 100

Código

def swap(arr, i, j):
  arr[i], arr[j] = arr[j], arr[i]

def generate_partition(arr, l, h):
  i = l - 1
  p = arr[h]
  
  for j in range(l, h):
    if arr[j] <= p:
      i = i + 1
      swap(arr, i, j)
  swap(arr, i + 1, h)
  return i + 1

def sort(arr, l, h):
  if len(arr) == 1:
    return arr
  if (l < h):
    p = generate_partition(arr, l, h)
    sort(arr, l, p - 1)
    sort(arr, p + 1, h)

n = int(input())
arr = [int(x) for x in input().split(" ")]
sort(arr, 0, n - 1)
for i in arr:
  print(i, end = " ")