贏家預測 (APCS 2022-01 中級)

有 \(n\) 位選手參加一場反覆進行多輪比賽的競賽。選手編號為 \(1\) 到 \(n\)， 選手 \(i\) 的戰力為 \(S_i\)，應變力為 \(T_i\)。這兩項能力會在每場比賽後 改變。

第一輪開始前，選手依序排成 \(idx_1,idx_2,\ldots,idx_n\)。每一輪從隊列前端開始，依序將相鄰的兩位 選手配成一組進行比賽。若該輪人數為奇數，最後一位沒有對手的選手直接 晉級下一輪；他的戰力與應變力在這一輪都不改變。

考慮一場比賽。比賽前，排在前面的選手戰力為 \(a\)、應變力為 \(b\)， 排在後面的選手戰力為 \(c\)、應變力為 \(d\)：

1. 若 \(ab\ge cd\)，前面的選手獲勝。比賽後四項能力變為：

   \[a+\left\lfloor\frac{cd}{2b}\right\rfloor,\quad b+\left\lfloor\frac{cd}{2a}\right\rfloor,\quad c+\left\lfloor\frac{c}{2}\right\rfloor,\quad d+\left\lfloor\frac{d}{2}\right\rfloor.\]

2. 若 \(ab<cd\)，後面的選手獲勝。比賽後四項能力變為：

   \[a+\left\lfloor\frac{a}{2}\right\rfloor,\quad b+\left\lfloor\frac{b}{2}\right\rfloor,\quad c+\left\lfloor\frac{ab}{2d}\right\rfloor,\quad d+\left\lfloor\frac{ab}{2c}\right\rfloor.\]

上式中的 \(a,b,c,d\) 都是這場比賽開始前的數值；四個新值必須由舊值 計算。所有除法都直接捨去小數部分。

每輪全部比賽結束後，依照下列規則排出下一輪的隊列：

1. 先放入本輪所有勝者，保持他們在本輪隊列中的相對順序；
2. 輪空者也放在勝者隊列的最後；
3. 再放入本輪所有尚未淘汰的敗者，保持敗者的相對順序。

每位選手的累積失敗次數起初都是 \(0\)。一位選手累積第 \(m\) 次失敗時立即 淘汰，不會進入下一輪。競賽持續到隊列只剩一位選手；請輸出他的編號。

輸入格式

第一行有兩個正整數 \(n\)、\(m\)，分別代表選手人數與淘汰所需的失敗次數。

第二行有 \(n\) 個正整數 \(S_1,S_2,\ldots,S_n\)，代表各選手的初始戰力。

第三行有 \(n\) 個正整數 \(T_1,T_2,\ldots,T_n\)，代表各選手的初始應變力。

第四行有 \(n\) 個互不相同的整數 \(idx_1,idx_2,\ldots,idx_n\)，代表第一輪的選手順序；它們是 \(1\) 到 \(n\) 的一個排列。

限制

• \(2\le n\le1000\)
• \(1\le m\le5\)
• \(1\le S_i,T_i\le100\)
• 計算過程中任兩項能力相乘的結果可能超過 \(2^{32}\)，但保證不超過 \(2^{60}\)。

輸出格式

輸出最後勝利者的編號。

評分說明

範例輸入 1

4 1
4 2 5 3
2 5 1 5
1 2 3 4

範例輸出 1

4

範例解釋 1

第一輪的兩場比賽分別由選手 \(2\) 與選手 \(4\) 獲勝。因為 \(m=1\)，兩位 敗者立刻淘汰，下一輪隊列是 \([2,4]\)。第二輪由選手 \(4\) 獲勝，因此答案 是 \(4\)。

範例輸入 2

4 5
4 1 5 3
6 5 1 6
4 1 3 2

範例輸出 2

1

範例解釋 2

第一輪由選手 \(4\) 與選手 \(1\) 獲勝，選手 \(3\) 與選手 \(2\) 都只累積一敗， 尚未淘汰，因此下一輪隊列是 \([4,1,3,2]\)。依相同規則繼續模擬，最後 留下選手 \(1\)。

題目來源

APCS 2022 年 1 月實作題第 2 題； ZeroJudge h082「贏家預測」。