— Dark mode

Datatähti 2024 alku

Käännöt

  • Start: 2023-10-30 00:00:00
  • End: 2023-11-13 00:00:00
Submission details
Task:Käännöt
Sender:ToukoP
Submission time:2023-11-07 15:13:11 +0200
Language:Rust
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
Test results
testverdicttimegroup
#10.01 s1details
#20.02 s1details
#30.02 s1details
#40.02 s1details
#50.02 s1details
#60.01 s2details
#7ACCEPTED0.01 s2details
#80.02 s2details
#90.02 s2details
#100.02 s2details
#110.02 s2details
#120.02 s2details
#130.02 s2details
#140.02 s2details
#150.02 s2details
#160.02 s2details
#170.01 s3details
#180.01 s3details
#190.01 s3details
#200.01 s3details
#210.01 s3details
#220.01 s3details
#230.01 s3details
#240.01 s3details
#250.01 s3details
#260.01 s4details
#27ACCEPTED0.01 s4details
#280.01 s4details
#290.01 s4details
#300.01 s4details
#310.01 s4details
#32ACCEPTED0.01 s4details
#330.01 s4details
#340.01 s4details

Code

use std::io::*;

const BUFFER_SIZE: usize = 600;

fn solve(
    result: &mut [i32],
    res_i: &mut usize,
    list: &mut [i32],
    start: i32,
    n: i32,
    k: i32,
) -> bool {
    let mut reverse = |list: &mut [i32], p: i32| {
        #[cfg(feature = "print")]
        {
            println!("Reverse index: {p} k: {k}");
            println!("{:?}", list[..((start + n) as usize)].to_vec());
        }

        if p + k > start + n {
            panic!("Out of bounds, index too large");
        }

        *res_i += 1;
        result[*res_i] = p;
        list[(p as usize)..((p + k) as usize)].reverse();

        #[cfg(feature = "print")]
        {
            println!("{:?}", list[..((start + n) as usize)].to_vec());
        }
    };

    let get = |list: &[i32], i: i32| list[i as usize];

    let mut index = start;
    let mut is_found = false;
    for i in start..(start + n) {
        if get(list, i) == start + 1 {
            index = i;
            is_found = true;
            break;
        }
    }

    #[cfg(feature = "print")]
    println!(
        "index: {}  target number: {}  start: {}",
        index,
        start + 1,
        start
    );

    if !is_found {
        #[cfg(feature = "print")]
        println!(
            "index not found\ntarget number: {}  start: {}",
            start + 1,
            start
        );
        return true;
    }

    if n < 1 {
        #[cfg(feature = "print")]
        println!("DONE");
        return true;
    } else if n <= k && k > 3 {
        if k == 4 {
            #[cfg(feature = "print")]
            println!("End reached, let's hope for the best (start: {start})\n");

            #[cfg(feature = "print")]
            println!("{:?}", list[..((start + n) as usize)].to_vec());
            let sum_of_last_pair = get(list, start + n - 1) + get(list, start + n - 2);
            if sum_of_last_pair != (start + n) * 2 - 1 && sum_of_last_pair != (start + n) * 2 - 5 {
                #[cfg(feature = "print")]
                println!("Pairs not matched");
                if (get(list, start + n - 2) - get(list, start + n - 3)).abs() == 1 {
                    #[cfg(feature = "print")]
                    println!("Middlematch ");
                    reverse(list, start - 2);
                    reverse(list, start - 1);

                    reverse(list, start - 1);
                    reverse(list, start);
                    reverse(list, start - 1);
                    reverse(list, start);

                    reverse(list, start - 2);
                    reverse(list, start - 1);
                    reverse(list, start - 2);
                    reverse(list, start - 1);
                } else {
                    #[cfg(feature = "print")]
                    println!("crossmatch ??");
                    reverse(list, start - 1);
                    reverse(list, start);
                    reverse(list, start - 2);

                    reverse(list, start);
                    reverse(list, start - 1);

                    reverse(list, start - 2);
                    reverse(list, start - 1);
                    reverse(list, start - 2);
                }
            }

            if (get(list, start + n - 2) - get(list, start + n - 1)) != 1 {
                #[cfg(feature = "print")]
                println!("Ascending order on last pair");
                if get(list, start + n - 1) == start + n {
                    #[cfg(feature = "print")]
                    println!("Last pair is correct + order = correct");
                } else {
                    #[cfg(feature = "print")]
                    println!("Swap pairs 1");
                    reverse(list, start - 2);
                    reverse(list, start);
                    reverse(list, start - 2);

                    reverse(list, start - 1);
                    reverse(list, start - 2);
                    reverse(list, start - 1);
                    reverse(list, start - 2);

                    reverse(list, start);
                    reverse(list, start - 1);
                    reverse(list, start);
                    reverse(list, start - 1);
                }
            } else {
                if get(list, start + n - 1) == start + n - 1 {
                    #[cfg(feature = "print")]
                    println!("Swap pairs + Reverse");
                    reverse(list, start - 2);
                    reverse(list, start);
                    reverse(list, start - 2);

                    reverse(list, start - 1);
                    reverse(list, start - 2);
                    reverse(list, start - 1);
                    reverse(list, start - 2);

                    reverse(list, start);
                    reverse(list, start - 1);
                    reverse(list, start);
                    reverse(list, start - 1);

                    reverse(list, start);
                } else {
                    #[cfg(feature = "print")]
                    println!("Reversed");
                    reverse(list, start);
                }
            }
        } else {
            // Handle k = 5 later
        }

        #[cfg(feature = "print")]
        println!("DONE FRFR");
        return true;
    }

    if index == start {
        #[cfg(feature = "print")]
        println!("Already good\n");
        return solve(result, res_i, list, start + 1, n - 1, k);
    }

    if k % 2 == 1 && index % 2 == get(list, index) % 2 {
        return false;
    }

    let mut pos = index;
    while pos != start {
        let i = (pos - k).max(start).min(start + n - k);
        #[cfg(feature = "print")]
        println!(
            "i: {i}, pos: {pos}, k: {k}, start: {start}, start + n - k - 1: {}",
            start + n - k - 1
        );
        reverse(list, i + 1);
        if start + k > i && k > 3 {
            reverse(list, i);
        }

        for i in i..(start + n) {
            if get(list, i) == start + 1 {
                pos = i;
                break;
            }
        }

        #[cfg(feature = "print")]
        println!("");
    }

    #[cfg(feature = "print")]
    {
        println!("Done");
        println!("{:?}\n", list[..((start + n) as usize)].to_vec());
    }

    return solve(result, res_i, list, start + 1, n - 1, k);
}

