— Dark mode

Datatähti 2026 alku

Hypyt

  • Start: 2025-10-27 00:00:00
  • End: 2025-11-10 00:00:00
Submission details
Task:Hypyt
Sender:vulpesomnia
Submission time:2025-11-04 13:48:20 +0200
Language:Rust (2021)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#10.00 s1, 2, 3, 4, 5details
#2ACCEPTED0.00 s1, 2, 3, 4, 5details
#30.00 s1, 2, 3, 4, 5details
#40.00 s1, 2, 3, 4, 5details
#50.00 s1, 2, 3, 4, 5details
#60.42 s2, 5details
#70.42 s2, 5details
#80.42 s2, 5details
#90.32 s3, 4, 5details
#100.32 s3, 4, 5details
#110.01 s3, 4, 5details
#120.40 s4, 5details
#130.39 s4, 5details
#140.05 s4, 5details
#150.42 s5details
#160.42 s5details
#170.42 s5details
#180.42 s5details
#190.42 s5details
#200.42 s5details
#210.42 s5details
#22ACCEPTED0.00 s1, 2, 3, 4, 5details
#23ACCEPTED0.00 s1, 2, 3, 4, 5details
#240.42 s5details
#25ACCEPTED0.32 s5details
#260.43 s5details
#270.43 s5details

Compiler report

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

warning: 1 warning emitted

Code

use std::collections::HashMap;
use std::collections::HashSet;
use std::io;

#[derive(Clone, PartialEq, Debug)]
enum Tile {
    SAFE,
    MONSTER,
}

fn main() {
    let mut input = String::new();
    io::stdin()
        .read_line(&mut input)
        .expect("failed to readline");
    let mut iter = input.trim().split_whitespace();
    let (height, width, query_count): (usize, usize, i32) = (
        iter.next().unwrap().parse().unwrap(),
        iter.next().unwrap().parse().unwrap(),
        iter.next().unwrap().parse().unwrap(),
    );

    // Get all indexes for each row. O(n^2)
    let mut map: Vec<Vec<Tile>> = vec![vec![Tile::MONSTER; width]; height];
    for h in 0..height {
        let mut line = String::new();
        io::stdin().read_line(&mut line).expect("failed");
        for (i, c) in line.chars().enumerate() {
            if c == '.' {
                map[h][i] = Tile::SAFE;
            }
        }
    }

    const INF: usize = 10_usize.pow(5);
    // row1, row2 -> length and (col to cols) # perhaps turn vec into set
    let mut answer_map: Vec<Vec<(usize, Vec<(HashSet<usize>, HashSet<usize>)>)>> =
        vec![vec![(INF, vec![(HashSet::new(), HashSet::new()); height]); height]; height];
    // Create graph from overlapping indexes. O(n^3)
    for r1 in 0..height {
        for r2 in 0..height {
            for i in 0..width {
                if map[r1][i] == Tile::SAFE {
                    if map[r1][i] == map[r2][i] {
                        if answer_map[r1][r2].0 == INF {
                            let length = if r1 == r2 { 0 } else { 1 };
                            answer_map[r1][r2].0 = length;
                            answer_map[r1][r2].1[r1].0.insert(i);
                            answer_map[r1][r2].1[r1].1.insert(i);
                        } else {
                            answer_map[r1][r2].1[r1].0.insert(i);
                            answer_map[r1][r2].1[r1].1.insert(i);
                        }
                    }
                }
            }
        }
    }

    //print_map(&answer_map);

    // Update matrix to final form. O(n^3)
    for ni in 0..height {
        for n1 in 0..height {
            for n2 in 0..height {
                // Make sure no overlapping nodes:
                if (ni != n1 && ni != n2) && n1 != n2 {
                    let sum = answer_map[n1][ni].0 + answer_map[ni][n2].0;
                    if answer_map[n1][n2].0 > sum {
                        answer_map[n1][n2].0 = sum;
                        answer_map[n1][n2].1 = Vec::new();
                        answer_map[n1][n2].1[ni].0 = answer_map[n1][ni].1[n1].0.clone();
                        answer_map[n1][n2].1[ni].1 = answer_map[ni][n2].1[ni].1.clone();
                    } else if answer_map[n1][n2].0 == sum {
                        answer_map[n1][n2].1[ni].0 = answer_map[n1][ni].1[n1].0.clone();
                        answer_map[n1][n2].1[ni].1 = answer_map[ni][n2].1[ni].1.clone();
                    }
                }
            }
        }
    }

    //print_map(&answer_map);

    for _ in 0..query_count {
        let mut query = String::new();
        io::stdin()
            .read_line(&mut query)
            .expect("failed to readline");
        let mut iter = query.trim().split_whitespace();
        let (y1, x1, y2, x2): (usize, usize, usize, usize) = (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        );
        if x1 == x2 && y1 == y2 {
            println!("{}", 0);
        } else if x1 == x2 || y1 == y2 {
            println!("{}", 1);
        } else {
            let ans = &answer_map[y1 - 1][y2 - 1];
            if ans.0 == 1 { // If not on same column, but distance is one, then the leaps are solved.
                println!("{}", 2);
            } else {
                let mut leaps = if ans.0 != INF { 2 * ans.0 - 1 } else { INF };
                //println!("leaps beginning: {}", leaps);
                if leaps == INF {
                    println!("{}", -1);
                } else {
                    let mut first_correct = false;
                    let mut second_correct = false;
                    let mut first_index = 0;
                    let mut second_index = 0;
                    let mut index = 0;
                    for path in &ans.1 {
                      if path.0.contains(&(x1 - 1)) {
                        first_correct = true;
                        first_index = index;
                      }
                      if path.1.contains(&(x2 - 1)) {
                        second_correct = true;
                        second_index = index;
                      }
                      index += 1
                    }
                    if !first_correct && !second_correct {
                        leaps += 2;
                    } else if first_correct && !second_correct {
                        leaps += 1;
                    } else if !first_correct && second_correct {
                        leaps += 1;
                    } else if first_index != second_index {
                        leaps += 1;
                    }

                    println!("{}", leaps);
                }
            }
        }
    }
}

