Käännöt

use rand::prelude::*;
use std::io;

fn main() {
    let (k, mut list) = get_k_and_list();

    let result = match k {
        2 => solve2(&mut list),
        3 => solve3(&list),
        4 => solve4(&mut list),
        5 => todo!(),
        _ => panic!("k should be in range 2..5"),
    };
    dbg!(&list);
    print_results(&result);
}

fn get_k_and_list() -> (usize, Vec<i32>) {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let mut nums = input
        .split_whitespace()
        .map(|x| x.parse::<usize>().unwrap());
    let _n = nums.next().unwrap();
    let k = nums.next().unwrap();

    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let list = input
        .split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect();

    (k, list)
}

fn solve2(list: &mut [i32]) -> Option<Vec<usize>> {
    Some(sort2(list))
}

fn sort2(list: &mut [i32]) -> Vec<usize> {
    let n = list.len();
    let mut result = Vec::new();
    for m in (2..=n).rev() {
        for i in 0..m - 1 {
            if list[i] > list[i + 1] {
                list.swap(i, i + 1);
                result.push(i);
            }
        }
    }
    result
}

fn solve3(list: &[i32]) -> Option<Vec<usize>> {
    let mut part1: Vec<i32> = list.iter().cloned().step_by(2).collect();
    let mut part2: Vec<i32> = list.iter().cloned().skip(1).step_by(2).collect();
    if part1.iter().any(|x| x % 2 != 1) || part2.iter().any(|x| x % 2 != 0) {
        return None;
    }
    let mut seq1 = sort2(&mut part1);
    let mut seq2 = sort2(&mut part2);
    seq1.iter_mut().for_each(|x| *x *= 2);
    seq2.iter_mut().for_each(|x| *x = 2 * *x + 1);
    seq1.append(&mut seq2);

    Some(seq1)
}

fn solve4(list: &mut [i32]) -> Option<Vec<usize>> {
    let n = list.len();
    let mut result = Vec::new();
    for m in (7..=n).rev() {
        let mut i = list
            .iter()
            .position(|&x| x == m as i32)
            .expect("the list should have all elements 1..n");
        while i < m - 3 {
            reverse(i, list, &mut result);
            i += 3;
        }
        finish4(i, m, list, &mut result);
    }
    let possible = finish_finish4(&mut list[..6], &mut result);
    if possible {
        Some(result)
    } else {
        None
    }
}

fn reverse(i: usize, list: &mut [i32], result: &mut Vec<usize>) {
    list[i..i + 4].reverse();
    result.push(i);
}

fn finish4(i: usize, m: usize, list: &mut [i32], result: &mut Vec<usize>) {
    match m - i {
        1 => (),
        2 => {
            reverse(m - 4, list, result);
            reverse(m - 5, list, result);
            reverse(m - 4, list, result);
        }
        3 => {
            reverse(m - 5, list, result);
            reverse(m - 4, list, result);
        }
        _ => panic!("unexpected m - i. m: {} i: {}", m, i),
    }
}

fn finish_finish4(list: &mut [i32], result: &mut Vec<usize>) -> bool {
    let mut rng = rand::thread_rng();
    for _ in 0..10_000 {
        if let [1, 2, 3, 4, 5, 6] = list {
            return true;
        }
        let i = rng.gen_range(0..3);
        reverse(i, list, result)
    }
    false
}

fn print_results(result: &Option<Vec<usize>>) {
    match result {
        None => {
            println!("NO")
        }
        Some(ops) => {
            println!("YES");
            println!("{}", ops.len());
            println!(
                "{}",
                ops.iter()
                    .map(|x| (x + 1).to_string())
                    .collect::<Vec<_>>()
                    .join(" ")
            );
        }
    }
}

Test 1

Group: 1

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    1,
    2,
    3,
    4,
    5,
]

Test 2

Group: 1

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    1,
    2,
    3,
    4,
    5,
]

Test 3

Group: 1

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9...

Test 4

Group: 1

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9...

Test 5

Group: 1

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9...

Test 6

Group: 2

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    1,
    2,
    3,
    4,
    5,
]

Test 7

Group: 2

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    3,
    5,
    4,
    1,
    2,
]

Test 8

Group: 2

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    5,
    2,
    1,
    4,
    3,
]

Test 9

Group: 2

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    19,
    14,
    1,
    18,
    3,
    4,
    11,
    20,...

Test 10

Group: 2

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    9,
    6,
    13,
    18,
    5,
    10,
    3,
    2,...

Test 11

Group: 2

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    53,
    52,
    21,
    76,
    25,
    142,
    5,
    4...

Test 12

Group: 2

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    51,
    44,
    147,
    172,
    1,
    28,
    27,...

Test 13

Group: 2

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    75,
    46,
    179,
    62,
    221,
    14,
    67,...

Test 14

Group: 2

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    161,
    54,
    285,
    12,
    71,
    142,
    111,...

Test 15

Group: 2

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    122,
    260,
    455,
    113,
    315,
    276,
    433...

Test 16

Group: 2

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    499,
    500,
    497,
    498,
    495,
    496,
    493...

Test 17

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'range end index 6 out of range for slice of length 5', input/co...

Test 18

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'range end index 6 out of range for slice of length 5', input/co...

Test 19

Group: 3

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9...

Test 20

Group: 3

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9...

Test 21

Group: 3

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9...

Test 22

Group: 3

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9...

Test 23

Group: 3

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9...

Test 24

Group: 3

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    2,
    4,
    5,
    1,
    3,
    6,
    7,
    8,
    9...

Test 25

Group: 3

Verdict: ACCEPTED

[input/code.rs:14] &list = [
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9...

Test 26

Group: 4

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not yet implemented', input/code.rs:11:14
note: run with `RUST_...

Test 27

Group: 4

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not yet implemented', input/code.rs:11:14
note: run with `RUST_...

Test 28

Group: 4

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not yet implemented', input/code.rs:11:14
note: run with `RUST_...

Test 29

Group: 4

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not yet implemented', input/code.rs:11:14
note: run with `RUST_...

Test 30

Group: 4

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not yet implemented', input/code.rs:11:14
note: run with `RUST_...

Test 31

Group: 4

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not yet implemented', input/code.rs:11:14
note: run with `RUST_...

Test 32

Group: 4

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not yet implemented', input/code.rs:11:14
note: run with `RUST_...

Test 33

Group: 4

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not yet implemented', input/code.rs:11:14
note: run with `RUST_...

Test 34

Group: 4

Verdict: RUNTIME ERROR

thread 'main' panicked at 'not yet implemented', input/code.rs:11:14
note: run with `RUST_...