Lista

#include <bits/stdc++.h>

namespace {

// Tracks how many copies of each value we can still place and how many
// appear in the yet-to-be-processed suffix of the original array.
// For each value we know whether taking one copy would reduce the
// "free" matches we can make later (tight) or not (loose).
class ValueTracker {
public:
    explicit ValueTracker(const std::vector<int>& values) {
        max_value_ = 0;
        for (int v : values) {
            max_value_ = std::max(max_value_, v);
        }
        available_.assign(max_value_ + 1, 0);
        suffix_need_.assign(max_value_ + 1, 0);
        for (int v : values) {
            ++available_[v];
            ++suffix_need_[v];
        }
        matched_ = 0;
        for (int v = 1; v <= max_value_; ++v) {
            matched_ += std::min(available_[v], suffix_need_[v]);
            if (available_[v] > 0) {
                classify_value(v);
            }
        }
    }

    int max_value() const { return max_value_; }

    int remaining(int v) const { return available_[v]; }

    int suffix(int v) const { return suffix_need_[v]; }

    long long matched_total() const { return matched_; }

    const std::set<int>& loose_values() const { return loose_; }
    const std::set<int>& tight_values() const { return tight_; }

    // We move past position i, so the suffix loses one occurrence of values[i].
    void consume_suffix(int v) {
        if (!in_range(v)) return;
        adjust_match(v, 0, -1);
        reclassify(v);
    }

    // We place one copy of value v into the result, so availability shrinks.
    void consume_value(int v) {
        if (!in_range(v)) return;
        adjust_match(v, -1, 0);
        reclassify(v);
    }

private:
    bool in_range(int v) const { return 1 <= v && v <= max_value_; }

    void adjust_match(int v, int delta_available, int delta_suffix) {
        matched_ -= std::min(available_[v], suffix_need_[v]);
        available_[v] += delta_available;
        suffix_need_[v] += delta_suffix;
        matched_ += std::min(available_[v], suffix_need_[v]);
    }

    void classify_value(int v) {
        if (available_[v] == 0) return;
        if (available_[v] > suffix_need_[v]) {
            loose_.insert(v);
        } else {
            tight_.insert(v);
        }
    }

    void reclassify(int v) {
        if (!in_range(v)) return;
        loose_.erase(v);
        tight_.erase(v);
        classify_value(v);
    }

    int max_value_ = 0;
    std::vector<int> available_;
    std::vector<int> suffix_need_;
    long long matched_ = 0;
    // Values where we have spare copies (picking one now does not hurt the suffix).
    std::set<int> loose_;
    // Values that are tightly coupled to the suffix demand (picking one now consumes future budget).
    std::set<int> tight_;
};

int extra_cost(const ValueTracker& tracker, int candidate, int original) {
    if (candidate < 1 || candidate > tracker.max_value()) return std::numeric_limits<int>::max();
    if (tracker.remaining(candidate) == 0) return std::numeric_limits<int>::max();

    // We spend one mismatch if we change the value at this index.
    int cost = (candidate == original) ? 0 : 1;

    // If this value is "tight" (demand >= supply), using it now
    // forces one extra mismatch somewhere in the suffix.
    if (tracker.remaining(candidate) <= tracker.suffix(candidate)) {
        cost += 1;
    }
    return cost;
}

void consider_candidate(const ValueTracker& tracker, int candidate, int original, long long budget, int& best_choice) {
    int cost = extra_cost(tracker, candidate, original);
    if (cost <= budget) {
        if (best_choice == -1 || candidate < best_choice) {
            best_choice = candidate;
        }
    }
}

}

