Lista

#include <bits/stdc++.h>
using namespace std;

/*
  Problem:
    Choose exactly k indices and permute the values among those indices arbitrarily.
    Output the lexicographically smallest possible array.

  Key fact:
    For a chosen index set S, the best we can do is:
      - sort indices S
      - sort their values
      - assign smallest value to smallest index, etc.
    So we only need to find the optimal set S.
*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> x(n + 1);
    for (int i = 1; i <= n; i++) cin >> x[i];

    // ---- Step 1: compute suffix minimums ----
    const int INF = 1e9;
    vector<int> sufMin(n + 2, INF);
    for (int i = n; i >= 1; i--) {
        sufMin[i] = min(x[i], sufMin[i + 1]);
    }

    // ---- Step 2: find earliest index i0 that can be improved ----
    int i0 = -1;
    for (int i = 1; i <= n; i++) {
        if (sufMin[i + 1] < x[i]) {
            i0 = i;
            break;
        }
    }

    // If no improvement is possible, answer is the original array
    if (i0 == -1) {
        for (int i = 1; i <= n; i++) {
            cout << x[i] << (i == n ? '\n' : ' ');
        }
        return 0;
    }

    /*
      By the correctness argument:
        - any optimal solution must include i0
        - the remaining k-1 indices should be the smallest values from suffix (i0+1..n),
          tie-breaking by taking rightmost positions.
        - if suffix has fewer than k-1 indices, we fill from prefix (i0-1..1) right-to-left.
    */

    // ---- Step 3: bucket indices by value for the suffix ----
    // Because 1 <= x[i] <= n, we can do O(n) selection with buckets.
    vector<vector<int>> bucket(n + 1);
    for (int i = i0 + 1; i <= n; i++) {
        bucket[x[i]].push_back(i); // indices stored increasing
    }

    // We will pop from the back => rightmost occurrences first (best tie-break)
    vector<int> chosen;
    chosen.reserve(k);

    // Mandatory choice
    chosen.push_back(i0);

    int need = k - 1;

    // ---- Step 4: pick the (k-1) smallest values from the suffix ----
    for (int v = 1; v <= n && need > 0; v++) {
        auto &vec = bucket[v];
        while (!vec.empty() && need > 0) {
            int idx = vec.back(); // rightmost index with this value
            vec.pop_back();
            chosen.push_back(idx);
            need--;
        }
    }

    // ---- Step 5: if still need indices, fill from prefix right-to-left ----
    // These fillers do not spoil lexicographic optimality (see Lemma 5).
    for (int i = i0 - 1; i >= 1 && need > 0; i--) {
        chosen.push_back(i);
        need--;
    }

    // Now chosen.size() == k
    sort(chosen.begin(), chosen.end());

    // ---- Step 6: sort the values on chosen positions, assign back in index order ----
    vector<int> vals;
    vals.reserve(k);
    for (int idx : chosen) vals.push_back(x[idx]);
    sort(vals.begin(), vals.end());

    vector<int> y = x;
    for (int t = 0; t < k; t++) {
        y[chosen[t]] = vals[t];
    }

    // Output
    for (int i = 1; i <= n; i++) {
        cout << y[i] << (i == n ? '\n' : ' ');
    }
    return 0;
}

Test 1 (public)

Group: 1, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 2 (public)

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 3

Group: 1, 2, 4, 5, 6

Verdict: ACCEPTED

Test 4

Group: 1, 2, 4, 5, 6

Verdict: ACCEPTED

Test 5

Group: 1, 2, 4, 5, 6

Verdict: ACCEPTED

Test 6

Group: 1, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 7

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 8

Group: 1, 4, 5, 6

Verdict: WRONG ANSWER

Test 9

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 10

Group: 1, 2, 4, 5, 6

Verdict: ACCEPTED

Test 11

Group: 1, 4, 5, 6

Verdict: WRONG ANSWER

Test 12

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 13

Group: 1, 4, 5, 6

Verdict: WRONG ANSWER

Test 14

Group: 2, 6

Verdict: ACCEPTED

Test 15

Group: 2, 6

Verdict: ACCEPTED

Test 16

Group: 2, 6

Verdict: ACCEPTED

Test 17

Group: 2, 6

Verdict: ACCEPTED

Test 18

Group: 2, 6

Verdict: ACCEPTED

Test 19

Group: 2, 6

Verdict: ACCEPTED

Test 20

Group: 1, 3, 4, 5, 6

Verdict: ACCEPTED

Test 21

Group: 3, 6

Verdict: WRONG ANSWER

Test 22

Group: 3, 6

Verdict: WRONG ANSWER

Test 23

Group: 3, 6

Verdict: WRONG ANSWER

Test 24

Group: 3, 6

Verdict: WRONG ANSWER

Test 25

Group: 3, 6

Verdict: ACCEPTED

Test 26

Group: 3, 6

Verdict: ACCEPTED

Test 27

Group: 4, 6

Verdict: WRONG ANSWER

Test 28

Group: 4, 6

Verdict: WRONG ANSWER

Test 29

Group: 4, 6

Verdict: WRONG ANSWER

Test 30

Group: 2, 4, 6

Verdict: ACCEPTED

Test 31

Group: 4, 6

Verdict: WRONG ANSWER

Test 32

Group: 4, 6

Verdict: ACCEPTED

Test 33

Group: 5, 6

Verdict: WRONG ANSWER

Test 34

Group: 5, 6

Verdict: WRONG ANSWER

Test 35

Group: 5, 6

Verdict: WRONG ANSWER

Test 36

Group: 2, 5, 6

Verdict: ACCEPTED

Test 37

Group: 5, 6

Verdict: ACCEPTED

Test 38

Group: 6

Verdict: WRONG ANSWER

Test 39

Group: 6

Verdict: WRONG ANSWER

Test 40

Group: 6

Verdict: WRONG ANSWER

Test 41

Group: 2, 5, 6

Verdict: ACCEPTED

Test 42

Group: 5, 6

Verdict: ACCEPTED

Test 43

Group: 1, 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 44

Group: 1, 2, 4, 5, 6

Verdict: ACCEPTED

Test 45

Group: 1, 4, 5, 6

Verdict: WRONG ANSWER