Task: | Käännöt |
Sender: | Roopekt |
Submission time: | 2023-11-12 23:27:12 +0200 |
Language: | Rust |
Status: | READY |
Result: | 32 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 13 |
#2 | ACCEPTED | 19 |
#3 | RUNTIME ERROR | 0 |
#4 | RUNTIME ERROR | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1 | details |
#2 | ACCEPTED | 0.00 s | 1 | details |
#3 | ACCEPTED | 0.00 s | 1 | details |
#4 | ACCEPTED | 0.00 s | 1 | details |
#5 | ACCEPTED | 0.00 s | 1 | details |
#6 | ACCEPTED | 0.00 s | 2 | details |
#7 | ACCEPTED | 0.00 s | 2 | details |
#8 | ACCEPTED | 0.00 s | 2 | details |
#9 | ACCEPTED | 0.00 s | 2 | details |
#10 | ACCEPTED | 0.00 s | 2 | details |
#11 | ACCEPTED | 0.01 s | 2 | details |
#12 | ACCEPTED | 0.01 s | 2 | details |
#13 | ACCEPTED | 0.01 s | 2 | details |
#14 | ACCEPTED | 0.01 s | 2 | details |
#15 | ACCEPTED | 0.00 s | 2 | details |
#16 | ACCEPTED | 0.01 s | 2 | details |
#17 | ACCEPTED | 0.00 s | 3 | details |
#18 | RUNTIME ERROR | 0.00 s | 3 | details |
#19 | ACCEPTED | 0.01 s | 3 | details |
#20 | ACCEPTED | 0.01 s | 3 | details |
#21 | ACCEPTED | 0.01 s | 3 | details |
#22 | ACCEPTED | 0.01 s | 3 | details |
#23 | ACCEPTED | 0.01 s | 3 | details |
#24 | ACCEPTED | 0.00 s | 3 | details |
#25 | ACCEPTED | 0.01 s | 3 | details |
#26 | ACCEPTED | 0.00 s | 4 | details |
#27 | RUNTIME ERROR | 0.00 s | 4 | details |
#28 | RUNTIME ERROR | 0.00 s | 4 | details |
#29 | RUNTIME ERROR | 0.00 s | 4 | details |
#30 | RUNTIME ERROR | 0.00 s | 4 | details |
#31 | RUNTIME ERROR | 0.00 s | 4 | details |
#32 | ACCEPTED | 0.00 s | 4 | details |
#33 | ACCEPTED | 0.01 s | 4 | details |
#34 | RUNTIME ERROR | 0.00 s | 4 | details |
Compiler report
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: `...
Code
#[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])}}//inefficientfn 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 amountslet 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 rangefn 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 evenif (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 details
Test 1
Group: 1
Verdict: ACCEPTED
input |
---|
5 2 1 2 3 4 5 |
correct output |
---|
YES 0 |
user output |
---|
YES 0 |
Test 2
Group: 1
Verdict: ACCEPTED
input |
---|
5 2 2 1 3 4 5 |
correct output |
---|
YES 1 1 |
user output |
---|
YES 1 1 |
Test 3
Group: 1
Verdict: ACCEPTED
input |
---|
20 2 6 20 18 2 16 13 19 17 8 14 11 ... |
correct output |
---|
YES 366 2 3 4 5 6 7 8 9 10 11 12 13 14... |
user output |
---|
YES 132 19 18 17 16 15 14 13 12 11 10 ... Truncated |
Test 4
Group: 1
Verdict: ACCEPTED
input |
---|
100 2 100 92 62 88 12 7 43 31 19 72 ... |
correct output |
---|
YES 2876 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
YES 2438 77 76 75 74 73 72 71 70 69 68 ... Truncated |
Test 5
Group: 1
Verdict: ACCEPTED
input |
---|
100 2 100 99 98 97 96 95 94 93 92 91... |
correct output |
---|
YES 5248 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
user output |
---|
YES 4950 99 98 97 96 95 94 93 92 91 90 ... Truncated |
Test 6
Group: 2
Verdict: ACCEPTED
input |
---|
5 3 1 2 3 4 5 |
correct output |
---|
YES 0 |
user output |
---|
YES 0 |
Test 7
Group: 2
Verdict: ACCEPTED
input |
---|
5 3 3 5 4 1 2 |
correct output |
---|
NO |
user output |
---|
NO |
Test 8
Group: 2
Verdict: ACCEPTED
input |
---|
5 3 5 2 1 4 3 |
correct output |
---|
YES 8 1 2 1 3 1 2 3 1 |
user output |
---|
YES 2 1 3 |
Test 9
Group: 2
Verdict: ACCEPTED
input |
---|
20 3 19 14 1 18 3 4 11 20 13 6 17 8... |
correct output |
---|
YES 52 8 10 12 14 16 18 1 3 5 7 9 11 ... |
user output |
---|
YES 42 1 12 10 8 6 4 2 3 6 4 11 9 7 5... Truncated |
Test 10
Group: 2
Verdict: ACCEPTED
input |
---|
20 3 9 6 13 18 5 10 3 2 7 20 1 4 19... |
correct output |
---|
YES 50 10 12 14 16 18 13 15 17 4 6 8 ... |
user output |
---|
YES 34 9 7 5 3 1 6 4 2 7 5 3 10 8 6 4... Truncated |
Test 11
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 53 52 21 76 25 142 5 4 83 176 ... |
correct output |
---|
YES 15194 334 336 338 340 342 344 346 34... |
user output |
---|
YES 15174 67 65 63 61 59 57 55 53 51 49 ... Truncated |
Test 12
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 51 44 147 172 1 28 27 82 233 1... |
correct output |
---|
YES 15565 366 368 370 372 374 376 378 38... |
user output |
---|
YES 15543 3 1 108 106 104 102 100 98 96 ... Truncated |
Test 13
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 75 46 179 62 221 14 67 154 89 ... |
correct output |
---|
YES 15920 454 456 458 460 462 464 466 46... |
user output |
---|
YES 15902 75 73 71 69 67 65 63 61 59 57 ... Truncated |
Test 14
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 161 54 285 12 71 142 111 94 97... |
correct output |
---|
YES 15931 408 410 412 414 416 418 420 42... |
user output |
---|
YES 15907 275 273 271 269 267 265 263 26... Truncated |
Test 15
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 122 260 455 113 315 276 433 43... |
correct output |
---|
NO |
user output |
---|
NO |
Test 16
Group: 2
Verdict: ACCEPTED
input |
---|
500 3 499 500 497 498 495 496 493 49... |
correct output |
---|
YES 62264 2 4 6 8 10 12 14 16 18 20 22 2... |
user output |
---|
YES 62250 497 495 493 491 489 487 485 48... Truncated |
Test 17
Group: 3
Verdict: ACCEPTED
input |
---|
5 4 1 2 3 4 5 |
correct output |
---|
YES 0 |
user output |
---|
YES 0 |
Test 18
Group: 3
Verdict: RUNTIME ERROR
input |
---|
5 4 5 1 2 3 4 |
correct output |
---|
YES 4 1 2 1 2 |
user output |
---|
(empty) |
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
input |
---|
500 4 58 14 107 124 4 113 24 290 56 ... |
correct output |
---|
YES 15698 389 392 395 398 401 404 407 41... |
user output |
---|
YES 14902 24 21 18 15 12 9 6 3 2 1 17 14... Truncated |
Test 20
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 113 187 278 242 23 67 48 298 3... |
correct output |
---|
YES 15004 480 481 480 482 485 488 491 49... |
user output |
---|
YES 14077 265 262 259 256 253 250 247 24... Truncated |
Test 21
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 5 233 199 35 213 354 11 134 30... |
correct output |
---|
YES 16770 458 461 464 467 470 473 476 47... |
user output |
---|
YES 15733 227 224 221 218 215 212 209 20... Truncated |
Test 22
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 169 47 21 137 57 138 360 147 4... |
correct output |
---|
YES 15889 497 371 372 371 373 376 379 38... |
user output |
---|
YES 14948 58 55 52 49 46 43 40 37 34 31 ... Truncated |
Test 23
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 493 409 291 313 156 443 496 40... |
correct output |
---|
YES 22886 480 481 480 482 485 488 491 49... |
user output |
---|
YES 22039 338 335 332 329 326 323 320 31... Truncated |
Test 24
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 137 99 100 226 326 298 140 340... |
correct output |
---|
NO |
user output |
---|
NO |
Test 25
Group: 3
Verdict: ACCEPTED
input |
---|
500 4 500 499 498 497 496 495 494 49... |
correct output |
---|
YES 41458 1 2 1 2 5 8 11 14 17 20 23 26 ... |
user output |
---|
YES 42130 497 494 491 488 485 482 479 47... Truncated |
Test 26
Group: 4
Verdict: ACCEPTED
input |
---|
5 5 1 2 3 4 5 |
correct output |
---|
YES 0 |
user output |
---|
YES 0 |
Test 27
Group: 4
Verdict: RUNTIME ERROR
input |
---|
5 5 5 4 3 2 1 |
correct output |
---|
YES 1 1 |
user output |
---|
(empty) |
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
input |
---|
500 5 145 26 285 154 147 314 141 40 ... |
correct output |
---|
YES 13786 216 220 224 228 232 236 240 24... |
user output |
---|
(empty) |
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
input |
---|
500 5 137 22 399 292 249 6 51 224 42... |
correct output |
---|
YES 13465 456 460 464 468 472 476 480 48... |
user output |
---|
(empty) |
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
input |
---|
500 5 153 52 85 100 329 60 433 468 4... |
correct output |
---|
YES 13642 377 378 377 380 384 388 392 39... |
user output |
---|
(empty) |
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
input |
---|
500 5 267 326 95 108 189 32 291 366 ... |
correct output |
---|
YES 14639 213 214 213 216 220 224 228 23... |
user output |
---|
(empty) |
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
input |
---|
500 5 15 450 272 80 321 101 247 438 ... |
correct output |
---|
NO |
user output |
---|
NO |
Test 33
Group: 4
Verdict: ACCEPTED
input |
---|
499 5 497 498 499 496 495 494 493 49... |
correct output |
---|
YES 30886 3 7 11 15 19 23 27 31 35 39 43... |
user output |
---|
YES 31614 495 491 487 483 479 475 471 46... Truncated |
Test 34
Group: 4
Verdict: RUNTIME ERROR
input |
---|
500 5 499 500 497 498 495 496 493 49... |
correct output |
---|
YES 30919 1 4 8 12 16 20 24 28 32 36 40 ... |
user output |
---|
(empty) |
Error:
thread 'main' panicked at 'index out of bounds: the len is 6 but the index is 6', input/co...