Algorithm

[shizuka]

To that end:

Timofey decided to organize a sports program competition to find talented trainees. Targets are set, participants are registered, tests are written. We have to figure out how the winner will be determined at the end of the competition.

Each participant has a unique logic. When the competition is over, two indicators will be attached to it: the number of tasks performed by the Pi and the amount of the Fi fine. The fine is calculated for failures and time spent on the task.

Timofey decided to classify the results table as follows: when compared to the two participants above, it will be the one with more tasks. If the number of tasks is equal, the first participant goes with a lower fine. If the fines match, the first will be the one with the logic going in alphabetical (electric) procedure.

Timofey ordered the winners' thicks and went to the store the other day. In his absence, he instructed you to implement the quick-grading algorithm (Angl. quick sort) for the results table. Because Timofay likes sports programming and doesn't like to waste operational memory, your exercise can't consume O(n) additional memory for intermediate data (this is sorted as "in-place."

How does it work in-place quick sort As in the case of a normal fast sorting that uses additional memory, a backbone (angl. pivot) must be selected and then the area should be adjusted. Let's make sure that the elements that do not exceed the backbone and then the big team.

The grading is then recurring for two parts received. It is during the grouping phase that the normal algorithm uses additional memory. Now we'll figure out how to take this step in-place.

Let us somehow choose the support element. We'll have two indicators left and a right that will initially indicate the left and right end of the cut, respectively. Then we move the left index to the right as long as it points to the element smaller. It's like moving the right index to the left while it's on an element above the back. As a result, the left of all the elements is exactly the first group and the right is the second. Elements on which the indexes are standing violate the order. Change their seats (the majority of the programming languages use swap()) and extend the indicators to the following elements. Let us repeat this action until the left and the right are met. The drawing gives an example of separation at pivot=5. The index left is blue, right is orange.

Introduction form In the first line the number of participants n, 1 ≤ n < 100,000. In each of the following n lines, information was provided about one participant. i The participant shall be described in three parameters:

unique login (line of small Latin letters of not more than 20 length) Number of mandated tasks Fi fine Fi and Pi are total numbers between 0 and 109. Form of withdrawal For the selected list of participants, put their logic on one line.

Example 1

Ввод           Вывод   
5              gena
alla 4 100     timofey
gena 6 1000    alla
gosha 2 90     gosha
rita 2 90      rita
timofey 4 80

The teacher asks to adjust the code: We need to write our class to show the participant. (Source: the method is sufficient in to maintain values in class attributes.) Use the method <which allows for a " less than " test.

But I don't know how to do it. Please help. Here's my code:

def quicksort(nums):
    if len(nums) <= 1:
        return nums
q = nums[len(nums) // 2]
s_nums = []
m_nums = []
e_nums = []

for n in nums:
    if n[1] &gt; q[1]:
        s_nums.append(n)
    elif n[1] &lt; q[1]:
        m_nums.append(n)
    else:
        if n[0] == q[0]:
            e_nums.append(n)
        elif n[2] != q[2]:
            s_nums.append(n) if n[2] &lt; q[2] else m_nums.append(n)
        else:
            s_nums.append(n) if n[0] &lt; q[0] else m_nums.append(n)

return quicksort(s_nums) + e_nums + quicksort(m_nums)

def main():

n = int(input())

p = []

for i in range(n):

q = list(input().split())

q[1] = int(q[1])

q[2] = int(q[2])

p.append(q)

sort = quicksort(p)

for s in sort:

print(s[0])

[courtlanda]

You just need to put the right condition in the sorting. I took a quick sorting. https://gb.ru/posts/python_sort ♪ When we compare the elements, we have to compare Pi first, then Fi and at the end of the name. I decided to use the code for purity. https://habr.com/ru/post/415829/ ♪

from dataclasses import dataclass
import random
@dataclass

class Person:

name: str

solved: int

errors: int
def __gt__(self, other):
    """
    "Больше", т.е. ниже в списке.
    У этого участника меньше Pi, больше Fi и имя в алфавите ниже.
    """
    if self.solved == other.solved:
        if self.errors == other.errors:
            return self.name > other.name
        return self.errors > other.errors
    return self.solved < other.solved

def __lt__(self, other):
    """
    "Меньше", т.е. выше в списке.
    У этого участника больше Pi, меньше Fi и имя в алфавите выше.
    """
    if self.solved == other.solved:
        if self.errors == other.errors:
            return self.name < other.name
        return self.errors < other.errors
    return self.solved > other.solved

def quicksort(nums, left, right):

if left >= right:

return
i, j = left, right

pivot = nums[random.randint(left, right)]
while i <= j:

while nums[i] < pivot:

i += 1

while nums[j] > pivot:

j -= 1
   if i &lt;= j:
       nums[i], nums[j] = nums[j], nums[i]
       i, j = i + 1, j - 1

quicksort(nums, left, j)

quicksort(nums, i, right)
def main():

n = int(input())

persons = []

for _ in range(n):

name, solved, errors = input().split()

persons.append(

Person(name, int(solved), int(errors))

)
quicksort(persons, 0, n - 1)
for person in persons:
    print(person.name)

main()