CSES - Datatähti 2026 alku

Submission details
Task:	Hypyt
Sender:	asonnine
Submission time:	2025-11-09 13:26:58 +0200
Language:	Rust (2021)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	10
#2	ACCEPTED	20
#3	ACCEPTED	15
#4	ACCEPTED	15
#5	ACCEPTED	40

Test results
test	verdict	time	group
#1	ACCEPTED	0.00 s	1, 2, 3, 4, 5	details
#2	ACCEPTED	0.00 s	1, 2, 3, 4, 5	details
#3	ACCEPTED	0.00 s	1, 2, 3, 4, 5	details
#4	ACCEPTED	0.00 s	1, 2, 3, 4, 5	details
#5	ACCEPTED	0.00 s	1, 2, 3, 4, 5	details
#6	ACCEPTED	0.03 s	2, 5	details
#7	ACCEPTED	0.03 s	2, 5	details
#8	ACCEPTED	0.03 s	2, 5	details
#9	ACCEPTED	0.33 s	3, 4, 5	details
#10	ACCEPTED	0.34 s	3, 4, 5	details
#11	ACCEPTED	0.34 s	3, 4, 5	details
#12	ACCEPTED	0.34 s	4, 5	details
#13	ACCEPTED	0.36 s	4, 5	details
#14	ACCEPTED	0.37 s	4, 5	details
#15	ACCEPTED	0.42 s	5	details
#16	ACCEPTED	0.56 s	5	details
#17	ACCEPTED	0.60 s	5	details
#18	ACCEPTED	0.49 s	5	details
#19	ACCEPTED	0.43 s	5	details
#20	ACCEPTED	0.41 s	5	details
#21	ACCEPTED	0.40 s	5	details
#22	ACCEPTED	0.00 s	1, 2, 3, 4, 5	details
#23	ACCEPTED	0.00 s	1, 2, 3, 4, 5	details
#24	ACCEPTED	0.33 s	5	details
#25	ACCEPTED	0.31 s	5	details
#26	ACCEPTED	0.35 s	5	details
#27	ACCEPTED	0.32 s	5	details

Code

use std::{io, ops::BitAnd};

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct PathNode {
    jump_target: usize,
    second_last_row: usize,
    path_length: i32,
}

#[derive(Debug, Clone, Eq)]
struct Row {
    first_half: u128,
    second_half: u128,
    pub paths: Vec<Option<PathNode>>,
}

impl PartialEq for Row {
    fn eq(&self, other: &Self) -> bool {
        self.first_half == other.first_half && self.second_half == other.second_half
    }
}
impl TryFrom<&Vec<bool>> for Row {
    type Error = ();

    fn try_from(value: &Vec<bool>) -> Result<Self, Self::Error> {
        match value.len() {
            len if len <= 128 => {
                let mut first_half = [false; 128];
                first_half[..len].copy_from_slice(&value);
                let first_half = u128_from_bits(first_half);
                let second_half = 0u128;
                Ok(Row {
                    first_half,
                    second_half,
                    paths: Vec::new(),
                })
            }
            len if len <= 256 => {
                let mut first_half = [false; 128];
                let mut second_half = [false; 128];
                first_half.copy_from_slice(&value[..128]);
                second_half[..len - 128].copy_from_slice(&value[128..]);
                let first_half = u128_from_bits(first_half);
                let second_half = u128_from_bits(second_half);
                Ok(Row {
                    first_half,
                    second_half,
                    paths: Vec::new(),
                })
            }
            _ => Err(()),
        }
    }
}
impl BitAnd for &Row {
    type Output = Row;

