— Dark mode

Putka Open 2020 – 4/5

Ruudukko

  • Start: 2020-11-06 18:00:00
  • End: 2020-11-08 23:00:00
CSES - Putka Open 2020 – 4/5 - Results
Submission details
Task:Ruudukko
Sender:Hennkka
Submission time:2020-11-07 21:42:56 +0200
Language:Rust
Status:READY
Result:5
Feedback
groupverdictscore
#1ACCEPTED5
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 5details
#20.01 s2, 5details
#30.01 s3, 5details
#40.01 s4, 5details
#50.01 s5details
#60.01 s5details
#70.01 s2, 5details
#80.01 s2, 5details
#90.01 s3, 5details
#100.01 s3, 5details
#110.01 s3, 5details
#120.01 s3, 5details
#130.01 s4, 5details
#140.01 s5details
#150.01 s3, 5details
#160.01 s5details

Compiler report

warning: unused import: `rand::prelude::*`
 --> input/code.rs:1:5
  |
1 | use rand::prelude::*;
  |     ^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `std::collections::BTreeMap`
 --> input/code.rs:2:5
  |
2 | use std::collections::BTreeMap;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^

warning: value assigned to `y` is never read
  --> input/code.rs:96:13
   |
96 |             y += 1;
   |             ^
   |
   = note: `#[warn(unused_assignments)]` on by default
   = help: maybe it is overwritten before being read?

warning: value assigned to `y` is never read
  --> input/code.rs:99:13
   |
99 |             y -= 1;
   |             ^
   |
   = help: maybe it is overwritten before being read?

Code

use rand::prelude::*;
use std::collections::BTreeMap;
use std::io::BufRead;

fn flip_y(path: String) -> String {
    path.chars()
        .map(|c| match c {
            'U' => 'D',
            'D' => 'U',
            c => c,
        })
        .collect()
}

fn flip_x(path: String) -> String {
    path.chars()
        .map(|c| match c {
            'R' => 'L',
            'L' => 'R',
            c => c,
        })
        .collect()
}

fn solve(h: usize, w: usize, y1: usize, x1: usize, y2: usize, x2: usize) -> Option<String> {
    if y2 < y1 {
        return solve(h, w, h + 1 - y1, x1, h + 1 - y2, x2).map(flip_y);
    }
    if x2 < x1 {
        return solve(h, w, y1, w + 1 - x1, y2, w + 1 - x2).map(flip_x);
    }

    if h == 1 {
        if x1 == 1 && x2 == w {
            Some("R".repeat(w - 1))
        } else {
            None
        }
    } else if h == 2 {
        if y1 == 2 {
            return solve(h, w, h + 1 - y1, x1, h + 1 - y2, x2).map(flip_y);
        }
        assert!(y1 == 1);

        if x1 == x2 {
            if x1 == 1 {
                // Go right, down, and then back left
                return Some(format!("{}D{}", "R".repeat(w - 1), "L".repeat(w - 1)));
            } else if x1 == w {
                // Go left, down, and then back right
                return Some(format!("{}D{}", "L".repeat(w - 1), "R".repeat(w - 1)));
            } else {
                return None;
            }
        }
        assert!(x1 < x2);
        // Go first left until the left wall, then back, then fill the space in between, right and back left
        let mut res = "".to_string();
        let mut x = x1;
        while x > 1 {
            res.push('L');
            x -= 1;
        }
        res.push('D');
        while x <= x1 {
            res.push('R');
            x += 1;
        }
        // Now we need to go up and down until we reach x2, hopefully on the other side
        let mut y = 2;
        while x + 1 < x2 {
            res.push('R');
            x += 1;
            if y == 1 {
                res.push('D');
                y += 1;
            } else {
                res.push('U');
                y -= 1;
            }
        }
        // In next step we share x coordinate with x2
        res.push('R');
        x += 1;
        if y == y2 {
            // We hit end, this a failure because the other cell in this column is unvisited
            return None;
        }
        // Now we just walk right until wall, go up or down, and then walk back to x2
        while x < w {
            res.push('R');
            x += 1;
        }
        if y == 1 {
            res.push('D');
            y += 1;
        } else {
            res.push('U');
            y -= 1;
        }
        while x > x2 {
            res.push('L');
            x -= 1;
        }

        assert!(res.len() == h * w - 1);
        Some(res)
    } else {
        unimplemented!()
    }
}

