Käännöt

error[E0432]: unresolved import `rand_chacha`
 --> input/code.rs:2:5
  |
2 | use rand_chacha::ChaCha8Rng;
  |     ^^^^^^^^^^^ use of undeclared crate or module `rand_chacha`

warning: unused import: `rand::prelude`
 --> input/code.rs:1:5
  |
1 | use rand::prelude::*;
  |     ^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

error: aborting due to previous error; 1 warning emitted

For more information about this error, try `rustc --explain E0432`.

use rand::prelude::*;
use rand_chacha::ChaCha8Rng;
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 = ChaCha8Rng::seed_from_u64(2);
    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(" ")
            );
        }
    }
}