提出 #49559724

---

ソースコード 拡げる

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<ValueMatrix> ValueCube;
typedef std::string string;
typedef std::vector<string> StringVector;
typedef std::vector<bool> bitset;
typedef std::vector<bitset> BitMatrix;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::vector<PairVector> PairMatrix;
typedef std::tuple<valueType, valueType, valueType> ValueTuple;
typedef std::vector<ValueTuple> TupleVector;
typedef std::vector<TupleVector> TupleMatrix;
typedef std::set<valueType> ValueSet;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::set<ValuePair> PairSet;

void solve() {
    valueType N;

    std::cin >> N;

    ValueVector A(N), B(N);

    for (auto &a : A)
        std::cin >> a;

    for (auto &b : B)
        std::cin >> b;

    std::sort(A.begin(), A.end());
    std::sort(B.begin(), B.end());

    if (A[N - 1] + A[N - 2] <= B.back()) {
        std::cout << "Bob\n";

        return;
    }

    // A.erase(std::unique(A.begin(), A.end()), A.end());

    auto Count = [&](valueType l, valueType r) -> valueType { // count number of elements in (l, r) of A
        ++l;
        --r;

        if (l > r)
            return 0;

        return std::upper_bound(A.begin(), A.end(), r) - std::lower_bound(A.begin(), A.end(), l);
    };

    auto Check = [&](valueType l, valueType r, valueType a) -> bool {
        if (l < a && a < r) {
            return Count(l, r) > 1;
        } else {
            return Count(l, r) > 0;
        }
    };

    ValueVector LimitB(N, 0);

    for (valueType i = 0; i < N; ++i) {
        valueType const b = B[i];

        auto iter = std::lower_bound(A.begin(), A.end(), b);



        if (iter != A.end()) {
            LimitB[i] = *iter - b;
        }

        if (iter != A.begin()) {
            --iter;

            LimitB[i] = std::max(LimitB[i], b - *iter);
        }
    }

    ValueVector SufMaxOfLimitB = LimitB;

    for (valueType i = N - 2; i >= 0; --i)
        SufMaxOfLimitB[i] = std::max(SufMaxOfLimitB[i], SufMaxOfLimitB[i + 1]);

    bool ok = false;

    valueType pointer = 0;

    valueType const MinB = B.front();

    for (auto const &a : A) {
        while (pointer < N && B[pointer] < a)
            ++pointer;

        bool flag = true;

        if (pointer != N) {
            if (a <= SufMaxOfLimitB[pointer])
                flag = false;
        }

        if (std::lower_bound(B.begin(), B.end(), a) != B.end()) {
            valueType nextB = *std::lower_bound(B.begin(), B.end(), a);

            valueType const l = nextB - a;
            valueType const r = nextB + a;

            if (!Check(l, r, a))
                flag = false;
        }

        if (std::upper_bound(B.begin(), B.end(), a) != B.end()) {
            valueType nextB = *std::upper_bound(B.begin(), B.end(), a);

            valueType const l = nextB - a;
            valueType const r = nextB + a;

            if (!Check(l, r, a))
                flag = false;
        }

        if (MinB < a) {
            if (!Check(a - MinB, a + MinB, a))
                flag = false;
        }

        if (flag) {
            ok = true;

            break;
        }
    }

    std::cout << (ok ? "Alice" : "Bob") << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType T;

    std::cin >> T;

    for (valueType testcase = 0; testcase < T; ++testcase)
        solve();

    std::cout << std::flush;

    return 0;
}

提出情報

ジャッジ結果