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" (без кавычек) в одной строке вместо этого.