TopCoder

bb
\ https://bbqube.ac - https://brian.su /

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

65.0% (13/20)

Tags

Description

有一天,一個神祕人物來請求你。原來,他與其他N-1個人參與了雷族的「特內門特」活動,並且十分幸運地,他所獲得的臨時編號是N-1。如今,他透過特殊的管道知道了比試的項目;而也因為他的臨時編號是最後一個,他知道在他站好位置之前所有人站在哪裡,也為每一個人(包含他自己)給了一個「能力值」,從最低的0到最高的N-1。能確定的是,在一輪的比試內,所有參與比試的人中,能力值最高的人將會獲勝。
這個神秘人物希望他能在馬爾門特內獲得最高的分數,可是卻不知道他應該要選哪裡站。而如果有很多個位置都能獲得同樣多的分數,他希望可以站愈前面愈好

這個神秘人物整理了下列資訊:參與的人數(包含神秘人物)N、在神秘人物還沒有進入隊列前所有人按照順序從前到後的能力值K0...N-2、以及馬爾門特的C組數對(A0...C-1, B0...C-1)。他希望你告訴他一個數字X,代表他在第一輪身為編號X可以獲得最高的分數。另外,為了你的方便,雖然你可以直接從K0...N-2裡面推論出這位神秘人物的能力值,他還是會另外告訴你他自己的能力值R。

當然,你身為一個普通人,不會知道什麼是「特內門特」。還好,你在各處打聽,找到了以下的資料。你能不能幫助他找到能獲得最高分數的位置呢?



特內門特(雷族語拼音、烏梭文:Terneemeent)是雷族古老傳統的一個儀式。原先是雷族吉祥、祝歲的儀式,後來傳入烏梭後,普遍做為團康活動。

活動介紹
傳統儀式
特內門特會在每年的閃月初(相當於雅善曆七月末),於塔斯黎長廊(Tarzslil)舉行。儀式的參與人數基本上沒有上限,且愈多人愈好。雷族會推派一個長老團,或稱馬爾門特(Ma'ermeent),主持整個儀式。
概略來說,特內門特的參與人會進行多輪的比試(每一輪的比試並非所有人都會參加),每一輪的勝出人只有一個,其他人便遭淘汰。特別的是,最後的排名並不是按照淘汰的先後順序,而是按照總共勝出了幾輪的比試。勝出的輪數被視為在這個活動獲得的分數。

傳統上,特內門特有七天的準備期,人們在這段時間報名。在開始前一天晚上,報名結束,主持單位會統計參加人數,並且給每個參加者一個臨時編號,從0編號到N-1。隔天早上,活動正式開始。馬爾門特會宣布C組數對,代表總共進行C輪比試;第i個數對(Ai, Bi)(Ai < Bi)代表在第i輪編號在[Ai, Bi]之內的人需進行比試。接著所有參加者按照臨時編號小到大的順序,一個一個進入隊列,每個人在進入隊列的時候都可以選擇自己要站在哪個位置(任兩個人中間,或者隊列的頭或尾)。等到站完之後,從隊列的最前端開始由0開始編號,一直編到最後端的N-1,此即為第一輪的編號。編號完畢之後,馬爾門特才會宣布比試的方式。比試的方式十分多樣化,也考驗著馬爾門特的創意。相傳,想出創新的比試方式能為整個族人帶來好運,所以馬爾門特在七天的準備期,會召開規模龐大的會議。
從第一輪開始,每一輪都按照這個比試方式進行,只有勝出者留在隊列並累計勝利次數,被淘汰者則離開隊列。接著進入下一輪,並且重新按照隊列順序編號。馬爾門特宣布的C組數對必定會使C輪結束之後,留在隊列中的只剩下一個人。
最後,依照勝利次數的多寡,會得到大小不一的獎項。活動結束當天,亦會有豐盛的晚宴。

舉例
假設總共有5個人A、B、C、D、E參加特內門特。
在特內門特前一天,A、B、C、D、E分別獲得的臨時編號是2、4、0、1、3。
特內門特開始後,馬爾門特宣布三組數對:(1, 3), (0, 1), (0, 1)。按照臨時編號,C先進入隊列;D選擇站在C前面;A選擇站在C、D中間;E選擇站在C後面;B選擇站在D前面。
假設馬爾門特的比試規則是身高最高的人勝出。假設五人的身高A < B < C < D < E。
第一輪,隊列是(前)BDACE(後)。該輪的數對是(1, 3),D、A、C三人進行比試,D獲勝,A、C離開隊列。
第二輪,隊列是(前)BDE(後)。該輪的數對是(0, 1),B、D二人進行比試,D獲勝,B離開隊列。
第三輪,隊列是(前)DE(後)。該輪的數對是(0, 1),D、E二人進行比試,E獲勝,D離開隊列。
因此,D獲得2分、E獲得1分,其餘三人皆為0分。

Input Format

本題沒有輸入,如果你輸入了任何東西可能會導致各種不可預期的結果(?)。

#include "lib1275.h"之後實作下列函數,這個函數傳入六個參數。這個函數要回傳你算出來的X值。
第一、二、三個參數是整數N、C、R,分別代表參加特內門特的人數、馬爾門特的數對數、神秘人物的能力值。
第四個參數K是長度為N-1的整數陣列,代表已經排好的人的能力值。
第五、六個參數A、B都是長度為C的整數陣列,代表馬爾門特的數對。
int GetBestPosition(int, int, int, int[], int[], int[]);
如果你的函數名稱不對或者長得不像上面那行,你將會獲得一個CE。

在一次執行當中,這個函數會被呼叫很多次,所以請確保函數中有進行初始化。

對於17%的測資,N ≤ 500。
對於32%的測資,N ≤ 5,000。
對於所有的測資,N ≤ 100,000。

Output Format

本題沒有輸出,如果你輸出了任何東西,你將會獲得一個WA

Hints

這裡有一個測試用的標頭檔,可以用來測試。
該標頭檔接受以下輸入:
第一行:N, C, R;
第二行:K[0], K[1], ..., K[N - 2];
第三行:S[0], E[0], S[1], E[1], ..., S[C - 1], E[C - 1];
並輸出GetBestPosition回傳的數值。

Problem Source

IOI 2012 Day 2
Judge / Description by Yihda Yol

Subtasks

No. Testdata Range Score
1 0 17
2 1 32
3 2 51

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 262144 262144 1
1 4000 262144 262144 2
2 4000 262144 262144 3