Käännöt

warning: unused variable: `rng`
  --> input/code.rs:98:13
   |
98 |     let mut rng = StdRng::from_entropy();
   |             ^^^ help: if this is intentional, prefix it with an underscore: `_rng`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `end_is_sorted`
   --> input/code.rs:177:9
    |
177 |     let end_is_sorted = end.windows(2).all(|w| w[0] <= w[1]);
    |         ^^^^^^^^^^^^^ help: if this is intentional, prefix it with an underscore: `_end_is_sorted`

warning: unused variable: `end_is_reverse_sorted`
   --> input/code.rs:178:9
    |
178 |     let end_is_reverse_sorted = end.windows(2).all(|w| w[0] >= w[1]);
    |         ^^^^^^^^^^^^^^^^^^^^^ help: if this is intentional, prefix it with an underscore: `_end_is_reverse_sorted`

warning: variable does not need to be mutable
  --> input/code.rs:98:9
   |
98 |     let mut rng = StdRng::from_entropy();
   |         ----^^^
   |         |
   |         help: remove this `mut`
   |
   = note: `...

#[cfg(test)]
mod tests;

use std::io::stdin;
use std::vec::Vec;
use rand::prelude::*;

#[derive(Debug, Clone)]
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 bogo_sort(operator: Operator) -> Option<Operator> {
    let mut rng = StdRng::from_entropy();

    let attempts = vec![
        vec![],
        vec![2, 0, 1, 0, 1, 0, 2, 0, 1],
        vec![2, 0, 1, 2, 1, 2, 1, 0, 1],
        vec![1, 0, 2, 1, 0, 1, 0, 1],
        vec![2],
        vec![1, 0, 1, 2, 1, 2, 1, 0],
        vec![0, 2, 1, 2, 1, 2, 0, 1],
        vec![0, 1, 2, 0, 2, 1, 0, 2],
        vec![0, 2, 1, 2, 0, 1, 0, 1],
        vec![0, 1, 0, 2, 0, 1, 0],
        vec![0, 1, 0, 1, 0, 2, 0, 1],
        vec![1, 0, 1, 0, 2, 1, 2, 0],
    ];

    for attempt in attempts {
        let mut test_operator = operator.clone();
        for i in attempt {
            test_operator.flip(i)
        }

        let is_sorted = test_operator.array.windows(2).all(|w| w[0] <= w[1]);
        if is_sorted {
            return Some(test_operator);
        }
    }

    // let first_moving_index_range = 0..(operator.array.len() - operator.flip_length);

    // for _ in 0..100_000 {
    //     let mut test_operator = operator.clone();

    //     for _ in 0..100 {
    //         let first_moving_index = rng.gen_range(first_moving_index_range.clone());
    //         test_operator.flip(first_moving_index);

    //         let is_sorted = test_operator.array.windows(2).all(|w| w[0] <= w[1]);

    //         if is_sorted {
    //             return Some(test_operator);
    //         }
    //     }
    // }

    None
}

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

    if operator.flip_length > 3 {
        let end_start = if operator.array.len() >= 6 { operator.array.len() - 6 } else { 0 };
        let end: Vec<i32> = operator.array[end_start..operator.array.len()]
            .iter().copied().collect();
        let end_operator = Operator::new(end, operator.flip_length);

        match bogo_sort(end_operator) {
            Some(successful_end_operator) => {
                for i in successful_end_operator.flip_record {
                    operator.flip(end_start + i);
                }
                return true;
            },
            None => return false
        }
    }

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

    println!("{}", operator.flip_record.len());
    operator.flip_record
        .iter()
        .map(|&i| i + 1)
        .map(|i| i.to_string())
        .for_each(|s| print!("{s} "));
    println!("");
}

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 'index out of bounds: the len is 5 but the index is 5', input/co...

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

thread 'main' panicked at 'index out of bounds: the len is 5 but the index is 6', input/co...

Test 28

Group: 4

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 6 but the index is 6', input/co...

Test 29

Group: 4

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 6 but the index is 6', input/co...

Test 30

Group: 4

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 6 but the index is 6', input/co...

Test 31

Group: 4

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 6 but the index is 6', input/co...

Test 32

Group: 4

Verdict: ACCEPTED

Test 33

Group: 4

Verdict: ACCEPTED

Test 34

Group: 4

Verdict: RUNTIME ERROR

thread 'main' panicked at 'index out of bounds: the len is 6 but the index is 6', input/co...