Editorial for Bảng Xếp Hạng


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Nghaiz

Lời giải: Bảng Xếp Hạng

Chủ đề: lists + tuples (sắp xếp theo khóa là tuple), có dùng thêm dict, set

Tóm tắt đề

Cho nhật ký nộp bài theo luật ICPC. Tính số bài, thời gian phạt và thời điểm AC cuối cùng của từng đội, rồi in bảng xếp hạng: nhiều bài hơn đứng trên, cùng số bài thì ít phạt hơn đứng trên, vẫn bằng thì AC cuối sớm hơn đứng trên, bằng cả ba thì đồng hạng và in theo tên.

Bước 1: tính điểm từng đội

Duyệt nhật ký một lần từ trên xuống, dùng:

  • so_bai[ten], penalty[ten], ac_cuoi[ten]: ba dict lưu kết quả của mỗi đội;
  • sai_truoc_ac[(ten, bai)]: số lần bị từ chối của đội ở bài đó cho tới hiện tại;
  • da_ac: một set chứa các cặp (ten, bai) đã AC.

Với mỗi lượt nộp (t, ten, bai, kq):

  1. Nếu (ten, bai) đã nằm trong da_ac → bỏ qua (luật 1).
  2. Nếu kq == "AC" → thêm vào da_ac, tăng số bài, cộng phạt t + 20 * sai_truoc_ac[(ten, bai)], và ghi ac_cuoi[ten] = t. Vì nhật ký đã theo thứ tự thời gian, lần AC được tính sau cùng chính là lần muộn nhất.
  3. Nếu kq là CE → không làm gì.
  4. Còn lại (bị từ chối) → tăng sai_truoc_ac[(ten, bai)].

Chú ý rằng số lần sai chỉ được "đổi thành phạt" tại thời điểm AC. Bài nào không bao giờ AC thì số lần sai của nó không bao giờ được cộng vào, đúng như luật 3.

Dùng tuple (ten, bai) làm khóa của dict/set là một kỹ thuật rất hay gặp: tuple không thay đổi được (immutable) nên hash được, còn list thì không.

Bước 2: sắp xếp bằng tuple

Python so sánh tuple từng phần tử từ trái sang phải. Ta muốn:

  • số bài giảm dần → dùng -so_bai;
  • phạt tăng dần → dùng penalty;
  • AC cuối tăng dần → dùng ac_cuoi;
  • tên tăng dần → dùng ten.
bang = sorted((-so_bai[ten], penalty[ten], ac_cuoi[ten], ten) for ten in doi)

Một dòng duy nhất, không cần viết hàm so sánh phức tạp.

Bước 3: tính hạng có đồng hạng

Duyệt bảng đã sắp xếp. Đội thứ \(i\) (đánh số từ \(0\)) có hạng \(i + 1\) nếu bộ ba (số bài, phạt, AC cuối) của nó khác đội đứng ngay trước, ngược lại nó giữ nguyên hạng của đội trước. Lưu ý: tên chỉ dùng để sắp thứ tự in, không dùng để phân hạng. Cách này cho ra dãy hạng kiểu 1, 1, 3, 3, 3, 6 như đề yêu cầu.

Độ phức tạp

Duyệt nhật ký \(O(s)\), sắp xếp \(O(n \log n)\).

Code mẫu

import sys

PHAT = 20


def main():
    data = sys.stdin.read().split()
    n, m, s = int(data[0]), int(data[1]), int(data[2])
    doi = data[3:3 + n]
    so_bai = {ten: 0 for ten in doi}
    penalty = {ten: 0 for ten in doi}
    ac_cuoi = {ten: 0 for ten in doi}
    sai_truoc_ac = {}
    da_ac = set()

    vt = 3 + n
    for _ in range(s):
        t = int(data[vt])
        ten, bai, kq = data[vt + 1], data[vt + 2], data[vt + 3]
        vt += 4
        cap = (ten, bai)
        if cap in da_ac:
            continue
        if kq == "AC":
            da_ac.add(cap)
            so_bai[ten] += 1
            penalty[ten] += t + PHAT * sai_truoc_ac.get(cap, 0)
            ac_cuoi[ten] = t
        elif kq != "CE":
            sai_truoc_ac[cap] = sai_truoc_ac.get(cap, 0) + 1

    bang = sorted((-so_bai[ten], penalty[ten], ac_cuoi[ten], ten) for ten in doi)
    kq = []
    hang = 0
    for i, dong in enumerate(bang):
        if i == 0 or dong[:3] != bang[i - 1][:3]:
            hang = i + 1
        kq.append(f"{hang} {dong[3]} {-dong[0]} {dong[1]}")
    print("\n".join(kq))


main()

Comments

There are no comments at the moment.