Parry Battle

2 secs 1024 MB

解説

各 $A_i \lparen 1 \leq i \leq N \rparen$ に対して $A_i-r \leq B_k < A_i$ を満たす $k$ が存在することが判定できればよいです。
二分探索によって配列 $B$ から $A_i-r$ 以上の最小の値を求め、それが $A_i$ 未満であれば敵の体力を減らし、そうでなければプレイヤーの体力を減らすことで、全体では $O(N \log M)$ で解を求めることができるため、十分高速です。

回答例

xxxxxxxxxx
 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
​
void solve() {
    ll n,m,h,r;
    cin >> n >> m >> h >> r;
    vector<ll> A(n), B(m);
    for (ll i = 0; i < n; ++i) cin >> A[i];
    for (ll i = 0; i < m; ++i) cin >> B[i];
​
    ll player = h;
    ll enemy = h;
    for (ll i = 0; i < n; ++i) {
        ll val = *lower_bound(B.begin(), B.end(),A[i]-r);
​
        if (A[i]-r <= val && val < A[i]) --enemy;
        else --player;
​
        if (!enemy) {
            cout << "Win" << endl;
            return;
        } else if (!player) {
            cout << "Lose" << endl;
            return;
        }
    }
    cout << "Draw" << endl;
}
​
int main() {
    solve();
    return 0;
}
​