TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

80.6% (25/31)

Submission's AC Ratio

48.9% (87/178)

Tags

Description

……「可不能讓你輕易通過呢!」
聲音是從洞穴內傳出來的。這個洞穴的形狀是個缺一角的圓周,長$L$公分,而小向現在就位於洞穴的兩個入口之間。聲音是從右邊還從左邊傳出來的?小向並不是很清楚。
「像妳這種不成器的瞬間移動,從中攔截可是輕而易舉呢!」一個身影從其中一個入口漸漸浮出。
「呃…這是什麼鬼啊…」

「真沒禮貌,我可是棲息於烏森的龍,簡稱烏龍呢!」這不知道是茶葉還是龍的生物如此反駁。
「比起這個,你不是想去森林的正中心嗎?不打敗我可是過不去的喔呵呵~」
說得也是。竟敢小看我的瞬間移動,明明只是茶葉而已。小向邊生氣邊對著烏龍施展魔法。只見烏龍底下突然出現了一個魔法陣,發出強烈光芒,緊接著是爆破。
「太好了,成功了!」小向正為了成功施展自己稍微不太擅長的破壞系魔法而開心,沒想到…洞穴裡傳來了更多聲音…
「太天真了(*n),剛剛那個只是我的其中一個分身(*n)。殺了一個我(*n),還有千千萬萬個我呢(*n),呵哈哈!(*n)」(嘲諷*n)
「每句話都重複n次煩不煩啊…吵死了…」小向偷偷地在心底抱怨。
不過為了確定敵方不是在虛張聲勢,小向單手觸地,發動了偵察魔法。
「……」
小向在洞穴裡偵察到了$N$個烏龍,不知道是本尊還是分身。不過他們在洞穴中都是以每秒1公分的速度前進,只是有的朝著左邊的入口前進,而有的朝著右邊的入口前進。而由於洞穴相當狹窄,兩個相向的烏龍相撞時會回頭。小向大膽猜測,本尊一定會在所有分身都出洞穴被小向打敗後才出洞穴,瞄準小向用盡魔力的那剎那攻擊小向。不過她也沒那麼多時間等所有分身慢慢走出來再找到本尊,所以小向希望能直接用她剛剛偵察到的資訊判斷哪個是本尊。
雖然已經化簡成一個可以用魔法解決的問題了,不過小向只會用魔法得知本尊還要多久才會從洞穴出來,找出本尊這種高階層的魔法還在小向的能力範圍之外。
「加油吧,我的頭腦…」

Input Format

第一行有兩個正整數$N\leq 10^ 6, L\leq 10^ 9$,分別代表洞穴裡的烏龍有幾個以及洞穴的長度。
接下來的$N$行,每行有兩個非負整數$0\leq x_i\leq L, d_i$,分別代表編號$i$的烏龍位置以及前進方向。編號由0到$n-1$,$x_i$代表烏龍距離左邊那個入口幾公分,而如果$d_i$是0代表烏龍朝著左邊的入口,如果是1代表烏龍朝著右邊的入口。

子任務(測資) 額外限制 分數
1 (0~4) $N\leq 10^ 3, L \leq 10^ 4$ 12
2 (5~9) 存在一個$M$使得所有位置小於等於$M$的烏龍都朝右,所有位置大於$M$的烏龍都朝左 12
3 (10~14) $N\leq 10^ 3$ 36
4 (15~19) 40

Output Format

輸出一個整數,代表本尊的編號。
注意:離開洞穴的定義是從左邊的入口往左走一步或從右邊的入口往右走一步。保證答案唯一,並且所有烏龍都在不同位置。

Sample Input

3 4
0 1
1 1
2 0

Sample Output

1

Hints

「找到了!」小向終於算出了本尊的所在地。
「霹麗卡霹麗拉拉,波波麗那貝貝魯多!」小向詠唱了咒文增加了她的破壞系魔法,直接衝向還在洞穴的烏龍。
「啊!」烏龍發出了茶葉般的悲鳴,分身們也隨之消失。

煙霧散去後,留下了一個身影。
「咦…沒清乾淨啊…」小向拿出魔杖,嘲著那身影。
「咳咳…咳咳…謝謝你…咳咳」烏龍突然這樣說。
「?」
「謝謝你幫我解開了洗腦。」

Problem Source

Problem Set / Description by Paupière
改編自NTUOJ

Subtasks

No. Testdata Range Score
1 0~4 12
2 5~9 12
3 10~14 36
4 15~19 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3
15 1000 65536 262144 4
16 1000 65536 262144 4
17 1000 65536 262144 4
18 1000 65536 262144 4
19 1000 65536 262144 4