Käännöt

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.
            {
                if k == 4 {
                    todo!("Block purge for k=4 not implemented!");
                } 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 - 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 '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.
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: RUNTIME ERROR

thread 'main' panicked at 'not yet implemented: Block purge for k=4 not implemented!', inp...

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: RUNTIME ERROR

thread 'main' panicked at 'not yet implemented: Block purge for k=4 not implemented!', inp...

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