Xếp hạng theo độ lệch mục tiêu

Bối cảnh

Một hệ thống tuyển chọn có n ứng viên, mỗi ứng viên được mô tả bằng (score,id). Ban tổ chức đưa ra mức mục tiêu T và muốn ưu tiên ứng viên có score gần T nhất. Nếu hai ứng viên cách T bằng nhau, score cao hơn được ưu tiên vì vượt chuẩn được xem là tốt hơn thiếu chuẩn; nếu vẫn hòa score, ID nhỏ hơn đứng trước.

Bài toán yêu cầu comparator ba tầng. Điều quan trọng không chỉ là viết đủ tie-break mà còn phải bảo đảm comparator strict: khi hai record hoàn toàn giống nhau về các tiêu chí so sánh, cmp(a,a) phải trả false. Dùng <= hoặc >= có thể phá contract của std::sort. Đây là Homework Medium nhằm đưa comparator từ ví dụ hai tiêu chí lên cấu trúc gần bài thi hơn.

Yêu cầu

1. Đọc n T và n cặp score id.
2. Sort theo |score-T| tăng; tie score giảm; tie id tăng.
3. In mỗi dòng id score theo ranking.

Input

Dòng 1 n T; n dòng score id.

Output

n dòng id score.

Ràng buộc

1≤n≤5000, mọi phép trừ nằm trong long long.

Ví dụ 1

Input

5 80
80 5
75 3
85 2
75 1
90 4

Output

5 80
2 85
1 75
3 75
4 90

Giải thích

Ứng viên score 80 có distance 0 nên đứng đầu. Score 85 và 75 đều cách T=80 đúng 5; tie theo score giảm nên 85 đứng trước 75. Hai record score 75 tiếp tục tie theo ID, nên ID 1 đứng trước ID 3. Score 90 cách 10 đứng cuối. Output vì vậy theo thứ tự ID 5,2,1,3,4 với score tương ứng.

Ví dụ 2

Input

4 0
-1 4
1 3
-1 2
1 1

Output

1 1
3 1
2 -1
4 -1

Giải thích

Với T=0, cả -1 và 1 đều cách mục tiêu 1. Tie theo score giảm nên mọi record score 1 đứng trước score -1; trong cùng score, ID nhỏ hơn đứng trước. Do đó thứ tự là ID1/score1, ID3/score1, ID2/score-1, ID4/score-1.

Thông tin học tập

• Module: M05
• Buổi: B17
• Loại bài: HOMEWORK
• Độ khó: Medium
• Concepts: pair, custom comparator, absolute distance, multi-level tie-break, strict ordering
• Giới hạn kiến thức: B01-B17
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100