/*fn print_map(map: &Vec<Vec<(usize, HashMap<usize, HashSet<usize>>)>>) {
  println!("Map for length of shortest path from row to row:");
  let size = map.len();
  for i in 0..size {
  let mut line = String::new();
  for j in 0..size {
  line.push_str(map[i][j].0.to_string().as_str());
  line.push_str(" ");
  }
  println!("{}", line);
  }

  println!("Map for how many columns from starting row to end row:");
  for i in 0..size {
  let mut line = String::new();
  for j in 0..size {
//let size2 = map[i][j].1.len();
line.push_str("( ");
line.push_str(format!("{:?}", map[i][j].1).as_str());
//line.push_str(" ");
line.push_str(" )");
}
println!("{}", line);
}

/*println!("Map for how many columns from starting to end row, but at the end:");
for i in 0..size {
let mut line = String::new();
for j in 0..size {
let size2 = map[i][j].1.len();
line.push_str("( ");
for c in 0..size2 {
line.push_str(map[i][j].1[c]1.to_string().as_str());
line.push_str(" ");
}
line.push_str(" )");
}
println!("{}", line);
}*/
}*/

Test details

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict:

input
4 6 5
.*.***
*...**
*****.
*..*.*
...
view save

correct output
1
0
3
3
-1
view save

user output
1
0
2
2
-1
view save

Feedback: Incorrect character on line 3 col 1: expected "3", got "2"

Test 2

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
10 10 10
..........
.....*....
........*.
*.*....*..
...
view save

correct output
1
2
1
2
2
...
view save

user output
1
2
1
2
2
...
view save

Test 3

Group: 1, 2, 3, 4, 5

Verdict:

input
10 10 10
*...***.**
*****.*...
**..**.**.
..**.**.*.
...
view save

correct output
1
2
2
1
2
...
view save

user output
(empty)

Error:
thread 'main' panicked at input/code.rs:72:45:
index out of bounds: the len is 0 but the index is 0
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 4

Group: 1, 2, 3, 4, 5

Verdict:

input
10 10 10
***.*.****
**********
*.********
.*.***.**.
...
view save

correct output
3
4
2
3
4
...
view save

user output
(empty)

Error:
thread 'main' panicked at input/code.rs:72:45:
index out of bounds: the len is 0 but the index is 0
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 5

Group: 1, 2, 3, 4, 5

Verdict:

input
10 10 1
.****.****
**.**..***
**********
*******..*
...
view save

correct output
7
view save

user output
(empty)

Error:
thread 'main' panicked at input/code.rs:72:45:
index out of bounds: the len is 0 but the index is 0
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 6

Group: 2, 5

Verdict:

input
250 250 250
.*...*.....*******..**...*.......
view save

correct output
2
3
3
2
2
...
view save

user output
(empty)

Test 7

Group: 2, 5

Verdict:

input
250 250 250
...*......**.**.*.*..**..*..**...
view save

correct output
2
2
2
2
3
...
view save

user output
(empty)

Test 8

Group: 2, 5

Verdict:

input
250 250 250
**..**..****.****.*.***.***..*...
view save

correct output
2
3
3
3
3
...
view save

user output
(empty)

Test 9

Group: 3, 4, 5

Verdict:

input
40 40 200000
...*.**.*..*.............*.*.....
view save

correct output
2
2
2
2
2
...
view save

user output
2
2
2
2
2
...
view save

Feedback: Incorrect character on line 32 col 1: expected "3", got "2"

Test 10

Group: 3, 4, 5

Verdict:

input
40 40 200000
**.**..*.*.*.******....****.*....
view save

correct output
2
1
3
2
2
...
view save

user output
2
1
2
2
2
...
view save

Feedback: Incorrect character on line 3 col 1: expected "3", got "2"

Test 11

Group: 3, 4, 5

