Käännöt

use std::io;
use std::process::exit;

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]);
        }
    };

    fn impossible() {
        println!("NO");
        exit(0);
    }

    for number in 1..=list_length {
        // Move the number so it can be moved only using jumps of length possible_jump_lengths[0].
        'initial_move: {
            let remainder = (*&index_table[number] - number) % possible_jump_lengths[0];
            if remainder != 0 {
                // Try jumping either to the left or right.
                for jump in [-(remainder as isize), (possible_jump_lengths[0] - remainder) as isize] {
                    let jump_length_index = match possible_jump_lengths.iter().position(|&x| x == jump.unsigned_abs()) {
                        None => { continue; } // If a jump of this size is not possible, continue.
                        Some(index) => { index }
                    };

                    let start_index = *&index_table[number] as isize - jump.abs() + jump_length_index as isize * jump.signum();
                    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;
                    }

                    // If this is reached, everything is fine, so the flip can be done.
                    flip(start_index as usize, &mut number_table, &mut index_table);

                    // The number can be flipped to the right.
                    break 'initial_move
                }

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

        // 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{}\n{}", instructions.len(), instructions.iter().map(|x| x.to_string()).collect::<Vec<String>>().join(" "));
}

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

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: WRONG ANSWER

Test 19

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 501 but the index is 1844674407...

Test 20

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 501 but the index is 1844674407...

Test 21

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 501 but the index is 1844674407...

Test 22

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 501 but the index is 1844674407...

Test 23

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 501 but the index is 1844674407...

Test 24

Group: 3

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 501 but the index is 1844674407...

Test 25

Group: 3

Verdict: WRONG ANSWER

Test 26

Group: 4

Verdict: ACCEPTED

Test 27

Group: 4

Verdict: ACCEPTED

Test 28

Group: 4

Verdict: WRONG ANSWER

Test 29

Group: 4

Verdict: WRONG ANSWER

Test 30

Group: 4

Verdict: WRONG ANSWER

Test 31

Group: 4

Verdict: ACCEPTED

Test 32

Group: 4

Verdict: ACCEPTED

Test 33

Group: 4

Verdict: WRONG ANSWER

Test 34

Group: 4

Verdict: WRONG ANSWER