uHunt

uHunt는 "UVa Hunting"을 줄인 이름이다. UVa 온라인 저지에서 내가 어떤 문제를 풀었는지 기록해 두고, 통계와 다음에 풀 만한 문제 목록을 보여 주는 도구다.

이 사이트는 내 동생 Felix Halim이 만들었다. UVa 온라인 저지에는 지금까지 제출이 약 900만 건 쌓였고(몇 초에 한 건꼴이다), 서로 다른 문제가 약 3000개, 사용자가 약 12만 명 있다. 실제로 활동하는 사람은 아마 수천 명 정도일 것이다. 동생은 모든 기능이 "즉시" 끝나도록 이 도구를 아주 강하게 최적화해야 했다.

이 문제에서는 uHunt의 기능 중 정답 제출 순위를 즉시 갱신하는 부분 하나만 다룬다. UVa 온라인 저지가 매기는 값 가운데 하나는 정답 코드가 저지 데이터와 저지 머신에서 걸린 실행 시간이다. 문제 번호가 100인 경우를 보자. 이 문제에는 이미 정답 제출이 네 개 있고 순위는 다음과 같다.

이제 사용자 you가 100번 문제에 정답 코드를 제출했고 실행 시간이 0.127초로 측정되면, you가 새로운 3위가 되고 felix와 steven은 각각 4위와 5위로 밀린다. you의 기록이 nhahtdh와 같지만, 그 기록을 먼저 세운 nhahtdh가 앞선다.

you가 3위에 만족하지 못하고 100번 문제의 코드를 고쳐서 다시 제출했다고 하자. 구현을 더 손본 새 코드가 0.115초를 받으면 you가 새로운 1위가 되고 josh와 nhahtdh는 각각 2위와 3위로 밀린다. felix와 steven은 4위와 5위 그대로다.

여기서 다른 사용자 grace가 100번 문제에 3.475초짜리 정답 코드를 제출하면 순위는 이렇게 된다.

you가 프로그램을 더 만지다가 100번 문제에 0.121초짜리 정답 코드를 또 제출했다고 하자. 이 기록은 you 자신의 기존 최고 기록보다 느리다. 저지는 이런 제출을 무시하므로 순위는 바로 위 표 그대로 남는다.

첫째 줄에 제출 개수 $n$ ($1 \le n \le 50000$)이 주어진다. 제출은 제출한 시각 순으로 정렬되어 있고, 주어진 순서대로 하나씩 처리해야 한다.

다음 $n$개 줄에는 제출 하나마다 problem_id, user_id, t가 공백 하나로 구분되어 주어진다. problem_id는 100 이상 199 이하의 세 자리 정수다. user_id는 0000 이상 9999 이하의 네 자리 정수이고 앞자리를 0으로 채워서 준다. t는 사용자 user_id가 문제 problem_id에 낸 정답 코드의 실행 시간이며, 소수점 아래 세 자리를 항상 채운 d.ddd 형식으로 0.000 이상 9.999 이하다. 모든 문제의 시간 제한이 10초 미만이라 t가 9.999를 넘는 일은 없다.

입력의 각 줄을 읽을 때마다 곧바로 한 줄을 출력한다.

그 제출의 실행 시간이 같은 사용자가 같은 문제에서 이미 세운 최고 기록보다 느리거나 같으면 submission ignored만 출력하고, 이 제출은 순위에 반영하지 않는다.

그렇지 않으면 다섯 값을 공백 하나로 구분해 출력한다. 앞의 세 값 problem_id, user_id, t는 입력에 있던 형식 그대로 다시 쓴다. 네 번째 값은 이 제출을 반영한 뒤 이 문제에서 1위인 사용자의 실행 시간이고, 다섯 번째 값은 이 제출을 반영한 뒤 이 사용자의 순위다. 실행 시간 두 개는 모두 d.ddd 형식으로 쓴다.

순위는 그 문제에서 정답을 받은 사용자를 각자의 최고 기록 오름차순으로 줄 세워 매긴다. 최고 기록이 같으면 그 기록을 먼저 세운 제출이 앞선다.