/*
 * @lc app=leetcode.cn id=870 lang=cpp
 *
 * [870] 优势洗牌
 */

// @lc code=start
class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        sort(nums1.begin(), nums1.end());
        vector<pair<int, int>> index;
        for (int i = 0; i < n; i++) {
            index.emplace_back(pair<int, int>(nums2[i], i));
        }
        sort(index.begin(), index.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.first > b.first;
        });

        vector<int> res(n, -1);
        int left = 0, right = n - 1;
        for (auto& p : index) {
            if (p.first < nums1[right]) {
                res[p.second] = nums1[right];
                right--;
            } else {
                res[p.second] = nums1[left];
                left++;
            }
        }
        return res;
    }
};
// @lc code=end