Phỏng vấn xin việc
Đề bài
Mô tả
Công ty của bạn đang tuyển dụng, và có ứng viên, đánh số từ đến , cùng nộp hồ sơ vào một vị trí. Mỗi ứng viên được phỏng vấn bởi cùng ba người phỏng vấn, và ứng viên nhận điểm , và lần lượt từ người phỏng vấn thứ nhất, thứ hai và thứ ba. Không người phỏng vấn nào cho hai ứng viên khác nhau cùng một điểm.
Bạn là trợ lý của Trưởng phòng Nhân sự, một người rất tỉ mỉ. Nhiệm vụ của bạn là xếp hồ sơ của các ứng viên thành một chồng duy nhất cho sếp, sao cho mỗi khi một hồ sơ nằm ngay trên một hồ sơ khác thì ứng viên của hồ sơ phía trên tốt hơn ứng viên của hồ sơ phía dưới.
Ban đầu, với hai ứng viên khác nhau và , ứng viên tốt hơn ứng viên khi và chỉ khi nhận điểm cao hơn từ ít nhất hai trong ba người phỏng vấn. Có thể thấy rằng với mọi cặp ứng viên khác nhau , đúng một trong hai người được coi là tốt hơn người kia.
Lưu ý rằng quan hệ "tốt hơn" không nhất thiết có tính bắc cầu. Ví dụ, giả sử có ba ứng viên với điểm , và . Khi đó ứng viên tốt hơn ứng viên (điểm cao hơn từ người phỏng vấn thứ hai và thứ ba), ứng viên tốt hơn ứng viên (từ người thứ nhất và thứ ba), nhưng ứng viên lại tốt hơn ứng viên (từ người thứ nhất và thứ hai). Dù vậy, chồng hồ sơ với ứng viên ở trên cùng, rồi ứng viên , rồi ứng viên ở dưới cùng vẫn hợp lệ: chỉ những hồ sơ nằm ngay trên nhau mới được so sánh, nên việc ứng viên tốt hơn ứng viên không quan trọng.
Trong ngày, các đồng nghiệp liên tục mang tin tức đến cho bạn, và tin tức có thể thay đổi việc ai tốt hơn ai. Có sự kiện, xảy ra lần lượt. Mỗi sự kiện chỉ thay đổi các phép so sánh được mô tả dưới đây, mọi phép so sánh khác giữ nguyên. Có bốn loại sự kiện:
UP x: hóa ra ứng viên là họ hàng của CEO. Từ giờ ứng viên tốt hơn mọi ứng viên khác.DOWN x: hóa ra ứng viên là họ hàng của kẻ thù không đội trời chung của CEO. Từ giờ mọi ứng viên khác đều tốt hơn ứng viên .REV x y: hội đồng tuyển dụng xem xét lại hai ứng viên và và đổi ý về họ. Nếu ứng viên đang tốt hơn ứng viên thì từ giờ ứng viên tốt hơn ứng viên , và ngược lại.STACK: không có gì thay đổi, nhưng sếp yêu cầu bạn đưa chồng gồm tất cả hồ sơ theo các phép so sánh hiện tại. Nói cách khác, chồng hồ sơ là một hoán vị của , liệt kê từ trên xuống dưới, sao cho với mọi , ứng viên tốt hơn ứng viên tại thời điểm đó. Hãy xác định xem có tồn tại chồng hồ sơ như vậy không, và nếu có thì tìm một chồng.
Mô tả hình thức:
- Tại mọi thời điểm (ban đầu và sau mỗi sự kiện), luôn đúng rằng: với mọi cặp ứng viên khác nhau , đúng một trong hai người được coi là tốt hơn người kia.
- Ban đầu, ứng viên tốt hơn trong cặp được xác định từ hai bộ và như mô tả ở trên.
- Gọi là ứng viên tốt hơn trong cặp sau sự kiện thứ . Khi đó với mọi cặp ứng viên và mọi sự kiện , trừ các trường hợp sau:
- Nếu sự kiện thứ là
UP xthì với mọi ứng viên . - Nếu sự kiện thứ là
DOWN xthì với mọi ứng viên . - Nếu sự kiện thứ là
REV x ythì .
- Nếu sự kiện thứ là
- Nếu sự kiện thứ là
STACK, bạn cần tìm một hoán vị của thỏa mãn với mọi , hoặc khẳng định rằng không tồn tại hoán vị như vậy.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (; ), số ứng viên và số sự kiện.
Dòng thứ trong dòng tiếp theo chứa ba số nguyên , và (), điểm của ứng viên từ người phỏng vấn thứ nhất, thứ hai và thứ ba. Các giá trị đôi một phân biệt, các giá trị cũng vậy, và các giá trị cũng vậy.
Mỗi dòng trong dòng tiếp theo mô tả một sự kiện, theo thứ tự xảy ra, ở một trong các dạng sau: UP x, DOWN x, REV x y hoặc STACK (; ).
Có không quá sự kiện STACK.
Dữ liệu ra
Với mỗi sự kiện STACK, theo thứ tự xuất hiện trong dữ liệu vào:
- Nếu không có chồng hồ sơ hợp lệ, in ra một dòng
NO. - Ngược lại, in ra một dòng
YES, tiếp theo là một dòng chứa số nguyên : một chồng hồ sơ hợp lệ, từ trên xuống dưới.
Nếu có nhiều đáp án, bạn có thể in ra đáp án bất kỳ.
Ràng buộc
- ; .
- ; các đôi một phân biệt, các đôi một phân biệt, các đôi một phân biệt.
- Trong mọi sự kiện, và .
- Có không quá sự kiện
STACK.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 6 3 1 2 1 3 1 2 2 3 STACK UP 2 REV 3 1 STACK DOWN 2 STACK |
YES 3 1 2 YES 2 1 3 YES 1 3 2 |
Ban đầu ứng viên tốt hơn ứng viên (điểm cao hơn từ người thứ nhất và thứ ba), ứng viên tốt hơn ứng viên (từ người thứ hai và thứ ba), ứng viên tốt hơn ứng viên (từ người thứ nhất và thứ ba). Sự kiện 1: chồng hợp lệ. Sự kiện 2 (UP 2): ứng viên tốt hơn ứng viên và , ứng viên vẫn tốt hơn ứng viên . Sự kiện 3 (REV 3 1): ứng viên trở thành tốt hơn ứng viên . Sự kiện 4: chồng hợp lệ. Sự kiện 5 (DOWN 2): ứng viên và tốt hơn ứng viên , ứng viên vẫn tốt hơn ứng viên . Sự kiện 6: chồng hợp lệ. |
| 4 5 1 2 3 2 3 1 3 1 2 4 4 4 STACK REV 4 1 DOWN 4 UP 1 STACK |
YES 4 3 2 1 YES 1 3 2 4 |
Ví dụ bổ sung (không có trong đề gốc). Ba ứng viên đầu là ví dụ không bắc cầu ở trên, ứng viên tốt hơn cả ba. Sau REV 4 1, DOWN 4 và UP 1: ứng viên tốt hơn mọi người, ứng viên kém hơn mọi người, ứng viên vẫn tốt hơn ứng viên . |
Bình luận