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