Käännöt

warning: variable does not need to be mutable
  --> input/code.rs:92:37
   |
92 | ...                   let mut sequence: [isize; 8] = // These are some very funny sequences I came up with.
   |                           ----^^^^^^^^
   |                           |
   |                           help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

warning: 1 warning emitted

use std::{cmp, io};
fn main() {
    let stdin = io::stdin();

    let (list_length, k) = {
        let mut input: String = String::new();
        stdin.read_line(&mut input).unwrap();
        let input = input.trim_end();

        let mut values = input.split_whitespace().map(|value| {
            value.parse::<usize>().unwrap()
        });

        (values.next().unwrap(), values.next().unwrap())
    };

    let possible_jump_lengths = get_possible_jump_lengths(k);

    // Maps indices to their numbers, (basically) starts from 1
    let mut number_table: Vec<usize> = {
        let mut input: String = String::new();
        stdin.read_line(&mut input).unwrap();
        let input = input.trim_end();

        let values = input.split_whitespace().map(|value| {
            value.parse::<usize>().unwrap()
        });

        values.take(list_length).collect()
    };
    number_table.insert(0, 0); // table[0] = 0 so the list basically starts indexing from 1.

    // Maps numbers to their indices, (basically) starts from 1
    let mut index_table: Vec<usize> = vec![0; list_length + 1];
    for (i, x) in number_table.iter().enumerate() {
        index_table[*x] = i
    }


    let mut instructions: Vec<usize> = Vec::new();

    let mut flip = |start_index: usize, number_table: &mut Vec<usize>, index_table: &mut Vec<usize>| {
        instructions.push(start_index);
        for (i, jump) in possible_jump_lengths.iter().enumerate() {
            let a_index = start_index + i;
            let b_index = a_index + jump;
            number_table.swap(a_index, b_index);
            index_table.swap(number_table[b_index], number_table[a_index]);
        }
    };

    for number in 1..=list_length {
        // Move the number so it can be moved only using jumps of `possible_jump_lengths[0]` length.
        'initial_move: {
            let remainder = (*&index_table[number] - number) % possible_jump_lengths[0];
            if remainder == 0 {
                // Nothing needs to be done
                break 'initial_move;
            }

            // Try jumping either to the left or right.
            for total_jump in [-(remainder as isize), (possible_jump_lengths[0] - remainder) as isize] {
                match try_jump(number, list_length, k, total_jump, &mut index_table, &possible_jump_lengths) {
                    None => {}
                    Some(start_indices) => {
                        for start_index in start_indices {
                            flip(start_index, &mut number_table, &mut index_table);
                        }
                        break 'initial_move;
                    }
                }
            }

            // If both jumps have been unsuccessfully tried (and the code hasn't broken out yet), the number is impossible to move by normal means.

            // Attempt block purge.
            // Please stop reading this code by now. This gets really messy.
            {
                if k == 4 && number > 2 {
                    // For some reason, the same sequence can be done backwards with different results, so we try both here.
                    'k4_loop: for method in [1, 2] {
                        let start = cmp::min(number - 1, list_length - possible_jump_lengths[0]) as isize;
                        let expected_number_index = start + if method == 1 { 3 } else { 2 }; // Where THE number should be when beginning.

                        match try_jump(number, list_length, k, index_table[number] as isize - expected_number_index, &mut index_table, &possible_jump_lengths) {
                            Some(start_indices) => {
                                // Move to suitable start position.
                                for start_index in start_indices {
                                    flip(start_index, &mut number_table, &mut index_table);
                                }

                                let mut sequence: [isize; 8] = // These are some very funny sequences I came up with.
                                    if method == 1 { [-2, 0, -1, 0, -2, -1, -2, -1] }
                                    else { [-1, -2, -1, -2, 0, -1, 0, -2] };

                                for entry in sequence {
                                    flip((start + entry) as usize, &mut number_table, &mut index_table);
                                }
                                break 'k4_loop;
                            }
                            _ => {}
                        }
                    }

                } else if k == 5 && number > 3 {
                    let start = cmp::min(number - 1, list_length - possible_jump_lengths[0]) as isize;
                    let expected_number_index = start + 3; // Where THE number should be when beginning.

                    match try_jump(number, list_length, k, index_table[number] as isize - expected_number_index, &mut index_table, &possible_jump_lengths) {
                        Some(start_indices) => {
                            // Move to suitable start position.
                            for start_index in start_indices {
                                flip(start_index, &mut number_table, &mut index_table);
                            }

                            let sequence: [isize; 7] = [0, -1, -2, -3, -1, -3, 0]; // This is a very funny sequence I came up with.
                            for entry in sequence {
                                flip((start + entry) as usize, &mut number_table, &mut index_table);
                            }
                        }
                        _ => {}
                    }
                }

                if *&index_table[number] == number {
                    break 'initial_move;
                }
            }

            println!("NO");
            return;
        }

        // Do maximum length jumps until the number is in place.
        while *&index_table[number] != number {
            let start_index = *&index_table[number] - possible_jump_lengths[0]; // Calculate where the flip would start.
            flip(start_index, &mut number_table, &mut index_table); // Flip
        }
    }

    println!("YES\n{}", instructions.len());
    if instructions.len() > 0 {
        println!("{}", instructions.iter().map(|x| x.to_string()).collect::<Vec<String>>().join(" "))
    }
}