fn main() {
    let stdin = std::io::stdin();
    let stdin = stdin.lock();
    let mut lines = stdin.lines();

    let t: usize = lines.next().unwrap().unwrap().parse().unwrap();
    for _ in 0..t {
        let input: Vec<usize> = lines
            .next()
            .unwrap()
            .unwrap()
            .split_whitespace()
            .map(|v| v.parse().unwrap())
            .collect();
        if let Some(res) = solve(input[0], input[1], input[2], input[3], input[4], input[5]) {
            println!("YES");
            println!("{}", res);
        } else {
            println!("NO");
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
}

Test details

Test 1

Group: 1, 5

Verdict: ACCEPTED

input
100
1 45 1 45 1 1
1 18 1 1 1 10
1 47 1 17 1 30
1 33 1 28 1 20
...
view save

correct output
YES
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...
view save

user output
YES
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLL...
Truncated

Test 2

Group: 2, 5

Verdict:

input
100
2 43 1 33 1 21
2 2 1 1 2 2
2 32 1 1 2 8
2 14 1 12 1 14
...
view save

correct output
NO
NO
NO
NO
YES
...
view save

user output
(empty)

Error:
thread 'main' panicked at 'assertion failed: res.len() == h * w - 1', input/code.rs:106:9...

Test 3

Group: 3, 5

Verdict:

input
100
3 4 2 1 2 4
3 38 2 24 1 22
3 29 2 23 2 3
3 8 3 1 1 2
...
view save

correct output
NO
NO
NO
YES
RRRRRRRUULDLULDLULDLLUR
...
view save

user output
(empty)

Error:
thread 'main' panicked at 'not implemented', input/code.rs:109:9
note: run with `RUST_BACK...

Test 4

Group: 4, 5

Verdict:

input
100
4 25 2 19 1 5
4 13 3 10 4 12
4 7 3 1 4 2
4 23 1 19 2 5
...
view save

correct output
YES
DDRRRRRRULLLLLURRRRRULLLLLLLDD...
view save

user output
(empty)

Error:
thread 'main' panicked at 'not implemented', input/code.rs:109:9
note: run with `RUST_BACK...

Test 5

Group: 5

Verdict:

input
100
16 8 13 1 14 8
41 21 19 11 32 12
46 17 13 7 6 11
8 41 4 32 4 12
...
view save

correct output
NO
YES
LURULURULURULURULURRDDDDDDDDDR...
view save

user output
(empty)

Error:
thread 'main' panicked at 'not implemented', input/code.rs:109:9
note: run with `RUST_BACK...

Test 6

Group: 5

Verdict:

input
100
31 38 18 35 31 37
35 48 7 13 21 21
46 21 25 2 4 19
35 2 13 2 35 1
...
view save

correct output
YES
LLLLLLLLLLLLDRRRRRRRRRRRRDLLLL...
view save

user output
(empty)

Error:
thread 'main' panicked at 'not implemented', input/code.rs:109:9
note: run with `RUST_BACK...

Test 7

Group: 2, 5

Verdict:

input
100
2 4 1 3 1 4
2 4 2 2 1 1
2 4 2 3 1 2
2 4 2 3 1 4
...
view save

correct output
YES
LLDRRRU
NO
NO
NO
...
view save

user output
(empty)

Error:
thread 'main' panicked at 'assertion failed: res.len() == h * w - 1', input/code.rs:106:9...

Test 8

Group: 2, 5

Verdict:

input
100
2 5 1 2 2 4
2 5 1 2 1 1
2 5 2 1 1 2
2 5 1 1 1 5
...
view save

correct output
YES
LDRRURRDL
YES
RRRDLLLLU
NO
...
view save

user output
NO
view save

Error:
thread 'main' panicked at 'assertion failed: res.len() == h * w - 1', input/code.rs:106:9...

Test 9

Group: 3, 5

Verdict:

input
100
3 4 1 1 2 3
3 4 2 4 3 2
3 4 2 1 3 1
3 4 1 4 3 4
...
view save

correct output
YES
DDRRRUULLDR
NO
YES
URRRDDLULDL
...
view save

user output
(empty)

Error:
thread 'main' panicked at 'not implemented', input/code.rs:109:9
note: run with `RUST_BACK...

Test 10

Group: 3, 5

Verdict:

input
100
3 5 3 4 3 2
3 5 3 5 2 3
3 5 3 1 2 2
3 5 3 1 3 2
...
view save

correct output
NO
NO
YES
UURRRRDDLULDLU
NO
...
view save

user output
(empty)

Error:
thread 'main' panicked at 'not implemented', input/code.rs:109:9
note: run with `RUST_BACK...

Test 11

Group: 3, 5

Verdict:

input
100
3 8 2 8 1 2
3 8 2 4 1 7
3 8 3 4 2 7
3 8 2 5 3 1
...
view save

correct output
NO
NO
NO
YES
LLLDRRRRURDRUULLLLLLLDD
...
view save

user output
(empty)

Error:
thread 'main' panicked at 'not implemented', input/code.rs:109:9
note: run with `RUST_BACK...

Test 12

Group: 3, 5

Verdict:

input
100
3 9 1 3 2 9
3 9 1 6 1 5
3 9 3 6 2 8
3 9 3 2 3 4
...
view save

correct output
NO
NO
NO
NO
NO
...
view save

user output
(empty)

Error:
thread 'main' panicked at 'not implemented', input/code.rs:109:9
note: run with `RUST_BACK...

Test 13

Group: 4, 5

Verdict:

input
100
4 4 2 2 1 4
4 4 4 1 2 2
4 4 2 1 4 3
4 4 3 1 3 3
...
view save

correct output
YES
DDLUUURRDDDRUUU
YES
UUURRRDLDRDLLUU
NO
...
view save

user output
(empty)

Error:
thread 'main' panicked at 'not implemented', input/code.rs:109:9
note: run with `RUST_BACK...

Test 14

Group: 5

Verdict:

input
100
12 27 6 22 1 8
6 25 3 2 4 4
6 16 4 6 5 2
36 33 8 6 1 6
...
view save

correct output
YES
DLDDDDDRUUUURDDDDRUURDDRRULURU...
view save

user output
(empty)

Error:
thread 'main' panicked at 'not implemented', input/code.rs:109:9
note: run with `RUST_BACK...

Test 15

Group: 3, 5

Verdict:

input
100
3 12 3 5 1 4
3 20 3 19 2 19
3 34 3 9 2 9
3 38 2 15 3 15
...
view save

correct output
YES
RRRRRRRUULDLULDLULDLULDLDLULDL...
view save

user output
(empty)

Error:
thread 'main' panicked at 'not implemented', input/code.rs:109:9
note: run with `RUST_BACK...

Test 16

Group: 5

Verdict:

input
100
50 50 29 1 16 21
50 50 37 5 23 48
50 50 32 22 45 24
50 50 6 28 12 37
...
view save

correct output
YES
DDDDDDDDDDDDDDDDDDDDDRUUUUUUUU...
view save

user output
(empty)

Error:
thread 'main' panicked at 'not implemented', input/code.rs:109:9
note: run with `RUST_BACK...

Tasks

A Neliöt-B Peli-C Tekijät-D Ruudukko-

Submissions (Hennkka)

2020-11-08 21:52:42 722020-11-08 17:59:15 442020-11-08 14:04:10 52020-11-08 14:00:09 52020-11-08 13:58:32 02020-11-08 13:16:35 172020-11-08 13:16:05 172020-11-08 11:43:21 172020-11-08 00:53:51 172020-11-08 00:39:59 172020-11-07 21:55:06 172020-11-07 21:42:56 52020-11-07 21:42:12 02020-11-07 18:52:37 52020-11-07 18:50:11 02020-11-07 00:01:04 5