Problem E: Help Your Teacher

Time Limit: 1 Sec  Memory Limit: 32 MB
Submit: 137  Solved: 84
[Submit][Status][Web Board]


You are a good student, when your teacher needs help you will be the first one that helps him. Now after the final examination, everyone has two kinds of scores, Math and English. You know nowadays English is very important, so the teacher will arrange your scores firstly according to your English score, then, according to Math. Now there are N(1<=N<=100000) students, everybody has his own scores and name .The teacher will ask you who is the Kth student after arranging them by score. We ensure that there are no two students have the same scores.


There are several tests.

In the first line there is two integers N , Q , represent there are N students and the teacher will ask Q (1<=Q<=1000) times . Then N lines follow, each line has three parts, the student’s name (the length is no longer than 20) the Math score and the English score (the scores are between 1 and 1000).Then following Q lines, each line contains a number K (1<=K<=N), means the teacher ask you the name of the Kth student after arranging them by scores.


There are Q lines of each test case; each line contains the answer of the teacher’s question.

Sample Input

5 3abcde 100 200defg 150 300hyzd 260 150pku 50 400heu 500 500123

Sample Output




#include <stdio.h>
#include <string.h>

long n;

char name[100010][22];
int E[100010], M[100010];

void swap(int i, int j)
int t;
char b[22];
t = E[i];
E[i] = E[j];
E[j] = t;
t = M[i];
M[i] = M[j];
M[j] = t;
strcpy(b, name[i]);
strcpy(name[i], name[j]);
strcpy(name[j], b);

int main()
long q, tmp, i, j, k;
scanf("%ld%ld", &n, &q);
for (i=1;i<=n;++i)
scanf("%s%d%d", name[i], &M[i], &E[i]);
j = 1;
while (((E[j]>E[i]) || ((E[j] == E[i]) && (M[j]>M[i]))) && j<=i-1)
for (k=i;k>=j+1;--k)
swap(k,k - 1);
for (i=0;i<q;++i)
scanf("%ld", &tmp);
printf("%s\n", name[tmp]);
return 0;