Verdict:

input
40 40 200000
.*.*.**.*****.***.*.****.**.**...
view save

correct output
3
3
3
3
3
...
view save

user output
(empty)

Error:
thread 'main' panicked at input/code.rs:72:45:
index out of bounds: the len is 0 but the index is 0
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 12

Group: 4, 5

Verdict:

input
80 80 200000
*....**.***..****...*.....*......
view save

correct output
2
2
2
2
2
...
view save

user output
2
2
2
2
2
...
view save

Feedback: Incorrect character on line 30 col 1: expected "3", got "2"

Test 13

Group: 4, 5

Verdict:

input
80 80 200000
.***.*..*.***..*****....**...*...
view save

correct output
3
2
2
3
2
...
view save

user output
2
2
2
2
2
...
view save

Feedback: Incorrect character on line 1 col 1: expected "3", got "2"

Test 14

Group: 4, 5

Verdict:

input
80 80 200000
*******.*****.*..*..****...***...
view save

correct output
2
3
1
2
2
...
view save

user output
(empty)

Error:
thread 'main' panicked at input/code.rs:72:45:
index out of bounds: the len is 0 but the index is 0
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 15

Group: 5

Verdict:

input
250 250 200000
*....*..*..*..**..*.........**...
view save

correct output
3
2
2
2
2
...
view save

user output
(empty)

Test 16

Group: 5

Verdict:

input
250 250 200000
..*....*..*......*.**.*.*..***...
view save

correct output
2
2
2
2
2
...
view save

user output
(empty)

Test 17

Group: 5

Verdict:

input
250 250 200000
*..*.*****.*********.****.****...
view save

correct output
3
3
2
2
2
...
view save

user output
(empty)

Test 18

Group: 5

Verdict:

input
250 250 200000
*********.**********.******.**...
view save

correct output
3
3
3
3
3
...
view save

user output
(empty)

Test 19

Group: 5

Verdict:

input
250 250 200000
.*****************************...
view save

correct output
104
422
145
93
65
...
view save

user output
(empty)

Test 20

Group: 5

Verdict:

input
250 250 200000
..****************************...
view save

correct output
57
155
38
65
98
...
view save

user output
(empty)

Test 21

Group: 5

Verdict:

input
250 250 200000
.*****************************...
view save

correct output
498
498
498
498
498
...
view save

user output
(empty)

Test 22

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
10 1 10
*
*
.
*
...
view save

correct output
0
1
1
0
0
...
view save

user output
0
1
1
0
0
...
view save

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
1 10 10
........*.
1 7 1 10
1 4 1 7
1 5 1 1
...
view save

correct output
1
1
1
1
1
...
view save

user output
1
1
1
1
1
...
view save

Test 24

Group: 5

Verdict:

input
250 1 200000
*
.
*
.
...
view save

correct output
1
1
1
1
1
...
view save

user output
(empty)

Test 25

Group: 5

Verdict: ACCEPTED

input
1 250 200000
*.*.*...*.*.**.***..**.*.*..**...
view save

correct output
1
1
1
1
1
...
view save

user output
1
1
1
1
1
...
view save

Test 26

Group: 5

Verdict:

input
250 250 200000
.................................
view save

correct output
2
2
2
2
2
...
view save

user output
(empty)

Test 27

Group: 5

Verdict:

input
250 250 200000
******************************...
view save

correct output
0
0
0
0
0
...
view save

user output
(empty)

Tasks

A Palindromi-B Monikulmio-C Tulkki-D Maalaus-E Hypyt-F Lukujono-

Submissions (vulpesomnia)

2025-11-06 14:48:08 1002025-11-06 12:52:00 602025-11-06 12:45:33 02025-11-06 10:43:00 402025-11-06 09:22:58 602025-11-06 00:34:27 302025-11-06 00:16:44 402025-11-05 21:51:20 602025-11-05 21:49:59 402025-11-05 21:37:31 602025-11-05 21:34:28 602025-11-05 21:23:28 602025-11-05 21:18:50 602025-11-05 21:15:21 602025-11-05 12:50:35 602025-11-05 12:48:22 602025-11-05 12:35:13 602025-11-05 12:29:39 602025-11-05 12:11:04 602025-11-05 11:56:34 602025-11-05 10:48:21 602025-11-05 10:39:38 602025-11-05 10:30:14 2025-11-05 10:20:35 602025-11-05 09:56:47 402025-11-05 09:44:06 402025-11-05 09:33:01 102025-11-04 22:40:21 02025-11-04 16:58:48 2025-11-04 13:48:20 02025-11-04 11:14:58 402025-11-04 10:33:14 402025-11-04 10:27:08 102025-11-04 10:23:40 402025-11-04 10:21:35 402025-11-04 09:48:04 102025-11-03 23:50:28 02025-11-03 23:20:36 02025-10-31 01:59:53 02025-10-30 14:01:34 02025-10-30 12:55:39 02025-10-29 10:26:58 102025-10-29 10:26:35 0