Käännöt

// #[cfg(test)]
// mod tests;

use std::io::stdin;
use std::vec::Vec;

struct Operator {
    array: Vec<i32>,
    flip_length: usize,
    flip_record: Vec<usize>
}
impl Operator {
    pub fn new(array: Vec<i32>, flip_length: usize) -> Self {
        Self  {
            array,
            flip_length,
            flip_record: Vec::new()
        }
    }

    pub fn flip(&mut self, first_moving_index: usize) {
        flip(&mut self.array, first_moving_index, self.flip_length);
        self.flip_record.push(first_moving_index)
    }
}

fn flip(array: &mut Vec<i32>, first_moving_index: usize, flip_length: usize) {
    let last_moving_index = first_moving_index + flip_length - 1;

    for i in 0..flip_length / 2 {
        (array[first_moving_index + i], array[last_moving_index - i]) = (array[last_moving_index - i], array[first_moving_index + i])
    }
}

//inefficient
fn get_index_of_item_to_move(operator: &Operator, destination: usize) -> Option<usize> {
    let value = *operator.array
        .iter()
        .skip(destination)
        .min()
        .unwrap();

    for i in destination..operator.array.len() {
        if operator.array[i] == value {

            //with an odd flip_length, elements can only be moved by even amounts
            let movement_is_possible = operator.flip_length % 2 == 0 ||
                (i - destination) % 2 == 0;
            
            if movement_is_possible {
                return Some(i);
            }
        }
    }

    None
}

fn bring_to_proximity(operator: &mut Operator, destination: usize, mut index_to_move: usize) -> usize {
    assert!(destination <= index_to_move);

    let movement_amount = operator.flip_length - 1;
    while (index_to_move - destination) >= movement_amount {
        let new_position = index_to_move - movement_amount;
        operator.flip(new_position);
        index_to_move = new_position;
    }
    index_to_move
}

//it is assumed that the position_before_flip is within the flip range
fn get_position_after_flip(position_before_flip: usize, first_moving_index: usize, flip_length: usize) -> usize {
    let last_moving_index = first_moving_index + flip_length - 1;
    first_moving_index + (last_moving_index - position_before_flip)
}

fn fine_tune_position(operator: &mut Operator, destination: usize, mut index_to_move: usize) {
    assert!(destination <= index_to_move);

    //make sure the distance is even
    if (index_to_move - destination) % 2 == 1 {
        assert!(operator.flip_length % 2 == 0);
        operator.flip(destination);
        index_to_move = get_position_after_flip(index_to_move, destination, operator.flip_length);
    }

    let step_count = (index_to_move - destination) / 2;
    for _ in 0..step_count {
        //move index_to_move 2 places left (towards destination)
        operator.flip(destination + 1);
        operator.flip(destination);
    }
}

fn sort_array(operator: &mut Operator) -> bool {
    for destination in 0..(operator.array.len() - operator.flip_length) {
        let mut index_to_move = match get_index_of_item_to_move(operator, destination) {
            Some(index) => index,
            None => return false
        };

        index_to_move = bring_to_proximity(operator, destination, index_to_move);
        fine_tune_position(operator, destination, index_to_move);
    }

    let end: Vec<i32> = operator.array[(operator.array.len() - operator.flip_length)..operator.array.len()]
        .iter().copied().collect();
    let end_is_sorted = end.windows(2).all(|w| w[0] <= w[1]);
    let end_is_reverse_sorted = end.windows(2).all(|w| w[0] >= w[1]);

    if end_is_sorted {
        return true;
    }
    else if end_is_reverse_sorted {
        operator.flip(operator.array.len() - operator.flip_length);
        return true;
    }
    else {
        return false;//might still be sortable!
    }
}

fn main() {
    let mut input = stdin().lines();

    let line = input.next().unwrap().unwrap();
    let mut split = line.split_whitespace();
    let _length: usize = split.next().unwrap().parse().unwrap();
    let flip_length: usize = split.next().unwrap().parse().unwrap();

    let line = input.next().unwrap().unwrap();
    let array: Vec<i32> = line
        .split_whitespace()
        .map(|s| s.parse().unwrap())
        .collect();

    let mut operator = Operator::new(array, flip_length);
    let sorting_successful = sort_array(&mut operator);

    if sorting_successful {
        println!("YES");
    }
    else {
        println!("NO");
        return;
    }

    let flip_string = operator.flip_record
        .iter()
        .map(|&i| i + 1)
        .map(|i| i.to_string())
        .reduce(|acc, s| format!("{acc} {s}"))
        .unwrap_or_default();
    println!("{}", operator.flip_record.len());
    println!("{flip_string}");
}

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: TIME LIMIT EXCEEDED

Test 17

Group: 3

Verdict: ACCEPTED

Test 18

Group: 3

Verdict: ACCEPTED

Test 19

Group: 3

Verdict: ACCEPTED

Test 20

Group: 3

Verdict: WRONG ANSWER

Test 21

Group: 3

Verdict: WRONG ANSWER

Test 22

Group: 3

Verdict: WRONG ANSWER

Test 23

Group: 3

Verdict: ACCEPTED

Test 24

Group: 3

Verdict: ACCEPTED

Test 25

Group: 3

Verdict: WRONG ANSWER

Test 26

Group: 4

Verdict: ACCEPTED

Test 27

Group: 4

Verdict: ACCEPTED

Test 28

Group: 4

Verdict: ACCEPTED

Test 29

Group: 4

Verdict: WRONG ANSWER

Test 30

Group: 4

Verdict: WRONG ANSWER

Test 31

Group: 4

Verdict: WRONG ANSWER

Test 32

Group: 4

Verdict: ACCEPTED

Test 33

Group: 4

Verdict: ACCEPTED

Test 34

Group: 4

Verdict: WRONG ANSWER