はまやんはまやんはまやん

hamayanhamayan's blog

Chef goes Left Right Left [CodeChef November Challenge 2017 B]

https://www.codechef.com/NOV17/problems/CLRL

N人いる。i番目の人のレートはA[i]である。
最後の人は自分で、レートはRである。
N人で順番に二分探索のようなことをする。
 
i番目より大きいならば、左に。
小さいならば、右に移る。
矛盾するならNO,矛盾しないならYES

解法

有効な範囲をメモしながら処理を進めていく。
範囲を持ちながらやっていく手法は典型。

int N, R, A[1010101];
#define INF INT_MAX/2
//---------------------------------------------------------------------------------------------------
string solve() {
    cin >> N >> R;
    rep(i, 0, N) cin >> A[i];
 
    int l = 0, r = INF;
    rep(i, 0, N - 1) {
        if (A[i] < l or r < A[i]) return "NO";
        if (l <= R and R <= A[i]) r = A[i];
        else l = A[i];
    }
    return "YES";
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) cout << solve() << endl;
}