Сокращение времени работы программмы

Question

Всем привет! При выполнении задачи я попадаю в time limit, а идей по сокращению времени/кода так и не появилось. Дайте совет/подсказку, в какую сторону думать, пожалуйста)

Входные данные: Первая строка - целое число n. В следующих n строках - пары целых чисел через табуляцию(уникальный ID≤10^6 и параметр≤10^9).

Задача - отсортировать входные данные по невозрастанию параметра, причём сортировка должна быть устойчивой (при равенстве параметров сохраняется порядок ID)

Ограничение памяти: 64 Mb

Ограничение времени: 1 секунда

Вывод: n пар чисел через tab, каждая пара в новой строке.

Код:

n = int(input())
c = input().split()
for i in range(1, n):
    a, b = input().split()
    if int(b) > int(c[1]):
        c.insert(0, b)
        c.insert(0, a)
    elif int(b) <= int(c[len(c) - 1]):
        c.append(a)
        c.append(b)
    else:
        for j in range(0, len(c) - 3):
            if int(b) <= int(c[j + 1]) and int(b) > int(c[j + 3]):
                c.insert(j + 2, b)
                c.insert(j + 2, a)
                break
for i in range(0, (len(c) // 2), 1):
    print(c[2 * i],  c[2 * i + 1], sep = '\t')

Ввод и вывод:

Answer 1

Встроенная в Python сортировка (sort, sorted) является устойчивой (по крайней мере с версии 2.2), поэтому нужно её и применить с ключом по второму элементу кортежа (в кортежах пары (id,par))

sorted(l, key=lambda x: x[1])

Если по какой-то причине встроенный sort не дозволяется, то нетрудно сделать сортировку слиянием (mergesort)

БЛОГ НА HUSL

Сокращение времени работы программмы

Ответы (1 шт):