Overview

This problem requires determining whether all delivery requests can be fulfilled given the stamina values \(A\) of delivery workers and the required stamina values \(B\) of delivery requests (first objective), and if possible, maximizing the number of “perfect assignments” where stamina values exactly match (second objective).

By sorting the arrays and using a greedy approach for the first objective’s determination and a two-pointer technique for the second objective’s optimization, the problem can be solved efficiently.

---

Analysis

1. First Objective: Can all requests be assigned?

To fulfill all \(M\) requests, it is clearly most advantageous to assign the top \(M\) delivery workers with the highest stamina.

Therefore, we sort the delivery workers’ stamina \(A\) and the required stamina \(B\) of requests each in ascending order. Let the top \(M\) delivery workers with the highest stamina be \(A' = [A_{N-M}, A_{N-M+1}, \ldots, A_{N-1}]\). Then the following must hold for all \(i\) (\(0 \leq i < M\)): $\(A_{N-M+i} \geq B_i\)\( If there exists any \)i$ that does not satisfy this condition, it is impossible to assign all requests regardless of how delivery workers are chosen. In this case, output -1 and terminate.

2. Second Objective: Maximize perfect assignments

When the first objective is achievable, we next maximize the number of “perfect assignments (\(A_i = B_j\))”.

At first glance, you might worry: “If we prioritize making perfect pairs, won’t we be unable to allocate high-stamina workers to other requests, making the first objective unachievable?” However, the following property actually holds: “If the first objective is achievable, then even when maximizing perfect pairs, an assignment that achieves the first objective always exists.”

Why is it sufficient to simply count the number of common elements?

For example, suppose in some valid assignment, a pair \(A_i = B_j\) that could be a perfect match is not paired together, and different assignments are made instead: - Worker \(i\) (stamina \(A_i\)) is assigned to request \(k\) (required stamina \(B_k\)) (\(A_i \geq B_k\)) - Worker \(l\) (stamina \(A_l\)) is assigned to request \(j\) (required stamina \(B_j\)) (\(A_l \geq B_j\))

Here, we want to create the pair where \(A_i = B_j\). If we swap the assignments to \((A_i, B_j)\) and \((A_l, B_k)\): - \((A_i, B_j)\) satisfies the stamina condition since \(A_i = B_j\) (perfect pair). - For \((A_l, B_k)\), since \(A_l \geq B_j = A_i \geq B_k\), we have \(A_l \geq B_k\), so the stamina condition is also satisfied.

In this way, if a valid assignment exists, we can create all possible perfect pairs while maintaining assignment consistency. Therefore, the second objective of this problem reduces to simply finding the “maximum number of common elements between \(A\) and \(B\) as multisets (sets allowing duplicates)”.

---

Algorithm

1. Sort: Sort the delivery workers’ stamina array \(A\) and the required stamina array \(B\) each in ascending order.

2. First Objective Determination: Compare the last \(M\) elements of \(A\) with the \(M\) elements of \(B\) in order. Check whether \(A[N - M + i] \geq B[i]\) holds for all \(0 \leq i < M\). If not satisfied, output -1.

3. Second Objective Calculation (Two-Pointer): For the sorted \(A\) and \(B\), use two pointers ptr_a and ptr_b to count the number of common elements.

   • If \(A[\text{ptr\_a}] == B[\text{ptr\_b}]\): A common element is found, so increment the count by \(1\) and advance both pointers.
   • If \(A[\text{ptr\_a}] < B[\text{ptr\_b}]\): The value in \(A\) is too small, so advance ptr_a.
   • If \(A[\text{ptr\_a}] > B[\text{ptr\_b}]\): The value in \(B\) is too small, so advance ptr_b.

---

Complexity

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

  • Sorting arrays \(A, B\) takes \(O(N \log N + M \log M)\) time.
  • The first objective determination takes \(O(M)\), and the two-pointer traversal takes \(O(N + M)\) time.
  • Overall, sorting is the bottleneck, and it runs sufficiently fast for the constraints \(N, M \leq 2 \times 10^5\).

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

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

---

Implementation Notes

• Difference between 1-indexed and 0-indexed: Since Python lists are 0-indexed, the index in \(A\) to compare against in the first objective determination is N - M + i.

• Two-pointer termination condition: The loop runs while ptr_a < N and ptr_b < M. Once either array has been fully traversed, no more common elements can be found, so it is safe to terminate the search.

  Source Code

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return

    N = int(data[0])
    M = int(data[1])

    A = [int(x) for x in data[2 : 2 + N]]
    B = [int(x) for x in data[2 + N : 2 + N + M]]

    A.sort()
    B.sort()

    # 第一目標の判定：すべての配達依頼に割り当て可能か
    for i in range(M):
        if A[N - M + i] < B[i]:
            print(-1)
            return

    # 第二目標：ぴったりの最大数（共通要素の数）を尺取り法でカウント
    ans = 0
    ptr_a = 0
    ptr_b = 0
    while ptr_a < N and ptr_b < M:
        if A[ptr_a] == B[ptr_b]:
            ans += 1
            ptr_a += 1
            ptr_b += 1
        elif A[ptr_a] < B[ptr_b]:
            ptr_a += 1
        else:
            ptr_b += 1

    print(ans)


if __name__ == "__main__":
    solve()

---

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