Overview

This problem involves assigning \(N\) delivery workers (with stamina \(A_i\)) to \(M\) delivery requests (requiring stamina \(B_j\)). The condition to satisfy is that there exists an assignment where “worker’s stamina \(\ge\) required stamina” for all requests (primary objective), and among such assignments, we want to maximize the number of “exact match” pairs where “worker’s stamina \(=\) required stamina” (secondary objective).

This can be solved efficiently using sorting, a greedy approach, and the Two Pointers technique.

---

Analysis

1. Primary Objective: Can all requests be assigned?

To fulfill all requests, we need to select \(M\) workers from the available \(N\). The most advantageous strategy for determining “whether an assignment is possible” is “assign the top \(M\) workers with the highest stamina to the requests in order of increasing required stamina.”

Specifically, sort both the workers’ stamina \(A\) and the required stamina \(B\) in ascending order. The top \(M\) workers by stamina are the last \(M\) elements of \(A\), namely \(A[N-M], A[N-M+1], \dots, A[N-1]\). We match these to the sorted requests \(B[0], B[1], \dots, B[M-1]\) in order.

We check whether the following condition holds for all \(0 \le i < M\): $\(A[N - M + i] \ge B[i]\)$

If there exists any \(i\) that does not satisfy this condition, then no matter how we choose workers, it is impossible to assign all requests. In this case, output -1.

2. Secondary Objective: Maximizing exact match assignments

Once the primary objective is determined to be achievable, we next maximize the number of “exact match (\(A_i = B_j\))” assignments.

At first glance, one might worry that increasing the number of “exact match” pairs could cause insufficient stamina for workers assigned to other requests, making the primary objective unachievable (breaking the overall assignment). However, “if the primary objective is achievable, then greedily maximizing exact match pairs will always allow the remaining members to achieve the primary objective” — this property holds.

This is because creating a pair where \(A_i = B_j = v\) and removing it is equivalent to canceling out a “worker with stamina \(v\)” and a “request requiring stamina \(v\)” in the overall assignment. A worker with stamina \(v\) can only handle requests with required stamina \(\le v\), and a request requiring stamina \(v\) can only be handled by workers with stamina \(\ge v\). Therefore, pairing and removing these one-to-one does not negatively affect the “assignability” among the remaining elements.

Thus, the maximum value for the secondary objective can be obtained by simply computing the following sum over each value \(v\): $\(\sum_{v} \min(\text{count of } v \text{ in } A, \text{count of } v \text{ in } B)\)$

---

Algorithm

Since \(A\) and \(B\) are already sorted in ascending order, we can efficiently count the number of common elements in \(O(N + M)\) using the Two Pointers technique.

1. Sort arrays \(A\) and \(B\) in ascending order.
2. Determine whether the primary objective is achievable.
   • Check whether \(A[N - M + i] \ge B[i]\) holds for all \(0 \le i < M\). If not, output -1 and terminate.
3. Initialize two pointers \(i\) (for \(A\)) and \(j\) (for \(B\)) to \(0\).
4. While \(i < N\) and \(j < M\), repeat the following:
   • If \(A[i] < B[j]\): \(A[i]\) cannot be an exact match for \(B[j]\) or any subsequent request, so advance \(i\) (\(i \leftarrow i + 1\)).
   • If \(A[i] > B[j]\): \(B[j]\) cannot be an exact match for \(A[i]\) or any subsequent worker, so advance \(j\) (\(j \leftarrow j + 1\)).
   • If \(A[i] == B[j]\):
     • Let \(val\) be their common value.
     • Count the number of elements in \(A\) with value \(val\) as \(countA\), advancing pointer \(i\).
     • Count the number of elements in \(B\) with value \(val\) as \(countB\), advancing pointer \(j\).
     • Add \(\min(countA, countB)\) to the answer count.

---

Complexity

• Time Complexity: \(O(N \log N + M \log M)\)

  • Sorting arrays \(A, B\) takes \(O(N \log N + M \log M)\).
  • The primary objective check takes \(O(M)\), and the two-pointer scan for the secondary objective takes \(O(N + M)\).
  • Overall, sorting is the bottleneck, giving a total complexity of \(O(N \log N + M \log M)\). This runs sufficiently fast under the constraints \(N, M \le 2 \times 10^5\).

• Space Complexity: \(O(N + M)\)

  • Memory is needed to store the input arrays \(A\) and \(B\).

---

Implementation Notes

• Two-pointer boundary conditions: In the while loops that count elements with the same value, you must always include the conditions i < N and j < M to ensure that indices \(i, j\) do not exceed the array sizes \(N, M\) respectively.

• Fast I/O: In C++, since the input data size can be large, speeding up std::cin (with ios_base::sync_with_stdio(false); cin.tie(NULL);) prevents Time Limit Exceeded (TLE) due to I/O overhead.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    vector<long long> B(M);
    for (int i = 0; i < M; ++i) {
        cin >> B[i];
    }

    // 昇順にソート
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    // 第一目標の判定：
    // B の各要素 B[i] に対して、A の大きい方から M 個を順に対応させたときに、
    // すべての i について A[N - M + i] >= B[i] が成り立つかを確認する。
    bool possible = true;
    for (int i = 0; i < M; ++i) {
        if (A[N - M + i] < B[i]) {
            possible = false;
            break;
        }
    }

    if (!possible) {
        cout << -1 << "\n";
        return 0;
    }

    // 第二目標の計算：
    // 第一目標が達成可能な場合、A_i = B_j となるペアの最大数は、
    // 各値 v について min(Aにおけるvの個数, Bにおけるvの個数) の総和に等しい。
    // ソート済みなので、two pointers を用いて O(N + M) で計算できる。
    long long ans = 0;
    int i = 0, j = 0;
    while (i < N && j < M) {
        if (A[i] < B[j]) {
            i++;
        } else if (A[i] > B[j]) {
            j++;
        } else {
            long long val = A[i];
            long long countA = 0;
            while (i < N && A[i] == val) {
                countA++;
                i++;
            }
            long long countB = 0;
            while (j < M && B[j] == val) {
                countB++;
                j++;
            }
            ans += min(countA, countB);
        }
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.