fn try_jump(number: usize, list_length: usize, k: usize, total_jump: isize, index_table: &mut Vec<usize>, possible_jump_lengths: &Vec<usize>) -> Option<Vec<usize>> {
    if total_jump == 0 {
        return Some(vec![]);
    }

    // Try all good methods of getting there.
    'jump_combination_loop: for jump_combination in get_possible_jump_combinations(total_jump, k) {
        let mut start_indices = Vec::new();
        let mut future_index = *&index_table[number] as isize;
        // Check the jump combination is doable.
        for jump in jump_combination {
            let jump_length_index = match possible_jump_lengths.iter().position(|&x| x == jump.unsigned_abs()) {
                None => {
                    // If a jump of this size is not possible, continue.
                    continue 'jump_combination_loop;
                }
                Some(index) => { index }
            };

            let start_index = future_index - if jump > 0 { jump_length_index as isize } else { possible_jump_lengths[0] as isize - jump_length_index as isize };
            let end_index = start_index + possible_jump_lengths[0] as isize;

            // Validate everything is within bounds.
            if start_index < number as isize || end_index > list_length as isize {
                continue 'jump_combination_loop;
            }

            start_indices.push(start_index as usize);
            future_index += jump;
        };

        // If this is reached, everything is fine, so the flip(s) can be done.
        return Some(start_indices);
    }
    return None;
}

fn get_possible_jump_lengths(k: usize) -> Vec<usize> {
    (0..k).rev().step_by(2).collect()
}

/// Returns all good combinations of jumps in preferred order to achieve moving an item by `total_length`.
/// `abs(total_length) < k`.
/// For example, total_length = 4 could be achieved using 2 + 2 jumps. However, 2 - 2 + 2 + 2 would not be returned despite being also valid.
/// Side note: I was too lazy to make this a working code so I just did it manually. Please just go away instead of burning your eyes.
fn get_possible_jump_combinations(total_length: isize, k: usize) -> Vec<Vec<isize>> {
    assert!(total_length.unsigned_abs() < k, "Too large total length!");

    let mut combinations = vec![vec![total_length]];
    let sign = total_length.signum();

    if k == 3 {
        if total_length.abs() == 1 {
            return vec![];
        }
    } else if k == 4 {
        match total_length.abs() {
            1 => {
                combinations.push(vec![3 * sign, -1 * sign, -1 * sign]);
                combinations.push(vec![-1 * sign, 3 * sign, -1 * sign]);
                combinations.push(vec![-1 * sign, -1 * sign, 3 * sign]);
            },
            2 => {
                combinations.push(vec![1 * sign, 1 * sign]);
                combinations.push(vec![3 * sign, -1 * sign]);
                combinations.push(vec![-1 * sign, 3 * sign]);
            }
            3 => {
                combinations.push(vec![1 * sign, 1 * sign, 1 * sign]);
            }
            _ => {}
        }
    } else if k == 5 {
        match total_length.abs() {
            1 => return vec![],
            2 => {
                combinations.push(vec![4 * sign, -2 * sign]);
                combinations.push(vec![-2 * sign, 4 * sign]);
            }
            3 => return vec![],
            4 => {
                combinations.push(vec![2 * sign, 2 * sign]);
            }
            _ => {}
        }
    }

    combinations
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 2

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 3

Verdict: ACCEPTED

Test 18

Group: 3

Verdict: ACCEPTED

Test 19

Group: 3

Verdict: ACCEPTED

Test 20

Group: 3

Verdict: ACCEPTED

Test 21

Group: 3

Verdict: ACCEPTED

Test 22

Group: 3

Verdict: ACCEPTED

Test 23

Group: 3

Verdict: ACCEPTED

Test 24

Group: 3

Verdict: ACCEPTED

Test 25

Group: 3

Verdict: ACCEPTED

Test 26

Group: 4

Verdict: ACCEPTED

Test 27

Group: 4

Verdict: ACCEPTED

Test 28

Group: 4

Verdict: ACCEPTED

Test 29

Group: 4

Verdict: ACCEPTED

Test 30

Group: 4

Verdict: ACCEPTED

Test 31

Group: 4

Verdict: ACCEPTED

Test 32

Group: 4

Verdict: ACCEPTED

Test 33

Group: 4

Verdict: ACCEPTED

Test 34

Group: 4

Verdict: ACCEPTED