Lời giải

Gọi vị trí ~i~ là vị trí thắng nếu ~a_i > b_i~. Ta cần sắp lại ~b~ để có đúng ~x~ vị trí thắng.

Muốn một vị trí thắng thì nên cho ~a~ lớn gặp ~b~ nhỏ, còn muốn một vị trí thua thì nên cho ~a~ nhỏ gặp ~b~ lớn. Từ đó ta dựng một cách xếp cụ thể:

• ~x~ giá trị ~a~ lớn nhất được ghép với ~x~ giá trị ~b~ nhỏ nhất;
• ~n - x~ giá trị ~a~ còn lại được ghép với ~n - x~ giá trị ~b~ còn lại.

Trong mỗi nhóm, ta ghép theo thứ tự đã sắp: ~a~ nhỏ nhất với ~b~ nhỏ nhất, ~a~ nhỏ thứ hai với ~b~ nhỏ thứ hai, và cứ thế.

Ta sẽ chứng minh rằng nếu có một cách xếp nào đó đạt độ đẹp ~x~ thì cách xếp trên cũng đạt độ đẹp ~x~. Do đó thuật toán chỉ cần dựng cách xếp này và đếm độ đẹp. Nếu bằng ~x~ thì in ra, nếu khác thì in NO.

Lấy một cách xếp bất kỳ có độ đẹp ~x~ và gọi ~W~ là tập các vị trí thắng. Ta biến đổi nó qua ba bước, bước nào cũng giữ nguyên độ đẹp.

1. Thay các giá trị ~b~ ở ~W~ bằng ~x~ giá trị ~b~ nhỏ nhất. Ta sắp các giá trị ~b~ cũ ở ~W~ và ~x~ giá trị nhỏ nhất rồi ghép theo thứ tự. Mỗi vị trí trong ~W~ nhận một giá trị mới không lớn hơn giá trị cũ, nên vẫn thắng. Các vị trí ngoài ~W~ nhận giá trị mới không nhỏ hơn giá trị cũ, nên vẫn thua.
2. Đưa ~W~ về ~x~ vị trí có ~a~ lớn nhất. Nếu có ~i \in W~ và ~j \notin W~ mà ~a_i \le a_j~, ta tráo ~b_i~ và ~b_j~. Khi đó ~j~ nhận ~b_i < a_i \le a_j~ nên thắng, còn ~i~ nhận ~b_j \ge a_j \ge a_i~ nên thua. Độ đẹp không đổi. Lặp lại cho đến khi ~W~ gồm ~x~ vị trí có ~a~ lớn nhất.
3. Trong mỗi nhóm, ghép lại theo thứ tự đã sắp. Xét nhóm thắng và giả sử có một cách ghép để cả ~x~ cặp đều thắng. Lấy ~k~ giá trị ~a~ nhỏ nhất của nhóm; chúng thắng ~k~ giá trị ~b~ khác nhau, nên cả ~k~ giá trị ~b~ này đều nhỏ hơn ~a_{(k)}~. Trong ~k~ giá trị ~b~ khác nhau luôn có một giá trị không nhỏ hơn ~b_{(k)}~, nên ~b_{(k)} < a_{(k)}~. Đây chính là điều kiện để cặp thứ ~k~ trong cách ghép theo thứ tự thắng. Nhóm thua được chứng minh tương tự.

Sau ba bước, ta được đúng cách xếp đã dựng, và độ đẹp vẫn là ~x~.

Ví dụ với bộ test thứ tư (~a = [2, 4, 3]~, ~b = [4, 1, 2]~, ~x = 1~): ~b~ sau khi sắp là ~[1, 2, 4]~. Giá trị ~a~ lớn nhất là ~a_2 = 4~, nhận ~b~ nhỏ nhất là ~1~. Hai giá trị còn lại ~a_1 = 2~ và ~a_3 = 3~ lần lượt nhận ~2~ và ~4~. Ta được ~[2, 1, 4]~, chỉ có vị trí ~2~ thắng, độ đẹp bằng ~1~. Kết quả này khác đáp án mẫu ~[2, 4, 1]~ nhưng vẫn đúng, vì đề chấp nhận mọi cách xếp hợp lệ.

Cần lưu ý là các độ đẹp đạt được không nhất thiết liên tiếp từ ~0~ đến giá trị lớn nhất. Cũng với cặp dãy trên (các bộ test ~3~ đến ~6~), đạt được độ đẹp ~1~ và ~2~ nhưng không đạt được ~0~. Vì vậy không thể chỉ so ~x~ với độ đẹp lớn nhất.

Chương trình

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

#ifdef JASPER
#include <debug.h>
#else
#define debug(...) 166
#endif

void solve() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n), b(n), ord(n);
    for (auto &v : a) cin >> v;
    for (auto &v : b) cin >> v;
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int i, int j) { return a[i] < a[j]; });
    sort(b.begin(), b.end());
    // ord[0..n-x-1]: a nho  <-  b[x..n-1] (b lon), theo thu tu
    // ord[n-x..n-1]: a lon  <-  b[0..x-1] (b nho), theo thu tu
    vector<int> c(n);
    for (int k = 0; k < n - x; ++k) c[ord[k]] = b[x + k];
    for (int k = 0; k < x; ++k) c[ord[n - x + k]] = b[k];
    int beauty = 0;
    for (int i = 0; i < n; ++i) beauty += a[i] > c[i];
    if (beauty != x) {
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
    for (int i = 0; i < n; ++i) cout << c[i] << " \n"[i + 1 == n];
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

Độ phức tạp là ~O(n \log n)~ cho mỗi bộ test. Trên test nặng nhất (~n = 2 \cdot 10^5~), chương trình chạy trong 0,03 s và dùng 12 MB, trong khi giới hạn là ~2~ s và ~256~ MB.

Lỗi thường gặp

• Kết quả phải in theo vị trí gốc của ~a~, nên không được sắp trực tiếp mảng ~a~. Chương trình trên sắp mảng chỉ số ord thay cho ~a~.
• Trong nhóm thắng phải ghép ~a~ nhỏ với ~b~ nhỏ. Nếu ghép ngược thứ tự (~a~ lớn nhất với ~b~ nhỏ nhất), cặp cuối có thể không còn thắng.
• Phải đếm độ đẹp trên cả hai nhóm. Nếu nhóm thua có một cặp ~a > b~ thì độ đẹp vượt quá ~x~. Cách an toàn là đếm lại toàn bộ, như chương trình trên.
• Sau YES phải in đúng ~n~ số trên một dòng. Trình chấm kiểm tra dãy in ra là hoán vị của ~b~ và có độ đẹp đúng bằng ~x~; câu trả lời YES/NO phải trùng với đáp án chuẩn.