Bảng Xếp Hạng

Time limit: 1.0s Memory limit: 256M Read editorial

Problem

Câu lạc bộ lập trình tổ chức cuộc thi "Đêm Trăng Code" theo đúng luật ICPC. Mọi thứ diễn ra suôn sẻ cho tới phút cuối cùng, khi Khoa (vẫn là Khoa của vụ treo đèn lồng) vấp phải sợi dây điện và làm sập máy chủ bảng xếp hạng. Lễ trao giải sắp bắt đầu, may mắn là nhật ký nộp bài vẫn còn nguyên. Ban tổ chức nhờ bạn dựng lại bảng xếp hạng.

Cuộc thi có \(n\) đội và \(m\) bài tập, các bài được đặt tên bằng \(m\) chữ cái in hoa đầu tiên A, B, C, .... Mỗi dòng nhật ký có dạng "phút \(t\), đội nào, nộp bài nào, kết quả gì". Kết quả là một trong các loại sau:

  • AC: lời giải đúng.
  • WA, TLE, MLE, RTE: lời giải bị từ chối.
  • CE: lỗi biên dịch. Lượt nộp này không được tính gì cả, không phạt cũng không thưởng.

Luật tính điểm như sau:

  1. Một đội giải được một bài nếu có ít nhất một lần nộp AC cho bài đó. Chỉ lần AC đầu tiên được tính, mọi lượt nộp bài đó sau lần AC đầu tiên đều bị bỏ qua.
  2. Với mỗi bài giải được, đội bị cộng thời gian phạt bằng: phút có lần AC đầu tiên, cộng thêm \(20\) phút cho mỗi lần bị từ chối ở bài đó trước lần AC đầu tiên.
  3. Những bài không giải được thì không bị tính thời gian phạt, dù đội đã nộp sai bao nhiêu lần.
  4. Đội giải được nhiều bài hơn xếp trên. Nếu số bài bằng nhau, đội có tổng thời gian phạt ít hơn xếp trên.
  5. Nếu vẫn bằng nhau, đội có lần AC cuối cùng sớm hơn xếp trên. "Lần AC cuối cùng" của một đội là thời điểm muộn nhất trong các lần AC được tính của đội đó. Đội chưa giải được bài nào thì coi thời điểm này bằng \(0\).
  6. Nếu hai đội bằng nhau cả ba tiêu chí trên thì hai đội đồng hạng. Hạng của một đội bằng \(1\) cộng với số đội xếp trên hẳn đội đó. Ví dụ nếu có hai đội cùng hạng \(1\) thì đội tiếp theo xếp hạng \(3\).

Khi in bảng xếp hạng, các đội đồng hạng được in theo thứ tự từ điển tăng dần của tên (so sánh theo mã ASCII, giống phép so sánh chuỗi mặc định của Python).

"Bảng xếp hạng có thể sập, nhưng nhật ký thì không bao giờ nói dối."

-- Trưởng ban tổ chức, tay vẫn cầm cuộn băng dính

Input

  • Dòng đầu tiên gồm ba số nguyên \(n, m, s\) \((1 \leq n \leq 10^4, 1 \leq m \leq 26, 0 \leq s \leq 2 \times 10^5)\) lần lượt là số đội, số bài và số lượt nộp.
  • \(n\) dòng tiếp theo, mỗi dòng là tên một đội. Tên gồm từ \(1\) đến \(20\) ký tự, chỉ chứa chữ cái in thường, chữ số và dấu gạch dưới _. Các tên đôi một khác nhau.
  • \(s\) dòng tiếp theo mô tả các lượt nộp theo đúng thứ tự thời gian, mỗi dòng gồm:
    • số nguyên \(t\) \((0 \leq t \leq 300)\) là phút nộp bài;
    • tên đội nộp bài (luôn là một trong \(n\) đội đã cho);
    • tên bài (một trong \(m\) chữ cái in hoa đầu tiên);
    • kết quả (AC, WA, TLE, MLE, RTE hoặc CE).
    </li>
  • Các giá trị \(t\) không giảm. Nếu nhiều lượt nộp cùng một phút thì lượt nào xuất hiện trước trong input được coi là xảy ra trước.
  • </ul>

    Output

    • In ra \(n\) dòng là bảng xếp hạng từ trên xuống dưới. Mỗi dòng gồm: hạng, tên đội, số bài giải được, tổng thời gian phạt, cách nhau bởi dấu cách.

    Sample

    #InputOutput
    1
    3 3 8
    alpha
    beta
    gamma
    5 alpha A WA
    10 alpha A AC
    12 beta A CE
    15 beta A AC
    20 gamma B WA
    30 alpha B AC
    40 beta B AC
    45 alpha B WA
    1 beta 2 55
    2 alpha 2 60
    3 gamma 0 0
    2
    4 2 5
    dory
    nemo
    marlin
    bruce
    3 nemo A AC
    3 dory A AC
    7 nemo B TLE
    50 dory B RTE
    60 marlin A WA
    1 dory 1 3
    1 nemo 1 3
    3 bruce 0 0
    3 marlin 0 0

    Note

    Sample 1:

    • alpha: bài A bị WA ở phút \(5\) rồi AC ở phút \(10\), phạt \(10 + 20 = 30\). Bài B AC ở phút \(30\), phạt \(30\). Lần WA ở phút \(45\) xảy ra sau khi đã AC nên bị bỏ qua. Tổng: \(2\) bài, \(60\) phút.
    • beta: bài A bị CE (không tính) rồi AC ở phút \(15\). Bài B AC ở phút \(40\). Tổng: \(2\) bài, \(55\) phút.
    • gamma: chỉ có một lần WA ở bài chưa giải được, không bị phạt. Tổng: \(0\) bài, \(0\) phút.

    beta và alpha cùng giải \(2\) bài nhưng beta ít thời gian phạt hơn nên đứng trên.

    Sample 2: dory và nemo cùng giải \(1\) bài với \(3\) phút phạt, lần AC cuối cùng của cả hai đều ở phút \(3\), nên cùng hạng \(1\) và được in theo thứ tự tên. Hai lần nộp sai của họ ở bài B không bị phạt vì bài B chưa được giải. Đứng sau là bruce (không nộp bài nào) và marlin, cùng \(0\) bài và \(0\) phút phạt, nên cùng hạng \(3\) chứ không phải hạng \(2\).

    Ví dụ về luật 5 (không phải test mẫu): đội x giải bài A ở phút \(10\) và bài B ở phút \(50\), đội y giải cả hai bài ở phút \(30\). Cả hai đội cùng \(2\) bài và cùng \(60\) phút phạt, nhưng lần AC cuối cùng của y (phút \(30\)) sớm hơn của x (phút \(50\)), nên y xếp hạng \(1\) còn x xếp hạng \(2\).


Comments

There are no comments at the moment.

Code editor