    fn bitand(self, rhs: Self) -> Self::Output {
        Row {
            first_half: self.first_half & rhs.first_half,
            second_half: self.second_half & rhs.second_half,
            paths: Vec::new(),
        }
    }
}
impl Row {
    fn is_zero(&self) -> bool {
        self.first_half == 0 && self.second_half == 0
    }
    /*
        fn trailing_zeros(&self) -> u32 {
            let out = self.second_half.trailing_zeros();
            if out == 128 {
                out + self.first_half.trailing_zeros()
            } else {
                out
            }
        }
    */
}
fn u128_from_bits(value: [bool; 128]) -> u128 {
    let mut out = 0u128;
    for i in 0..128 {
        out += (value[i] as u128) << 127 - i;
    }
    out
}

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 columns: Vec<Vec<usize>> = vec![Vec::new(); m];
    for column in 0..m {
        for row in 0..n {
            if map[row][column] {
                columns[column].push(row);
            }
        }
    }

    let mut rows: Vec<Row> = map.iter().map(|row| row.try_into().unwrap()).collect();

    for target_row in 0..n {
        for row in rows.iter_mut() {
            row.paths.push(None);
        }

        for row in 0..n {
            let intersection = &rows[row] & &rows[target_row];
            if !intersection.is_zero() {
                rows[row].paths[target_row] = Some(PathNode {
                    jump_target: target_row,
                    second_last_row: row,
                    path_length: 1,
                });
            }
        }

        for step in 1..n {
            let mut can_continue = false;
            for step_target_row in 0..n {
                if rows[step_target_row].paths[target_row]
                    .is_some_and(|x| x.path_length == step as i32)
                {
                    for row in 0..n {
                        if rows[row].paths[target_row].is_none() {
                            let intersection = &rows[row] & &rows[step_target_row];
                            if !intersection.is_zero() {
                                rows[row].paths[target_row] = Some(PathNode {
                                    jump_target: step_target_row,
                                    second_last_row: rows[step_target_row].paths[target_row]
                                        .unwrap()
                                        .second_last_row,
                                    path_length: (step + 1) as i32,
                                });
                                can_continue = true;
                            }
                        }
                    }
                }
            }
            if !can_continue {
                break;
            }
        }
    }

    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 y1 = iter.next().unwrap().parse::<usize>().unwrap() - 1;
            let x1 = iter.next().unwrap().parse::<usize>().unwrap() - 1;
            let y2 = iter.next().unwrap().parse::<usize>().unwrap() - 1;
            let x2 = iter.next().unwrap().parse::<usize>().unwrap() - 1;

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

    let rows = rows;
    let columns = columns;
    let queries = queries;
    let map = map;

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

