— 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:asonnine
Submission time:2025-11-07 09:51:15 +0200
Language:Rust (2021)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3, 4, 5details
#20.00 s1, 2, 3, 4, 5details
#30.00 s1, 2, 3, 4, 5details
#4ACCEPTED0.00 s1, 2, 3, 4, 5details
#5ACCEPTED0.00 s1, 2, 3, 4, 5details
#6ACCEPTED0.08 s2, 5details
#7ACCEPTED0.08 s2, 5details
#8ACCEPTED0.04 s2, 5details
#9ACCEPTED0.56 s3, 4, 5details
#10ACCEPTED0.80 s3, 4, 5details
#11ACCEPTED0.96 s3, 4, 5details
#12ACCEPTED0.94 s4, 5details
#13--4, 5details
#14--4, 5details
#15--5details
#16--5details
#17--5details
#18--5details
#19--5details
#200.05 s5details
#21--5details
#22ACCEPTED0.00 s1, 2, 3, 4, 5details
#23ACCEPTED0.00 s1, 2, 3, 4, 5details
#240.32 s5details
#25ACCEPTED0.32 s5details
#260.33 s5details
#27ACCEPTED0.32 s5details

Code

use std::{io, usize, vec};

#[derive(Debug, Clone, PartialEq, Eq)]
struct Row {
    connections: Vec<bool>,
}

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let (n, m, q): (usize, usize, usize) = {
        let mut iter = input.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    };
    let mut map: Vec<Vec<bool>> = Vec::new();
    for _ in 0..n {
        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        map.push(input.trim().chars().map(|x| x == '.').collect());
    }

    let mut modifications = vec![false; n];
    let mut modification_targets: Vec<usize> = vec![0; n];

    for row in 0..n {
        if !modifications[row] {
            for rowi in 0..n {
                if map[row] == map[rowi] && row != rowi {
                    modifications[rowi] = true;
                    modification_targets[rowi] = row;
                }
            }
        }
    }

    let mut new_map: Vec<Vec<bool>> = Vec::new();
    for row in 0..n {
        if modifications[row] {
        } else {
            new_map.push(map[row].clone());
            modification_targets[row] = new_map.len() - 1;
        }
    }
    //dbg!(&modifications, &modification_targets);

    let n = new_map.len();
    let map = new_map;

    let mut rows: Vec<Row> = vec![
        Row {
            connections: Vec::new()
        };
        n
    ];

    for row in 0..n {
        let mut connections = vec![false; n];
        for column in 0..m {
            if map[row][column] {
                for rowi in 0..n {
                    if row != rowi && map[rowi][column] {
                        connections[rowi] = true;
                    }
                }
            }
        }
        rows[row].connections = connections;
        /*
                //dbg!(&connections);
                for rowi in 0..n {
                    if connections[rowi] {
                        rows[row].connections.push(rowi);
                    }
                }
        */
    }
    //dbg!(&rows[198]);

    let mut subsets: Vec<Option<usize>> = vec![None; n];

    for row in 0..n {
        for rowi in row + 1..n {
            if map[rowi]
                .iter()
                .enumerate()
                .all(|(i, cell)| (!cell) || map[row][i])
            {
                subsets[rowi] = Some(row);
            }
        }
    }

    let mut queries: Vec<((usize, usize), (usize, usize))> = Vec::new();
    for _ in 0..q {
        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        let (y1, x1, y2, x2): (usize, usize, usize, usize) = {
            let mut iter = input.split_whitespace();

            let mut y1 = iter.next().unwrap().parse::<usize>().unwrap() - 1;
            let x1 = iter.next().unwrap().parse::<usize>().unwrap() - 1;
            let mut y2 = iter.next().unwrap().parse::<usize>().unwrap() - 1;
            let x2 = iter.next().unwrap().parse::<usize>().unwrap() - 1;

            y1 = modification_targets[y1];
            y2 = modification_targets[y2];

            (y1, x1, y2, x2)
        };
        queries.push(((x1, y1), (x2, y2)));
    }

    let rows = rows;
    let queries = queries;

    for query in queries {
        println!("{}", process_query(&rows, &map, query, &subsets));
    }
}

