アルゴリズムと数学 027

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_aa

マージソートを実装するだけです。
URLはExcel方式ですね。

// Sorting
#![allow(non_snake_case)]

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}

fn read_input() -> Vec<i32> {
    let _N: usize = read();
    let A = read_vec();
    A
}

fn merge_sort(A: Vec<i32>) -> Vec<i32> {
    if A.len() == 1 {
        return A
    }
    
    let N = A.len();
    let M = N / 2;
    let A1 = merge_sort((0..M).map(|i| A[i]).collect::<Vec<i32>>());
    let A2 = merge_sort((M..N).map(|i| A[i]).collect::<Vec<i32>>());
    
    let mut B = Vec::<i32>::new();
    let mut k = 0;
    let mut l = 0;
    while k < M && l < N - M {
        if A1[k] <= A2[l] {
            B.push(A1[k]);
            k += 1
        }
        else {
            B.push(A2[l]);
            l += 1
        }
    }
    while k < M {
        B.push(A1[k]);
        k += 1
    }
    while l < N - M {
        B.push(A2[l]);
        l += 1
    }
    B
}

fn f(A: Vec<i32>) {
    let B = merge_sort(A);
    println!("{}", B.iter().map(|e| e.to_string()).
                            collect::<Vec<String>>().join(" "))
}

fn main() {
    let A = read_input();
    f(A)
}