fn process_query(
    rows: &Vec<Row>,
    columns: &Vec<Vec<usize>>,
    map: &Vec<Vec<bool>>,
    query: ((usize, usize), (usize, usize)),
) -> i32 {
    if query.0 == query.1 {
        return 0;
    }
    if query.0.0 == query.1.0 || query.0.1 == query.1.1 {
        return 1;
    }
    if rows[query.0.1].paths[query.1.1].is_none() {
        return -1;
    }
    if rows[query.0.1].paths[query.1.1].unwrap().jump_target == query.1.1
        && (map[query.0.1][query.1.0] || map[query.1.1][query.0.0])
    {
        return 2;
    }

    let mut steps1 = 0;
    let mut do_steps2 = false;
    if !map[rows[query.0.1].paths[query.1.1].unwrap().jump_target][query.0.0] {
        steps1 += 1;
        do_steps2 = true;
    }
    let mut current_row = query.0.1;

    steps1 += (rows[current_row].paths[query.1.1].unwrap().path_length - 1) * 2;
    current_row = rows[current_row].paths[query.1.1].unwrap().second_last_row;
    /*
        while rows[current_row].paths[query.1.1].unwrap().jump_target != query.1.1 {
            current_row = rows[current_row].paths[query.1.1].unwrap().jump_target;
            steps1 += 2;
        }
    */

    steps1 += 1;
    if !map[current_row][query.1.0] {
        steps1 += 1;
    }

    let steps_fwd = if do_steps2 {
        let mut steps2 = i32::MAX;
        for row in &columns[query.0.0] {
            if *row != query.0.1 {
                let mut proc_steps = 1;
                let mut current_row = *row;
                if !map[rows[current_row].paths[query.1.1].unwrap().jump_target][query.0.0] {
                    proc_steps += 1;
                }

                proc_steps += (rows[current_row].paths[query.1.1].unwrap().path_length - 1) * 2;
                current_row = rows[current_row].paths[query.1.1].unwrap().second_last_row;
                /*
                                while rows[current_row].paths[query.1.1].unwrap().jump_target != query.1.1 {
                                    current_row = rows[current_row].paths[query.1.1].unwrap().jump_target;
                                    proc_steps += 2;
                                }
                */
                proc_steps += 1;
                if !map[current_row][query.1.0] {
                    proc_steps += 1;
                }

                steps2 = steps2.min(proc_steps);
                if steps2 < steps1 {
                    break;
                }
            }
        }
        i32::min(steps1, steps2)
    } else {
        steps1
    };

    // Try in reverse
    let mut steps1 = 0;
    let mut do_steps2 = false;
    if !map[rows[query.1.1].paths[query.0.1].unwrap().jump_target][query.1.0] {
        steps1 += 1;
        do_steps2 = true;
    }
    let mut current_row = query.1.1;

    steps1 += (rows[current_row].paths[query.0.1].unwrap().path_length - 1) * 2;
    current_row = rows[current_row].paths[query.0.1].unwrap().second_last_row;
    /*
        while rows[current_row].paths[query.0.1].unwrap().jump_target != query.0.1 {
            current_row = rows[current_row].paths[query.0.1].unwrap().jump_target;
            steps1 += 2;
        }
    */

    steps1 += 1;
    if !map[current_row][query.0.0] {
        steps1 += 1;
    }

    let steps_bwd = if do_steps2 {
        let mut steps2 = i32::MAX;
        for row in &columns[query.1.0] {
            if *row != query.1.1 {
                let mut proc_steps = 1;
                let mut current_row = *row;
                if !map[rows[current_row].paths[query.0.1].unwrap().jump_target][query.1.0] {
                    proc_steps += 1;
                }

                proc_steps += (rows[current_row].paths[query.0.1].unwrap().path_length - 1) * 2;
                current_row = rows[current_row].paths[query.0.1].unwrap().second_last_row;
                /*
                                while rows[current_row].paths[query.0.1].unwrap().jump_target != query.0.1 {
                                    current_row = rows[current_row].paths[query.0.1].unwrap().jump_target;
                                    proc_steps += 2;
                                }
                */
                proc_steps += 1;
                if !map[current_row][query.0.0] {
                    proc_steps += 1;
                }

                steps2 = steps2.min(proc_steps);
                if steps2 < steps1 - 1 {
                    break;
                }
            }
        }
        i32::min(steps1, steps2)
    } else {
        steps1
    };
    i32::min(steps_fwd, steps_bwd)
}

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: 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: ACCEPTED

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

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

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

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: ACCEPTED

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

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

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

Test 14

Group: 4, 5

Verdict: ACCEPTED

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

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

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

Test 15

Group: 5

Verdict: ACCEPTED

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

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

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

Test 16

Group: 5

Verdict: ACCEPTED

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

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

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

Test 17

Group: 5

Verdict: ACCEPTED

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

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

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

Test 18

Group: 5

Verdict: ACCEPTED

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

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

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

Test 19

Group: 5

Verdict: ACCEPTED

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

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

user output
`104 422 145 93 65 ...` view save

Test 20

Group: 5

Verdict: ACCEPTED

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

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

user output
`57 155 38 65 98 ...` view save

Test 21

Group: 5

Verdict: ACCEPTED

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

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

user output
`498 498 498 498 498 ...` view save

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: ACCEPTED

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

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

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

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: ACCEPTED

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

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

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

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

Datatähti 2026 alku

Hypyt

Code

Test details

Test 1 (public)

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Tasks

Submissions (asonnine)