Hợp nhất hồ sơ sinh viên theo độ tin cậy

Bối cảnh

Một hệ thống nhận n bản ghi cập nhật sinh viên từ nhiều nguồn. Mỗi record có id, sourcePriority, timestamp, gpa. Cùng một ID có thể xuất hiện nhiều lần. Bản ghi "đáng tin" hơn được chọn theo thứ tự: sourcePriority lớn hơn; nếu hòa, timestamp mới hơn; nếu vẫn hòa, GPA lớn hơn. Sau khi hợp nhất, cần in đúng một record cho mỗi ID, theo GPA giảm dần; tie GPA thì ID tăng dần.

Bài Advanced mô phỏng conflict resolution thường gặp trong hệ thống dữ liệu. Học viên phải tách hai comparator logic khác nhau: comparator chọn record tốt nhất trong cùng ID và comparator xếp hạng sau merge. Không được trộn hai quy tắc vào một sort duy nhất vì chúng trả lời hai câu hỏi khác nhau.

Ngoài kết quả số học, bài còn kiểm tra việc mỗi thực thể được giữ dưới dạng một record nhất quán: các field phải luôn đi cùng nhau qua bước đọc, lọc, thống kê hoặc sắp xếp. Khi thiết kế lời giải, nên xác định rõ record gốc và record/aggregate suy ra để tránh dùng nhiều mảng song song làm lệch dữ liệu.

Ngoài kết quả số học, bài còn kiểm tra việc mỗi thực thể được giữ dưới dạng một record nhất quán: các field phải luôn đi cùng nhau qua bước đọc, lọc, thống kê hoặc sắp xếp. Khi thiết kế lời giải, nên xác định rõ record gốc và record/aggregate suy ra để tránh dùng nhiều mảng song song làm lệch dữ liệu.

Yêu cầu

1. Dùng struct Record.
2. Với mỗi ID chọn record tốt nhất theo priority → timestamp → gpa.
3. Sau merge, sort record thắng theo gpa giảm → id tăng.
4. In id priority timestamp gpa(2).

Input

Dòng 1 n; n dòng id priority timestamp gpa.

Output

Mỗi ID một dòng.

Ràng buộc

1≤n≤10000, timestamp, priority không âm.

Ví dụ 1

Input

7
S1 1 100 3.0
S1 2 90 2.5
S2 1 50 4.0
S2 1 60 3.5
S3 2 100 3.7
S3 2 100 3.8
S4 1 1 3.8

Output

S3 2 100 3.80
S4 1 1 3.80
S2 1 60 3.50
S1 2 90 2.50

Giải thích

S1 chọn priority2 dù timestamp90 cũ hơn record priority1. S2 cùng priority1 nên chọn timestamp60 GPA3.5. S3 priority/time hòa, chọn GPA3.8. S4 giữ3.8. Sau merge, GPA cao nhất 3.8 có S3 và S4 nên ID S3<S4; tiếp theo S2 3.5 rồi S1 2.5.

Ví dụ này đồng thời kiểm tra rằng các field của cùng một record không bị lệch khi duyệt hoặc sắp xếp. Quy tắc tie-break/giữ thứ tự chỉ được áp dụng sau khi dữ liệu cần so sánh đã được xác định đúng, nên kết quả trên là hệ quả trực tiếp của state record sau xử lý.

Ví dụ 2

Input

4
A 1 1 2.0
A 1 1 3.0
B 2 1 3.0
C 0 10 4.0

Output

C 0 10 4.00
A 1 1 3.00
B 2 1 3.00

Giải thích

A có hai record cùng priority/time nên chọn GPA3.0. B có priority2 GPA3.0. C GPA4.0. Ranking cuối C trước, rồi A/B cùng GPA3 nhưng ID A<B.

Ví dụ này đồng thời kiểm tra rằng các field của cùng một record không bị lệch khi duyệt hoặc sắp xếp. Quy tắc tie-break/giữ thứ tự chỉ được áp dụng sau khi dữ liệu cần so sánh đã được xác định đúng, nên kết quả trên là hệ quả trực tiếp của state record sau xử lý.

Thông tin học tập

• Module: M07
• Buổi: B23
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: struct, sorting, merge records, conflict resolution, timestamps, multi-key tie-break
• Giới hạn kiến thức: B01-B23
• Time limit: 2 second(s)
• Memory limit: 256 MB
• Point: 100