// Greedy construction of the lexicographically smallest permutation that differs
// from the original array in at most k positions. We place elements left to right
// and keep track of how many mismatches we have already spent and how many we are
// forced to spend in the suffix, so we know how much "budget" remains for a smaller
// choice at the current index.
std::vector<int> minimal_lexicographic_list(const std::vector<int>& values, int k) {
    int n = static_cast<int>(values.size());
    if (n == 0) return {};

    ValueTracker tracker(values);
    std::vector<int> result(n);
    int used_mismatches = 0;

    for (int i = 0; i < n; ++i) {
        int current = values[i];

        // Once position i is fixed, the suffix no longer needs values[i].
        tracker.consume_suffix(current);

        int remaining_positions = n - i - 1;
        long long unavoidable = remaining_positions - tracker.matched_total();
        long long budget = static_cast<long long>(k) - (used_mismatches + unavoidable);
        if (budget < 0) budget = -1;

        int choice = -1;
        // Only three categories can produce the optimal next value:
        //  (1) Keep the original value to avoid spending budget.
        //  (2) Take the smallest "loose" value (no extra future mismatch).
        //  (3) Take the smallest "tight" value (would force one future mismatch).
        consider_candidate(tracker, current, current, budget, choice);
        if (!tracker.loose_values().empty()) {
            consider_candidate(tracker, *tracker.loose_values().begin(), current, budget, choice);
        }
        if (!tracker.tight_values().empty()) {
            consider_candidate(tracker, *tracker.tight_values().begin(), current, budget, choice);
        }

        if (choice == -1) {
            choice = current;  // fallback, should not happen but keeps behavior defined
        }

        result[i] = choice;
        if (choice != current) {
            ++used_mismatches;
        }

        tracker.consume_value(choice);
    }

    return result;
}

#if !defined(TEST_BUILD)
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, k;
    if (!(std::cin >> n >> k)) {
        return 0;
    }
    std::vector<int> values(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> values[i];
    }

    std::vector<int> answer = minimal_lexicographic_list(values, k);
    for (int i = 0; i < n; ++i) {
        if (i) std::cout << ' ';
        std::cout << answer[i];
    }
    std::cout << '\n';

    return 0;
}
#endif

Test 1 (public)

Group: 1, 3, 4, 5, 6

Verdict: ACCEPTED

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: ACCEPTED

Test 7

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 8

Group: 1, 4, 5, 6

Verdict: ACCEPTED

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: ACCEPTED

Test 12

Group: 1, 4, 5, 6

Verdict: ACCEPTED

Test 13

Group: 1, 4, 5, 6

Verdict: ACCEPTED

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: ACCEPTED

Test 22

Group: 3, 6

Verdict: ACCEPTED

Test 23

Group: 3, 6

Verdict: ACCEPTED

Test 24

Group: 3, 6

Verdict: ACCEPTED

Test 25

Group: 3, 6

Verdict: ACCEPTED

Test 26

Group: 3, 6

Verdict: ACCEPTED

Test 27

Group: 4, 6

Verdict: ACCEPTED

Test 28

Group: 4, 6

Verdict: ACCEPTED

Test 29

Group: 4, 6

Verdict: ACCEPTED

Test 30

Group: 2, 4, 6

Verdict: ACCEPTED

Test 31

Group: 4, 6

Verdict: ACCEPTED

Test 32

Group: 4, 6

Verdict: ACCEPTED

Test 33

Group: 5, 6

Verdict: ACCEPTED

Test 34

Group: 5, 6

Verdict: ACCEPTED

Test 35

Group: 5, 6

Verdict: ACCEPTED

Test 36

Group: 2, 5, 6

Verdict: ACCEPTED

Test 37

Group: 5, 6

Verdict: ACCEPTED

Test 38

Group: 6

Verdict: ACCEPTED

Test 39

Group: 6

Verdict: ACCEPTED

Test 40

Group: 6

Verdict: ACCEPTED

Test 41

Group: 2, 5, 6

Verdict: ACCEPTED

Test 42

Group: 5, 6

Verdict: ACCEPTED

Test 43

Group: 1, 3, 4, 5, 6

Verdict: ACCEPTED

Test 44

Group: 1, 2, 4, 5, 6

Verdict: ACCEPTED

Test 45

Group: 1, 4, 5, 6

Verdict: ACCEPTED