uHunt
Для тих, хто не знає, uHunt означає "UVa Hunting". Це інструмент для UVa online-judge, який відстежує, які задачі ви розв'язали, надає статистику та пропонує кілька варіантів для наступної задачі.
Цей вебсайт створений моїм братом Феліксом Халімом. Зважаючи на те, що UVa online-judge має близько 9 мільйонів відправок (приблизно одна відправка кожні кілька секунд), близько 3000 різних задач з програмування та близько 120000 різних користувачів (ймовірно, лише тисячі з них зараз активні), мій брат мусить сильно оптимізувати цей інструмент, щоб усі його функції працювали "миттєво".
У цій задачі ми зосередимося на невеликій підмножині функцій uHunt, а саме на "миттєвому перерейтингу прийнятих відправок". Один з параметрів, який ранжується в UVa online judge, - це швидкість виконання прийнятої відправки на даних судді та машині судді. Припустимо, ми маємо справу з problem_id "100". Раніше було 4 прийнятих відправки для цієї задачі з наступними рейтингами у такому форматі: (ранг, ім'я_користувача, швидкість_виконання_в_секундах):
1. josh 0.120 2. nhahtdh 0.127 3. felix 0.223 4. steven 0.323
Тепер, якщо користувач "you" відправляє прийнятий код для problem_id "100" і цей код оцінюється як такий, що має швидкість виконання 0.127s, тоді "you" буде розміщено на новому ранзі 3, а "felix" та "steven" будуть знижені до рангу 4 та 5 відповідно. Зверніть увагу, що хоча "you" має такий же результат, як і "nhahtdh", "you" буде ранжовано після "nhahtdh", який відправив свій прийнятий код раніше.
1. josh 0.120 2. nhahtdh 0.127 3. you 0.127 4. felix 0.223 5. steven 0.323
Припустимо, користувач "you" не задоволений отриманим рангом 3 і вирішує покращити свій прийнятий код для problem_id "100". Після повторної відправки його новий код (який містить більше реалізаційних хитрощів) оцінюється як такий, що має швидкість виконання 0.115s, тоді "you" буде розміщено на новому ранзі 1, а "josh" та "nhahtdh" будуть знижені до рангу 2 та 3 відповідно. Зверніть увагу, що "felix" та "steven" залишаються на рангах 4 та 5 відповідно.
1. you 0.115 2. josh 0.120 3. nhahtdh 0.127 4. felix 0.223 5. steven 0.323
Якщо інший користувач "grace" відправляє прийнятий код для problem_id "100" зі швидкістю виконання 3.475s, тоді новий рейтинг буде:
1. you 0.115 2. josh 0.120 3. nhahtdh 0.127 4. felix 0.223 5. steven 0.323 6. grace 3.475
Припустимо, після подальших змін у своєму програмі, користувач "you" відправляє ще один прийнятий код для problem_id "100" зі швидкістю виконання 0.121s. Оскільки це фактично повільніше, ніж його попередній найкращий результат, UVa online judge (і uHunt) "ігнорує" цю відправку. Рейтинг залишається:
1. you 0.115 2. josh 0.120 3. nhahtdh 0.127 4. felix 0.223 5. steven 0.323 6. grace 3.475
Вхідні дані
Перша строка введення - це n (1 ≤ n ≤ 50000), кількість відправок, відсортованих за часом відправки. Ви повинні обробити ці відправки одну за одною.
Далі буде n рядків з трьома числами: problem_id, user_id та t.
problem_id - це 3-значне ціле число номерів задач у діапазоні [100-199].
user_id - це 4-значне ціле число ідентифікаційного номера програміста у діапазоні [0000-9999].
t - це дійсне число з не більше ніж 3 знаками після коми.
Ви можете бути впевнені, що t не буде більшим за 9.999 (оскільки обмеження часу для всіх задач менше 10 секунд). Це t - це швидкість виконання прийнятих кодів користувача user_id для задачі problem_id.
Вихідні дані
Для кожного рядка введення негайно виведіть п'ять чисел, розділених одним пробілом:
problem_id, user_id та t - ці три такі ж, як у введенні, а потім:
best_t_for_this_problem_id, і нарешті:
rank_of_user_id_for_this_problem_id
best_t_for_this_problem_id визначається як швидкість виконання прийнятого коду, відправленого найкращим програмістом (який наразі на ранзі 1) для цієї конкретної задачі.
rank_of_user_id_for_this_problem_id визначається як рейтинг поточного програміста для цієї конкретної задачі, як описано в умові задачі вище.
Однак, якщо ця відправка від певного користувача фактично повільніша або дорівнює його попередньому найкращому результату, тоді виведіть: "submission ignored" (без лапок) в одному рядку замість цього.