Giải Đấu Loại Trực Tiếp Tìm Á Quân

Buổi 63 — Interactive & Constructive Trees
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Đây là bài toán mô phỏng tương tác (không tương tác trực tiếp — toàn bộ dữ liệu được cho trước).

Cho $N$ vận động viên phân biệt sức mạnh $A_1, A_2, \dots, A_N$ ($2 \le N \le 10^5$). Ta tổ chức giải đấu loại trực tiếp để tìm người mạnh nhất (Quán quân) và người mạnh nhì (Á quân) với ít phép so sánh nhất:

  • Giai đoạn 1 (Tìm Quán quân): Ở mỗi vòng, ghép các đấu thủ còn lại theo từng cặp liên tiếp $(c_1, c_2), (c_3, c_4), \dots$. Mỗi cặp thực hiện đúng 1 phép so sánh, người mạnh hơn đi tiếp vào vòng sau; nếu số đấu thủ lẻ, người cuối cùng được đặc cách đi tiếp không cần so sánh.
  • Giai đoạn 2 (Tìm Á quân): Á quân chắc chắn nằm trong tập các đấu thủ đã từng thua trực tiếp dưới tay Quán quân. Nếu tập này có $m$ người, ta thực hiện đúng $m - 1$ phép so sánh tuần tự để tìm người mạnh nhất trong tập đó.

Hãy cho biết tổng số phép so sánh đã thực hiện, giá trị Quán quân và giá trị Á quân.

Dữ liệu vào
  • Dòng đầu ghi số nguyên $N$ ($2 \le N \le 10^5$).
  • Dòng thứ hai ghi $N$ số nguyên đôi một khác nhau $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$).
Dữ liệu ra
  • Ba số nguyên trên một dòng: tổng số phép so sánh, giá trị Quán quân, giá trị Á quân.
Ví dụ
Input Output
4
3 1 4 2
4 4 3
Giới hạn
  • $2 \le N \le 10^5$
Draft saved