uHunt#2544
Bilməyənlər üçün, uHunt "UVa Hunting" üçün bir vasitədir və UVa online-judge platformasında hansı problemləri həll etdiyinizi izləyir, statistikalar təqdim edir və növbəti həll üçün seçimlər təklif edir.
Bu veb sayt qardaşım Felix Halim tərəfindən yaradılıb. İndiyə qədər UVa online-judge təxminən 9 milyon təqdimat (təxminən hər bir neçə saniyədə bir təqdimat), təxminən 3000 fərqli proqramlaşdırma problemi və təxminən 120000 fərqli istifadəçi (ehtimal ki, yalnız minlərlə hazırda aktivdir) olduğu nəzərə alınaraq, qardaşım bu vasitəni yüksək dərəcədə optimallaşdırmalıdır ki, bütün xüsusiyyətləri "bir anda" işləsin.
Bu məsələdə biz uHunt xüsusiyyətinin kiçik bir alt dəstəsinə, "qəbul edilmiş təqdimatların dərhal yenidən sıralanmasına" diqqət yetirəcəyik. UVa online judge-də sıralanan parametrlərdən biri qəbul edilmiş təqdimatın hakim məlumatlarında və hakim maşınında işləmə sürətidir. Tutaq ki, biz "100" problem_id ilə məşğuluq. Əvvəlcə bu problem üçün aşağıdakı sıralamada 4 qəbul edilmiş təqdimat var idi: (sıra, istifadəçi adı, saniyələrdə işləmə sürəti):
1. josh 0.120 2. nhahtdh 0.127 3. felix 0.223 4. steven 0.323
İndi əgər "you" istifadəçisi "100" problem_id üçün qəbul edilmiş kod təqdim edərsə və bu kodun işləmə sürəti 0.127s olaraq qiymətləndirilərsə, onda "you" yeni 3 sırada yerləşdiriləcək və "felix" və "steven" müvafiq olaraq 4 və 5 sıraya endiriləcək. Qeyd edək ki, "you" "nhahtdh" ilə eyni olsa da, "you" daha əvvəl qəbul edilmiş kodunu təqdim edən "nhahtdh"dən sonra sıralanacaq.
1. josh 0.120 2. nhahtdh 0.127 3. you 0.127 4. felix 0.223 5. steven 0.323
Tutaq ki, "you" istifadəçisi 3 sırada olmaqdan məmnun deyil və "100" problem_id üçün qəbul edilmiş kodunu təkmilləşdirməyi seçir. Yenidən təqdim etdikdən sonra, daha çox implementasiya hiyləsi olan yeni kodu 0.115s işləmə sürəti ilə qiymətləndirilirsə, onda "you" yeni 1 sırada yerləşdiriləcək və "josh" və "nhahtdh" müvafiq olaraq 2 və 3 sıraya endiriləcək. Qeyd edək ki, "felix" və "steven" müvafiq olaraq 4 və 5 sırada qalır.
1. you 0.115 2. josh 0.120 3. nhahtdh 0.127 4. felix 0.223 5. steven 0.323
Əgər başqa bir istifadəçi "grace" "100" problem_id üçün qəbul edilmiş kod təqdim edərsə və işləmə sürəti 3.475s olarsa, yeni sıralama belə olacaq:
1. you 0.115 2. josh 0.120 3. nhahtdh 0.127 4. felix 0.223 5. steven 0.323 6. grace 3.475
Tutaq ki, proqramı ilə daha çox işlədikdən sonra "you" istifadəçisi "100" problem_id üçün başqa bir qəbul edilmiş kod təqdim edir və işləmə sürəti 0.121s olur. Bu, əslində onun əvvəlki ən yaxşısından daha yavaş olduğuna görə, UVa online judge (və uHunt) bu təqdimatı "yox sayır". Sıralama belə qalır:
1. you 0.115 2. josh 0.120 3. nhahtdh 0.127 4. felix 0.223 5. steven 0.323 6. grace 3.475
Girişin ilk sətiri təqdimatların sayı olan n (1 \leq n \leq 50000) olacaq, təqdimat vaxtına görə sıralanmışdır. Bu təqdimatları bir-bir emal etməlisiniz.
Sonra, n sətir üç rəqəmdən ibarət olacaq: problem_id, user_id və t.
problem_id 3 rəqəmli tam ədəd olub, [100-199] aralığında olur.
user_id 4 rəqəmli tam ədəd olub, [0000-9999] aralığındadır.
t ondalık nöqtədən sonra ən çox 3 rəqəm olan real ədəddir.
Əmin ola bilərsiniz ki, t -dan böyük olmayacaq (bütün problemlər üçün vaxt məhdudiyyəti saniyədir). Bu t istifadəçi user_id tərəfindən problem_id problemi üçün qəbul edilmiş kodların işləmə sürətidir.
Girişin hər sətiri üçün dərhal beş rəqəm çıxış edin, bir boşluqla ayrılmış:
problem_id, user_id, t — bunlar girişdəki ilə eynidir, sonra isə:
best_t_for_this_problem_id, və nəhayət
rank_of_user_id_for_this_problem_id
best_t_for_this_problem_id bu xüsusi problem üçün ən yaxşı proqramçı (hazırda sırada olan) tərəfindən təqdim edilmiş qəbul edilmiş kodun işləmə sürəti kimi təyin edilir.
rank_of_user_id_for_this_problem_id bu xüsusi problem üçün cari proqramçının sıralaması olaraq yuxarıda təsvir edildiyi kimi müəyyən edilir.
Lakin, əgər müəyyən bir istifadəçinin təqdimatı əslində onun əvvəlki ən yaxşısından daha yavaş və ya bərabərdirsə, onda: "submission ignored" (sitatlar olmadan) bir sətirdə çıxış edin.
Nümunə 1