fn main() -> Result<()> {
    for _ in 0..1 {
        let mut input = String::new();
        stdin().read_line(&mut input)?;

        let mut split = input.split(" ");
        let n: i32 = split.next().unwrap().trim().parse().unwrap();
        let k: i32 = split.next().unwrap().trim().parse().unwrap();

        let mut list_input = String::new();
        stdin().read_line(&mut list_input)?;
        let vector = list_input
            .split(" ")
            .map(|s| s.trim().parse().unwrap())
            .collect::<Vec<i32>>();

        let mut list = [0; BUFFER_SIZE];
        list[(0 as usize)..(n as usize)].clone_from_slice(&vector);

        #[cfg(feature = "print")]
        println!("{:?}\n", list[..(n as usize)].to_vec());

        let mut result = [0; 1_000_000];
        let mut res_i = 0;
        if solve(&mut result, &mut res_i, &mut list, 0, n, k) {
            #[cfg(feature = "check")]
            list[..(n as usize)].iter().enumerate().for_each(|(i, v)| {
                if *v != i as i32 + 1 {
                    println!("{:?}\n", list[..(n as usize)].to_vec());
                    panic!("Wrong answer");
                }
            });
            println!(
                "YES\n{}\n{}",
                res_i + 1,
                result[..(res_i + 1)]
                    .iter()
                    .map(|n| (n + 1).to_string())
                    .collect::<Vec<_>>()
                    .join(" ")
            );
        } else {
            println!("NO")
        }
    }

    Ok(())
}

Test details

Test 1

Group: 1

Verdict:

input
5 2
1 2 3 4 5
view save

correct output
YES
0
view save

user output
YES
1
1
view save

Test 2

Group: 1

Verdict:

input
5 2
2 1 3 4 5
view save

correct output
YES
1
1
view save

user output
(empty)

Error:
thread 'main' panicked at 'index out of bounds: the len is 1000000 but the index is 100000...

Test 3

Group: 1

Verdict:

input
20 2
6 20 18 2 16 13 19 17 8 14 11 ...
view save

correct output
YES
366
2 3 4 5 6 7 8 9 10 11 12 13 14...
view save

user output
(empty)

Error:
thread 'main' panicked at 'index out of bounds: the len is 1000000 but the index is 100000...

Test 4

Group: 1

Verdict:

input
100 2
100 92 62 88 12 7 43 31 19 72 ...
view save