fn process_query(
    map_rows: &Vec<Row>,
    map: &Vec<Vec<bool>>,
    query: ((usize, usize), (usize, usize)),
    subsets: &Vec<Option<usize>>,
) -> i32 {
    let mut steps = 1;
    let rows = map_rows.len();
    let mut used_rows = vec![false; rows];

    if query.0 == query.1 {
        return 0;
    } else if query.0.0 == query.1.0 || query.0.1 == query.1.1 {
        return 1;
    }

    let mut process_rows: Vec<usize> = Vec::new();
    let mut advantages = vec![false; rows];

    advantages[query.0.1] = true;

    for row in 0..rows {
        if map[row][query.0.0] {
            if subsets[row].is_none() {
                process_rows.push(row);
            }
            used_rows[row] = true;
        }
    }
    if used_rows[query.1.1] {
        return 2;
    }

    loop {
        //dbg!(&process_rows);
        if used_rows[query.1.1] {
            return steps + 1;
        }

        let mut can_continue = false;
        let mut new_process_rows: Vec<usize> = Vec::new();
        let mut new_advantages = vec![false; rows];
        let mut can_still_use = vec![false; rows];

        let mut lowest_score = -1;

        for row in 0..rows {
            if !used_rows[row] || can_still_use[row] {
                for rowi in &process_rows {
                    if map_rows[*rowi].connections[row] {
                        used_rows[row] = true;
                        if subsets[row].is_none() {
                            new_process_rows.push(row);
                            if advantages[*rowi] {
                                new_advantages[row] = true;
                            }
                        }
                        can_continue = true;

                        if row == query.1.1 {
                            //dbg!(row, rowi);
                            //dbg!(steps);
                            if advantages[*rowi] {
                                if lowest_score != -1 {
                                    if map[*rowi][query.1.0] {
                                        lowest_score = i32::min(lowest_score, steps + 1);
                                    } else {
                                        lowest_score = i32::min(lowest_score, steps + 2);
                                        can_still_use[row] = true;
                                    }
                                } else {
                                    // Sometimes goes to wrong branch??????
                                    if map[*rowi][query.1.0] {
                                        lowest_score = steps + 1;
                                    } else {
                                        lowest_score = steps + 2;
                                        can_still_use[row] = true;
                                    }
                                }
                            } else {
                                if lowest_score != -1 {
                                    if map[*rowi][query.1.0] {
                                        lowest_score = i32::min(lowest_score, steps + 2);
                                    } else {
                                        lowest_score = i32::min(lowest_score, steps + 3);
                                    }
                                } else {
                                    // Sometimes goes to wrong branch??????
                                    if map[*rowi][query.1.0] {
                                        lowest_score = steps + 2;
                                    } else {
                                        lowest_score = steps + 3; // 9946 branch
                                    }
                                }
                                can_still_use[row] = true;
                            }
                        }
                    }
                }
            }
        }
        /*
        for row in process_rows {
            for rowi in &map_rows[row].connections {
                // the issue
                if (!used_rows[*rowi]) || can_still_use[*rowi] {
                    used_rows[*rowi] = true;
                    if subsets[*rowi].is_none() {
                        new_process_rows.push(*rowi);
                        if advantages[row] {
                            new_advantages[*rowi] = true;
                        }
                    }
                    can_continue = true;

                    if *rowi == query.1.1 {
                        if advantages[row] {
                            if lowest_score != -1 {
                                if map[row][query.1.0] {
                                    lowest_score = i32::min(lowest_score, steps + 1);
                                } else {
                                    lowest_score = i32::min(lowest_score, steps + 2);
                                    can_still_use[*rowi] = true;
                                }
                            } else {
                                // Sometimes goes to wrong branch??????
                                if map[row][query.1.0] {
                                    lowest_score = steps + 1;
                                } else {
                                    lowest_score = steps + 2;
                                    can_still_use[*rowi] = true;
                                }
                            }
                        } else {
                            //dbg!(row, rowi);
                            if lowest_score != -1 {
                                if map[row][query.1.0] {
                                    lowest_score = i32::min(lowest_score, steps + 2);
                                } else {
                                    lowest_score = i32::min(lowest_score, steps + 3);
                                }
                            } else {
                                // Sometimes goes to wrong branch??????
                                if map[row][query.1.0] {
                                    lowest_score = steps + 2;
                                } else {
                                    lowest_score = steps + 3; // 9946 branch
                                }
                            }
                            can_still_use[*rowi] = true;
                        }
                    }
                }
            }
        }*/

        if lowest_score != -1 {
            return lowest_score;
        }

        if !can_continue {
            return -1;
        }

        process_rows = new_process_rows;
        advantages = new_advantages;

        steps += 2;
    }
}

Test details

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

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

correct output
1
0
3
3
-1
view save

user output
1
0
3
3
-1
view save

Test 2

Group: 1, 2, 3, 4, 5

Verdict:

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

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

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

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

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
1
2
2
1
2
...
view save

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

Test 4

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

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

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

user output
3
4
2
3
4
...
view save

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

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

correct output
7
view save

user output
7
view save

Test 6

Group: 2, 5

Verdict: ACCEPTED

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

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

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

Test 7

Group: 2, 5

Verdict: ACCEPTED

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

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

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

Test 8

Group: 2, 5

Verdict: ACCEPTED

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

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

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

Test 9

Group: 3, 4, 5

Verdict: ACCEPTED

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

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

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

Test 10

Group: 3, 4, 5

Verdict: ACCEPTED

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

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

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

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

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

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

user output
3
3
3
3
3
...
view save

Test 12

Group: 4, 5

Verdict: ACCEPTED

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

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

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

Test 13

Group: 4, 5

Verdict:

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

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

user output
(empty)

Test 14

Group: 4, 5

Verdict:

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

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

user output
(empty)

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
32
view save

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

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
0
0
0
0
0
...
view save

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

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
1
1
1
1
1
...
view save

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

Test 27

Group: 5

Verdict: ACCEPTED

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

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

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

Tasks

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

Submissions (asonnine)

2025-11-09 13:26:58 1002025-11-09 13:19:43 602025-11-09 13:18:28 602025-11-09 13:16:47 602025-11-09 12:53:03 302025-11-09 11:59:04 02025-11-09 11:10:37 02025-11-07 13:24:46 452025-11-07 09:51:15 02025-11-06 16:39:42 452025-11-06 16:10:31 452025-11-06 16:03:15 302025-11-06 16:01:38 02025-11-06 14:14:51 02025-11-06 13:56:23 02025-11-06 11:51:09 452025-11-05 09:35:07 02025-11-05 09:30:44 02025-11-01 10:30:38 02025-10-31 23:55:59 02025-10-31 23:45:14 02025-10-31 14:24:49 02025-10-31 14:22:28 02025-10-31 14:15:25 02025-10-31 14:12:42 02025-10-31 13:57:14 02025-10-31 13:48:21 02025-10-29 10:36:24 302025-10-28 12:10:07 452025-10-28 08:52:52 302025-10-28 08:31:28 302025-10-27 18:15:18 02025-10-27 18:02:22 0