Эффективная быстрая сортировка

Тимофей решил организовать соревнование по спортивному программированию, чтобы найти талантливых стажёров. Задачи подобраны, участники зарегистрированы, тесты написаны. Осталось придумать, как в конце соревнования будет определяться победитель.

Каждый участник имеет уникальный логин. Когда соревнование закончится, к нему будут привязаны два показателя: количество решённых задач P_i и размер штрафа F_i. Штраф начисляется за неудачные попытки и время, затраченное на задачу.

Тимофей решил сортировать таблицу результатов следующим образом: при сравнении двух участников выше будет идти тот, у которого решено больше задач. При равенстве числа решённых задач первым идёт участник с меньшим штрафом. Если же и штрафы совпадают, то первым будет тот, у которого логин идёт раньше в алфавитном (лексикографическом) порядке.

Тимофей заказал толстовки для победителей и накануне поехал за ними в магазин. В своё отсутствие он поручил вам реализовать алгоритм быстрой сортировки (англ. quick sort) для таблицы результатов. Так как Тимофей любит спортивное программирование и не любит зря расходовать оперативную память, то ваша реализация сортировки не может потреблять O(n) дополнительной памяти для промежуточных данных (такая модификация быстрой сортировки называется «in-place»).

Формат ввода

В первой строке задано число участников n, 1 ≤ n ≤ 100 000.

В каждой из следующих n строк задана информация про одного из участников.

i-й участник описывается тремя параметрами:

• уникальным логином (строкой из маленьких латинских букв длиной не более 20)
• числом решённых задач P_i
• штрафом F_i

F_i и P_i — целые числа, лежащие в диапазоне от 0 до 10⁹.

Формат вывода

Для отсортированного списка участников выведите по порядку их логины по одному в строке.

def partition(competitors, left, right):
    pivot = (competitors[left])
    i = left + 1
    j = right - 1
    while True:
        if (i <= j and competitors[j] > pivot):
            j -= 1
        elif (i <= j and competitors[i] < pivot):
            i += 1
        elif (competitors[j] > pivot) or (competitors[i] < pivot):
            continue
        if i <= j:
            competitors[i], competitors[j] = competitors[j], competitors[i]
        else:
            competitors[left], competitors[j] = competitors[j], competitors[left]
            return j


def quick_sort(competitors, left, right):
    if ((right - left) > 1):
        p = partition(competitors, left, right)
        quick_sort(competitors, left, p)
        quick_sort(competitors, p + 1, right)


def transformation(competitors):
    competitors[1] = - int(competitors[1])
    competitors[2] = int(competitors[2])

    return [competitors[1], competitors[2], competitors[0]]


if __name__ == '__main__':
    number = int(input())
    competitors = [transformation(input().split()) for _ in range(number)]
    left = 0
    quick_sort(competitors, left, len(competitors))
    print(*(list(zip(*competitors))[2]), sep="\n")