correct output
YES
2876
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

Error:
thread 'main' panicked at 'index out of bounds: the len is 1000000 but the index is 100000...

Test 5

Group: 1

Verdict:

input
100 2
100 99 98 97 96 95 94 93 92 91...
view save

correct output
YES
5248
1 2 3 4 5 6 7 8 9 10 11 12 13 ...
view save

user output
(empty)

Error:
thread 'main' panicked at 'index out of bounds: the len is 1000000 but the index is 100000...

Test 6

Group: 2

Verdict:

input
5 3
1 2 3 4 5
view save

correct output
YES
0
view save

user output
YES
1
1
view save

Test 7

Group: 2

Verdict: ACCEPTED

input
5 3
3 5 4 1 2
view save

correct output
NO
view save

user output
NO
view save

Test 8

Group: 2

Verdict:

input
5 3
5 2 1 4 3
view save

correct output
YES
8
1 2 1 3 1 2 3 1
view save

user output
(empty)

Error:
thread 'main' panicked at 'index out of bounds: the len is 1000000 but the index is 100000...

Test 9

Group: 2

Verdict:

input
20 3
19 14 1 18 3 4 11 20 13 6 17 8...
view save

correct output
YES
52
8 10 12 14 16 18 1 3 5 7 9 11 ...
view save

user output
(empty)

Error:
thread 'main' panicked at 'index out of bounds: the len is 1000000 but the index is 100000...

Test 10

Group: 2

Verdict:

input
20 3
9 6 13 18 5 10 3 2 7 20 1 4 19...
view save

correct output
YES
50
10 12 14 16 18 13 15 17 4 6 8 ...
view save

user output
(empty)

Error:
thread 'main' panicked at 'index out of bounds: the len is 1000000 but the index is 100000...

Test 11

Group: 2

Verdict:

input
500 3
53 52 21 76 25 142 5 4 83 176 ...
view save

correct output
YES
15194
334 336 338 340 342 344 346 34...
view save

user output
(empty)

Error:
thread 'main' panicked at 'index out of bounds: the len is 1000000 but the index is 100000...

Test 12

Group: 2

Verdict:

input
500 3
51 44 147 172 1 28 27 82 233 1...
view save

correct output
YES
15565
366 368 370 372 374 376 378 38...
view save

user output
(empty)

Error:
thread 'main' panicked at 'index out of bounds: the len is 1000000 but the index is 100000...

Test 13

Group: 2

Verdict:

input
500 3
75 46 179 62 221 14 67 154 89 ...
view save

correct output
YES
15920
454 456 458 460 462 464 466 46...
view save

user output
(empty)

Error:
thread 'main' panicked at 'index out of bounds: the len is 1000000 but the index is 100000...

Test 14

Group: 2

Verdict:

input
500 3
161 54 285 12 71 142 111 94 97...
view save

correct output
YES
15931
408 410 412 414 416 418 420 42...
view save

user output
(empty)

Error:
thread 'main' panicked at 'index out of bounds: the len is 1000000 but the index is 100000...

Test 15

Group: 2

Verdict:

input
500 3
122 260 455 113 315 276 433 43...
view save

correct output
NO
view save

user output
(empty)

Error:
thread 'main' panicked at 'index out of bounds: the len is 1000000 but the index is 100000...

Test 16

Group: 2

Verdict:

input
500 3
499 500 497 498 495 496 493 49...
view save

correct output
YES
62264
2 4 6 8 10 12 14 16 18 20 22 2...
view save

user output
(empty)

Error:
thread 'main' panicked at 'index out of bounds: the len is 1000000 but the index is 100000...

Test 17

Group: 3

Verdict:

input
5 4
1 2 3 4 5
view save

correct output
YES
0
view save

user output
YES
1
1
view save

Test 18

Group: 3

Verdict:

input
5 4
5 1 2 3 4
view save

correct output
YES
4
1 2 1 2
view save

user output
YES
7
1 2 1 2 1 2 1
view save

Test 19

Group: 3

Verdict:

input
500 4
58 14 107 124 4 113 24 290 56 ...
view save

correct output
YES
15698
389 392 395 398 401 404 407 41...
view save

user output
YES
17742
1 24 21 18 15 12 9 6 3 2 2 1 2...
Truncated

Test 20

Group: 3

Verdict:

input
500 4
113 187 278 242 23 67 48 298 3...
view save

correct output
YES
15004
480 481 480 482 485 488 491 49...
view save

