CSES 3305 - K-th Highest Score

一場程式競賽裡有 \(n\) 位來自芬蘭的參賽者與 \(n\) 位來自瑞典的參賽者。比賽結束後發現，每位參賽者的分數都不相同。

你的任務是找出這場比賽第 \(k\) 高的分數。

為此你可以提出詢問：你可以選一個國家（芬蘭或瑞典）與一個整數 \(i\)，然後會被告知該國家第 \(i\) 高的分數。

互動方式

這是一道互動題。你的程式透過標準輸入與標準輸出和評測程式互動。一開始你要先讀入兩個整數 \(n\) 和 \(k\)。

輪到你時，你可以輸出下列其中一種：

• F i，其中 \(1 \le i \le n\)：詢問芬蘭第 \(i\) 高的分數。

• S i，其中 \(1 \le i \le n\)：詢問瑞典第 \(i\) 高的分數。

• ! s：回報第 \(k\) 高的分數是 \(s\)。輸出這一行之後，你的程式必須結束。

每一行後面都要加上換行，而且每輸出一行之後都必須確保輸出已經送出（清空輸出緩衝區）。

互動範例

3 1
F 1
9
S 1
8
! 9

說明：芬蘭的分數是 \([9, 4, 3]\)，瑞典的分數是 \([8, 6, 1]\)。因為 \(k = 1\)，任務是找出整場比賽最高的分數，在這個例子裡是 \(9\)。

限制

• \(1 \le n \le 10^5\)
• \(1 \le k \le 2n\)
• 每個分數都介於 \(1\) 到 \(10^9\) 之間
• 前兩種型態的詢問合計最多 \(100\) 次

題目來源

CSES - K-th Highest Score

題目來自 CSES Problem Set（Antti Laaksonen），授權 CC BY-NC-SA 4.0；本頁為翻譯，以相同授權分享。