힌트 $i$번째 교환 후 $A$의 특정 범위의 값을 알 수 있습니다.

핵심 아이디어 선택 정렬은 문제 설명과 같이 최댓값을 한 번 찾고, 교환을 최대 한 번 하는 동작을 $N - 1$번만 반복합니다. 특히, $i$번째 교환에서 마지막 $i$개의 값이 모두 정렬됩니다.

알고리즘

이미 정렬된 배열과 뒤쪽 위치부터 비교하여 제자리에 있지 않은 값을 옮겨 주는 동작을 반복하는 식으로 문제를 해결할 수 있습니다.

가장 큰 원소를 찾아서 맨 뒤로 옮기는 과정

먼저 각 수의 처음 위치를 각 수의 크기 순으로 배열 $S$에 저장하고, 뒤부터 탐색하면서 $S[i]$가 $i$가 아니라면 (즉 숫자가 제자리에 있지 않다면) $A$에서 $S[i]$번째 수와 i번째 수를 바꿔야 합니다. 이때 $A$에서 $S[i]$번째 수에 해당하는 $S$의 값 또한 갱신해야 하는데, 이를 위해 $M[i] = k$이면 $A[i]$가 $A$에서 $k$번째로 큰 수이도록 하는 배열 $M$을 만들어줍니다. $M$은 $S$의 인덱스와 값을 맞바꾼 배열이며, $S[M[i]]$가 $A$에서 $S[i]$번째 수에 해당하는 $S$의 값임을 알 수 있습니다. 따라서 $S[M[i]]$를 $S[i]$로 바꾸고, $A$와 $M$에서 각각 $S[i]$번째와 $i$번째 수를 교환하는 방식으로 위치를 업데이트할 수 있습니다.

선택 정렬은 $O(n^2)$ 시간복잡도를 가지지만 $O(n\log n)$ 알고리즘을 사용하여 정렬한 후, 위와 같이 제자리를 찾아가는 알고리즘을 짜면 전체 시간 $O(n \log n) + O(n) = O(n \log n)$에 문제를 해결할 수 있습니다.

코드(23884번) 
use std::io::{stdin, Read};
fn main() {
    let mut input = String::new();
    stdin().read_to_string(&mut input).unwrap();
    let mut input = input.split_ascii_whitespace().map(str::parse).flatten();
    let n = input.next().unwrap();
    let mut k = input.next().unwrap();
    let mut a: Vec<_> = input.take(n).collect();
    let mut sorted: Vec<_> = (0..n).collect();
    sorted.sort_unstable_by_key(|&i| a[i]);
    let mut map = vec![0; n];
    for (i, &j) in sorted.iter().enumerate() {
        map[j] = i;
    }
    use std::fmt::Write;
    let mut output = String::new();
    for i in (0..n).rev() {
        if sorted[i] != i {
            sorted[map[i]] = sorted[i];
            map.swap(sorted[i], i);
            a.swap(sorted[i], i);
            k -= 1;
            if k == 0 {
                for ai in &a {
                    write!(output, "{} ", ai).unwrap();
                }
                break;
            }
        }
    }
    if k > 0 {
        println!("-1");
    } else {
        print!("{}", output);
    }
}