AtCoder ABC 355 B - Piano 2 (6Q, 灰色, 200 点)

ソートの練習！

• 問題へのリンク

問題概要

長さ の数列 と、長さ の数列 が与えられる。なお、これら 個の値はすべて互いに相異なる。

これらをすべて混ぜた 個の値を小さい順に並べたとき、数列 の要素が 2 個以上連続する箇所があるかどうかを判定せよ。

制約

• 

考えたこと

いろんな解法が考えられるが、次のペア値をソートするのが楽だと思う。

(値, その値が A のものであるかどうかを表すブール値)

このような 個のペア値を用意して、ソートして、二番目の値が True であるものが連続することがあるかどうかを判定すればよい。

コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int,int>;

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<pint> v;
    for (int i = 0; i < N; ++i) {
        int A; cin >> A;
        v.emplace_back(A, 0);
    }
    for (int i = 0; i < M; ++i) {
        int B; cin >> B;
        v.emplace_back(B, 1);
    }
    sort(v.begin(), v.end());
 
    bool res = false;
    for (int i = 0; i + 1 < v.size(); ++i) {
        if (v[i].second == 0 && v[i+1].second == 0) {
            res = true;
        }
    }
    cout << (res ? "Yes" : "No") << endl;
}