Editorial for Bảng Xếp Hạng
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]: badictlư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ộtsetchứa các cặp(ten, bai)đãAC.
Với mỗi lượt nộp (t, ten, bai, kq):
- Nếu
(ten, bai)đã nằm trongda_ac→ bỏ qua (luật 1). - Nếu
kq == "AC"→ thêm vàoda_ac, tăng số bài, cộng phạtt + 20 * sai_truoc_ac[(ten, bai)], và ghiac_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. - Nếu
kqlàCE→ không làm gì. - 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