Description

Writer: jjjjj19980806       Description: pclightyear        Difficulty: ★★★☆☆

As you all know, Kim Jong-un is the Chairman of the Workers' Party of Korea and supreme leader of North Korea. Over the past two years, the automobile industry in North Korea has been suffering from severe depression. The supreme leader thus decides to reorganize the whole industry to make North Korea GREAT AGAIN.

According to the survey, there are n factory in North Korea. Each of them can produce two kinds of cars (car A & car B). Now, the supreme leader wants to assign x factory to produce car A and y factory to produce car B (i.e. no factory will produce two kinds of car at the same time.) so that the net profit will become maximum. 

Although the supreme leader is absolutely smart enough to write a program by himself, he doesn't want to waste time on this little tiny thing. The supreme leader will thus give you the net profit each factory can make by producing car A and car B. Your program need to distribute x factory to produce car A and list their name in lexicographical order.

DO NOT DISAPPOINT HIM!!

Input

The first line contains three integers n, x, y, representing the total number of factory, the number of factory planned to produce car A, and the number of factory planned to produce car B. (according to the supreme leader's demand)

The next n lines contains one string s_i and two integers a_i, b_i, representing the name of each factory, and the net profit each factory can make by producing only car A or only car B.

It is guaranteed that :

• 0 < n, x, y < 10⁵
• x + y = n
• 1 ≤ | s_i | ≤ 20
• 0 < a_i, b_i < 10⁹
• No duplicate names appears.
• The answer will be unique.

Output

Please output the list of x factory that need to produce car A in lexicographical order so that it will maximum the net profit.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

In out class, HT Chen introduced a way to implement a qsort-like mysort using bubble sort. 

To make you more clearly to the machism, you are asked to implement a qsort-like mysort using insertion sort.

The main function has already provided for you, what you have to do is just implement the mysort function.

For more specific, you just need to fill the following blank:

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b)
{
    // compare a with b
}


void assign(char* x, char* y, size_t size) {
   // assign y to x
}

void mysort(void* arr, size_t count, size_t size, int (*cmp) (const void*, const void*))
{
    // do sorting!!!
}

 

The pseudo code below would be helpful if you want to know how the insertion sort works.

i ← 1
while i < length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
    i ← i + 1
end while

 

Input

There are 2 lines input.

The first line contains a integer, indicating the total number of integers would be sorted.

The second line consists of the integers being sorted.

Output

The integers have been sorted.

Please notice that the sequence has to be in ascending order.

Sample Input  Download

Sample Output  Download

Partial Judge Code

11752.c

Partial Judge Header

11752.h

Tags

Discuss