user output
YES
16758
1 265 262 259 256 253 250 247 ...
Truncated

Test 21

Group: 3

Verdict:

input
500 4
5 233 199 35 213 354 11 134 30...
view save

correct output
YES
16770
458 461 464 467 470 473 476 47...
view save

user output
YES
18611
1 227 224 221 218 215 212 209 ...
Truncated

Test 22

Group: 3

Verdict:

input
500 4
169 47 21 137 57 138 360 147 4...
view save

correct output
YES
15889
497 371 372 371 373 376 379 38...
view save

user output
YES
17777
1 58 55 52 49 46 43 40 37 34 3...
Truncated

Test 23

Group: 3

Verdict:

input
500 4
493 409 291 313 156 443 496 40...
view save

correct output
YES
22886
480 481 480 482 485 488 491 49...
view save

user output
YES
24893
1 338 335 332 329 326 323 320 ...
Truncated

Test 24

Group: 3

Verdict:

input
500 4
137 99 100 226 326 298 140 340...
view save

correct output
NO
view save

user output
YES
24768
1 17 14 11 8 5 4 3 2 2 1 2 1 2...
Truncated

Test 25

Group: 3

Verdict:

input
500 4
500 499 498 497 496 495 494 49...
view save

correct output
YES
41458
1 2 1 2 5 8 11 14 17 20 23 26 ...
view save

user output
YES
45116
1 497 494 491 488 485 482 479 ...
Truncated

Test 26

Group: 4

Verdict:

input
5 5
1 2 3 4 5
view save

correct output
YES
0
view save

user output
YES
1
1
view save

Test 27

Group: 4

Verdict: ACCEPTED

input
5 5
5 4 3 2 1
view save

correct output
YES
1
1
view save

user output
YES
1
1
view save

Test 28

Group: 4

Verdict:

input
500 5
145 26 285 154 147 314 141 40 ...
view save

correct output
YES
13786
216 220 224 228 232 236 240 24...
view save

user output
YES
15514
1 81 77 73 69 65 61 57 53 49 4...
Truncated

Test 29

Group: 4

Verdict:

input
500 5
137 22 399 292 249 6 51 224 42...
view save

correct output
YES
13465
456 460 464 468 472 476 480 48...
view save

user output
YES
15297
1 467 463 459 455 451 447 443 ...
Truncated

Test 30

Group: 4

Verdict:

input
500 5
153 52 85 100 329 60 433 468 4...
view save

correct output
YES
13642
377 378 377 380 384 388 392 39...
view save

user output
YES
15327
1 203 199 195 191 187 183 179 ...
Truncated

Test 31

Group: 4

Verdict:

input
500 5
267 326 95 108 189 32 291 366 ...
view save

correct output
YES
14639
213 214 213 216 220 224 228 23...
view save

user output
YES
16210
1 361 357 353 349 345 341 337 ...
Truncated

Test 32

Group: 4

Verdict: ACCEPTED

input
500 5
15 450 272 80 321 101 247 438 ...
view save

correct output
NO
view save

user output
NO
view save

Test 33

Group: 4

Verdict:

input
499 5
497 498 499 496 495 494 493 49...
view save

correct output
YES
30886
3 7 11 15 19 23 27 31 35 39 43...
view save

user output
YES
33098
1 495 491 487 483 479 475 471 ...
Truncated

Test 34

Group: 4

Verdict:

input
500 5
499 500 497 498 495 496 493 49...
view save

correct output
YES
30919
1 4 8 12 16 20 24 28 32 36 40 ...
view save

user output
YES
33719
1 495 491 487 483 479 475 471 ...
Truncated

Tasks

A Lumimyrsky-B Monistus-C Laskettelukeskus-D Uolevin kalansaalis-E Käännöt-F Säähavainnot-

Submissions (ToukoP)

2023-11-07 19:03:34 1002023-11-07 19:02:36 02023-11-07 19:02:05 02023-11-07 18:40:53 652023-11-07 18:30:51 652023-11-07 18:29:20 652023-11-07 18:18:07 652023-11-07 17:57:58 02023-11-07 17:55:28 652023-11-07 16:12:20 652023-11-07 16:11:13 02023-11-07 16:00:08 02023-11-07 15:59:52 02023-11-07 15:45:10 02023-11-07 15:13:11 02023-11-07 14:02:09 02023-11-07 14:00:44 02023-11-06 00:06:06 322023-11-06 00:02:10 02023-11-05 23:22:56 132023-11-05 23:20:23 02023-11-05 23:19:11 02023-11-05 23:03:11 0