小向的試煉 2-1：洞穴(Cave)

https://tioj.ck.tp.edu.tw/problems/1948

Description

小向在洞穴裡偵察到了$N$個烏龍，不知道是本尊還是分身。不過他們在洞穴中都是以每秒1公分的速度前進，只是有的朝著左邊的入口前進，而有的朝著右邊的入口前進。而由於洞穴相當狹窄，兩個相向的烏龍相撞時會回頭。小向大膽猜測，本尊一定會在所有分身都出洞穴被小向打敗後才出洞穴，瞄準小向用盡魔力的那剎那攻擊小向。不過她也沒那麼多時間等所有分身慢慢走出來再找到本尊，所以小向希望能直接用她剛剛偵察到的資訊判斷哪個是本尊。($N\leq10^6$，洞穴的長度$L\leq10^9$)

注意：離開洞穴的定義是從左邊的入口往左走一步或從右邊的入口往右走一步。保證答案唯一，並且所有烏龍都在不同位置。

Solution

首先若不管烏龍的編號，只想知道烏龍最後的位置，兩個烏龍相撞並回頭時可以當作穿過去
顯然地，我們可以知道所有烏龍最晚離開洞穴的時刻，就等於每隻烏龍單獨放在洞穴內離開洞穴的時刻的最大值，我們也能知道最後一隻離開洞穴的烏龍是向左還是向右

接著可以發現在烏龍相撞的過程中，左右順序一定不會變，意思是如果某個編號$i$的烏龍一開始是x座標第$k$大的，那不管經過多少次的相撞，他仍然會是x座標第$k$大的
同時向左的烏龍數量與向右的烏龍數量也不會變
所以，我們可以知道最後一隻烏龍離開洞穴時，一定是左邊全部向左，右邊全部向右，而那隻最後離開的烏龍一定是「向左的烏龍中最右邊的或者向右的烏龍中最左邊的」，也就知道了最後離開的烏龍是x座標第幾大的了

用 nth_element 可以快速找出x座標第$k$大的編號，注意一開始他給的編號沒有按照x座標排序，上述推論必須先照x座標排序才會是對的= =

AC code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#pragma g++ optimize("Ofast")
#pragma loop_opt(on)
#include <cstdio>
#include <algorithm>
const int N = 1000001;

int n,L,x[N],id[N],cnt;
signed main() {
    int t = -1e9, dir, pos;
    scanf("%d%d",&n,&L);
    for(int i = 0,d; i < n; i++) {
    	scanf("%d%d",x+i,&d);
        int dis = d ? L-x[i] : x[i];
        if(t < dis) t = dis, dir = d;
        if(!d) cnt++;
    }
    pos = cnt+dir-1;
    for(int i = 0; i < n; i++) id[i] = i;
    std::nth_element(id,id+pos,id+n,[](int a,int b){return x[a]<x[b];});
    printf("%d\n", id[pos]);
}