CSES - Datatähti 2026 alku

Submission details
Task:	Hypyt
Sender:	JuusoH
Submission time:	2025-11-08 16:10:14 +0200
Language:	Rust (2021)
Status:	READY
Result:	60

Feedback
group	verdict	score
#1	ACCEPTED	10
#2	ACCEPTED	20
#3	ACCEPTED	15
#4	ACCEPTED	15
#5	TIME LIMIT EXCEEDED	0

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.01 s	2, 5	details
#7	ACCEPTED	0.01 s	2, 5	details
#8	ACCEPTED	0.00 s	2, 5	details
#9	ACCEPTED	0.04 s	3, 4, 5	details
#10	ACCEPTED	0.05 s	3, 4, 5	details
#11	ACCEPTED	0.06 s	3, 4, 5	details
#12	ACCEPTED	0.04 s	4, 5	details
#13	ACCEPTED	0.05 s	4, 5	details
#14	ACCEPTED	0.06 s	4, 5	details
#15	ACCEPTED	0.05 s	5	details
#16	ACCEPTED	0.06 s	5	details
#17	ACCEPTED	0.08 s	5	details
#18	ACCEPTED	0.06 s	5	details
#19	ACCEPTED	0.80 s	5	details
#20	ACCEPTED	0.94 s	5	details
#21	TIME LIMIT EXCEEDED	--	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.04 s	5	details
#25	ACCEPTED	0.04 s	5	details
#26	ACCEPTED	0.04 s	5	details
#27	ACCEPTED	0.04 s	5	details

Compiler report

warning: unused variable: `cells`
  --> input/code.rs:50:13
   |
50 |     let mut cells: VecDeque<Pos> = VecDeque::with_capacity(n + m);
   |             ^^^^^ help: if this is intentional, prefix it with an underscore: `_cells`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: variable does not need to be mutable
  --> input/code.rs:50:9
   |
50 |     let mut cells: VecDeque<Pos> = VecDeque::with_capacity(n + m);
   |         ----^^^^^
   |         |
   |         help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

warning: unused variable: `res`
   --> input/code.rs:210:17
    |
210 |             let res = breadth_first_sparse(
    |                 ^^^ help: if this is intentional, prefix it with an underscore: `_res`

warning: unused variable: `len`
   --> input/code.rs:354:17
    |
354 |             let len = rows.len();
    |                 ^^^ help: if this is intentional, prefix it with an underscore: `_len`

warning: unused variable:...

Code

use std::collections::VecDeque;
use std::fs::File;
use std::io::{self, BufRead, BufReader, Write};
use std::time::*;
type Pos = (usize, usize);

fn test_perf() {
    let start_time = SystemTime::now();
    for _ in 0..(2 * 10usize.pow(5)) {
        let mut cells: VecDeque<Pos> = vec![(0, 0)].into();
        cells.reserve(250 + 250);
    }
    let dur = SystemTime::now().duration_since(start_time);
    println!("{:?}", dur.unwrap());
}
fn from_file() {
    let file = File::open("largest_test.txt").unwrap();
    let mut reader = BufReader::new(file);

    // first line
    let mut first_line = String::new();
    reader.read_line(&mut first_line).unwrap();
    let mut parts = first_line.split_whitespace();
    let n: usize = parts.next().unwrap().parse().unwrap();
    let m: usize = parts.next().unwrap().parse().unwrap();
    let q: usize = parts.next().unwrap().parse().unwrap();

    // board
    let mut board: [[bool; 250]; 250] = [[false; 250]; 250];
    for i in 0..n {
        let mut line = String::new();
        reader.read_line(&mut line).unwrap();
        for (l, ch) in line.trim().chars().enumerate() {
            board[i][l] = ch == '*';
        }
    }

    let mut row_safe: Vec<Vec<usize>> = vec![Vec::new(); n];
    let mut col_safe: Vec<Vec<usize>> = vec![Vec::new(); m];

    for i in 0..n {
        for j in 0..m {
            if !board[i][j] {
                row_safe[i].push(j);
                col_safe[j].push(i);
            }
        }
    }

    let mut cells: VecDeque<Pos> = VecDeque::with_capacity(n + m);

    let mut tests: Vec<(usize, usize, usize, usize)> = Vec::with_capacity(q);
    for _ in 0..q {
        let mut line = String::new();
        reader.read_line(&mut line).unwrap();
        let mut parts = line.split_whitespace();
        let y1: usize = parts.next().unwrap().parse().unwrap();
        let x1: usize = parts.next().unwrap().parse().unwrap();
        let y2: usize = parts.next().unwrap().parse().unwrap();
        let x2: usize = parts.next().unwrap().parse().unwrap();
        tests.push((y1 - 1, x1 - 1, y2 - 1, x2 - 1));
    }

    //test_once(&tests, &board, &row_safe, &col_safe, &mut cells, n, m);
    // test_many(&tests, &board, &mut cells, n, m);
}
fn main() {
    //test_perf();
    //from_file();
    //return;
    let mut input = String::new();
    let stdin = io::stdin();
    _ = stdin.read_line(&mut input);
    let mut first_line = input.split_whitespace();
    let n: usize = first_line.next().unwrap().parse().unwrap();
    let m: usize = first_line.next().unwrap().parse().unwrap();
    let q: usize = first_line.next().unwrap().parse().unwrap();

    let mut board: [[bool; 250]; 250] = [[false; 250]; 250];

    for i in 0..n {
        input.clear();
        _ = stdin.read_line(&mut input);
        let mut line = input.chars();

        for l in 0..m {
            board[i][l] = line.next().unwrap() == '*';
        }
    }

    let mut row_safe: Vec<Vec<usize>> = vec![Vec::new(); n];
    let mut col_safe: Vec<Vec<usize>> = vec![Vec::new(); m];

    let mut safe_count = 0;

    for i in 0..n {
        for j in 0..m {
            if !board[i][j] {
                row_safe[i].push(j);
                col_safe[j].push(i);
                safe_count += 1;
            }
        }
    }
    let total = (n * m) as f64;
    let safe_ratio = safe_count as f64 / total;

    let is_sparse = safe_ratio < 0.20;

    let mut cells: VecDeque<Pos> = vec![].into();
    cells.reserve(n + m);

    let mut tests: Vec<(usize, usize, usize, usize)> = vec![];

    for _ in 0..q {
        input.clear();
        _ = stdin.read_line(&mut input);
        let mut line = input.split_whitespace();
        let y1: usize = line.next().unwrap().parse().unwrap();
        let x1: usize = line.next().unwrap().parse().unwrap();
        let y2: usize = line.next().unwrap().parse().unwrap();
        let x2: usize = line.next().unwrap().parse().unwrap();
        tests.push((y1 - 1, x1 - 1, y2 - 1, x2 - 1));
    }
    test_once(
        &tests, &board, &row_safe, &col_safe, &mut cells, n, m, is_sparse,
    );
    //test_many(&tests, &board, &row_safe, &col_safe, &mut cells, n, m);
}

fn test_once(
    tests: &Vec<(usize, usize, usize, usize)>,
    board: &[[bool; 250]; 250],
    safe_cols_in_row: &Vec<Vec<usize>>,
    safe_rows_in_col: &Vec<Vec<usize>>,
    cells: &mut VecDeque<Pos>,
    n: usize,
    m: usize,
    sparse: bool,
) {
    let stdout = io::stdout();
    let mut out = io::BufWriter::new(stdout.lock());

    let mut buffer = Vec::with_capacity(tests.len() * 4);

    for t in tests {
        let start = (t.0, t.1);
        let end = (t.2, t.3);
        let res;
        if sparse {
            res = breadth_first_sparse(
                &board,
                safe_cols_in_row,
                safe_rows_in_col,
                cells,
                start,
                end,
                n,
                m,
            );
        } else {
            res = breadth_first_dense(&board, cells, start, end, n, m);
        }

        write_i32(&mut buffer, res);
        buffer.push(b' ');
    }

    out.write_all(&buffer).unwrap();
    out.flush().unwrap();
}
fn write_i32(buf: &mut Vec<u8>, mut n: i32) {
    if n == -1 {
        buf.push(b'-');
        buf.push(b'1');
        return;
    }
    if n == 0 {
        buf.push(b'0');
        return;
    }
    let mut digits = [0u8; 10];
    let mut i = 0;
    while n > 0 {
        digits[i] = b'0' + (n % 10) as u8;
        n /= 10;
        i += 1;
    }
    for j in (0..i).rev() {
        buf.push(digits[j]);
    }
}

fn test_many(
    tests: &Vec<(usize, usize, usize, usize)>,
    board: &[[bool; 250]; 250],
    safe_cols_in_row: &Vec<Vec<usize>>,
    safe_rows_in_col: &Vec<Vec<usize>>,
    cells: &mut VecDeque<Pos>,
    n: usize,
    m: usize,
) {
    let start_time = SystemTime::now();

    for i in 0..(2 * 10usize.pow(5)) {
        for t in tests {
            let start = (t.0, t.1);
            let end = (t.2, t.3);

            let res = breadth_first_sparse(
                &board,
                safe_cols_in_row,
                safe_rows_in_col,
                cells,
                start,
                end,
                n,
                m,
            );

            if i % 10000 == 0 {
                let dur = SystemTime::now().duration_since(start_time);
                println!(
                    "{} iters per second",
                    (i as f32 / dur.unwrap().as_secs_f32()).round()
                );
            }

            //println!("{res}");
        }
    }
    let dur = SystemTime::now().duration_since(start_time);
    println!("{:?}", dur.unwrap());
}

fn breadth_first_dense(
    board: &[[bool; 250]; 250],
    cells: &mut VecDeque<Pos>,
    start: Pos,
    end: Pos,
    n: usize,
    m: usize,
) -> i32 {
    if start == end {
        return 0;
    }
    if one_jump_gap(&start, &end) {
        return 1;
    }
    if two_jump_gap(board, &start, &end) {
        return 2;
    }
    cells.clear();
    cells.push_back(start);

    let mut rows: Vec<usize> = (0..n).collect();
    let mut cols: Vec<usize> = (0..m).collect();

    rows.swap_remove(start.0);
    cols.swap_remove(start.1);

    let mut jumps = 1;
    //let mut cap = cells.capacity();
    //let mut iters = 0;

    while cells.len() > 0 {
        let cell_len = cells.len();
        for _ in 0..cell_len {
            let cell = cells.pop_back().unwrap(); //.swap_remove(l);

            let len = rows.len();
            for i in (0..len).rev() {
                let row = rows[i];
                //iters += 1;
                if !board[row][cell.1] {
                    let new_cell = (row, cell.1);
                    if two_jump_gap(board, &new_cell, &end) {
                        //println!("iters: {iters}");
                        return jumps + 2;
                    }
                    rows.swap_remove(i);
                    cells.push_front(new_cell);
                    /*if cells.capacity() > cap {
                        println!("cap");
                    }*/
                }
            }
            let len = cols.len();

            for i in (0..len).rev() {
                let col = cols[i];
                //iters += 1;
                if !board[cell.0][col] {
                    let new_cell = (cell.0, col);
                    if two_jump_gap(board, &new_cell, &end) {
                        //println!("iters: {iters}");
                        return jumps + 2;
                    }
                    cols.swap_remove(i);
                    cells.push_front(new_cell);
                    /*if cells.capacity() > cap {
                        println!("cap");
                    }*/
                }
            }
        }
        jumps += 1;
    }

    -1
}

fn breadth_first_sparse(
    board: &[[bool; 250]; 250],
    safe_cols_in_row: &Vec<Vec<usize>>,
    safe_rows_in_col: &Vec<Vec<usize>>,
    cells: &mut VecDeque<Pos>,
    start: Pos,
    end: Pos,
    n: usize,
    m: usize,
) -> i32 {
    if start == end {
        return 0;
    }
    if one_jump_gap(&start, &end) {
        return 1;
    }
    if two_jump_gap(board, &start, &end) {
        return 2;
    }
    cells.clear();
    cells.push_back(start);

    //let mut rows: Vec<usize> = (0..n).collect();
    //let mut cols: Vec<usize> = (0..m).collect();
    let mut rows = [false; 250];
    let mut cols = [false; 250];

    //rows.swap_remove(start.0);
    //cols.swap_remove(start.1);
    rows[start.0] = true;
    cols[start.1] = true;

    let mut jumps = 1;
    //let mut cap = cells.capacity();
    //let mut iters = 0;

    while cells.len() > 0 {
        let cell_len = cells.len();
        for _ in 0..cell_len {
            let cell = cells.pop_back().unwrap(); //.swap_remove(l);

            let len = rows.len();
            for &row in &safe_rows_in_col[cell.1] {
                //let row = rows[i];
                //iters += 1;
                //if !board[row][cell.1] {
                if !rows[row] {
                    rows[row] = true;
                    let new_cell = (row, cell.1);
                    if two_jump_gap(board, &new_cell, &end) {
                        //println!("iters: {iters}");
                        return jumps + 2;
                    }
                    //rows.swap_remove(i);
                    cells.push_front(new_cell);
                    /*if cells.capacity() > cap {
                        println!("cap");
                    }*/
                }
            }
            let len = cols.len();

            for &col in &safe_cols_in_row[cell.0] {
                //let col = cols[i];
                //iters += 1;
                //if !board[cell.0][col] {
                if !cols[col] {
                    cols[col] = true;
                    let new_cell = (cell.0, col);
                    if two_jump_gap(board, &new_cell, &end) {
                        //println!("iters: {iters}");
                        return jumps + 2;
                    }
                    //cols.swap_remove(i);

                    cells.push_front(new_cell);
                    /*if cells.capacity() > cap {
                        println!("cap");
                    }*/
                }
            }
        }
        jumps += 1;
    }

    -1
}

fn one_jump_gap(a: &Pos, b: &Pos) -> bool {
    a.0 == b.0 || a.1 == b.1
}

fn two_jump_gap(board: &[[bool; 250]; 250], a: &Pos, b: &Pos) -> bool {
    !board[a.0][b.1] || !board[b.0][a.1]
}

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 2 2 2 1 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 2 1 3 2 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 2 -1 3 1 2` 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 2 2 2 2 2 2 2 2 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 3 3 2 2 3 2 3 3 2 2 ...` 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 2 3 3 3 3 2 3 3 3 2 ...` 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 2 2 2 2 2 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 2 3 3 3 2 3 2 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 3 3 3 2 3 2 3 3 3 2 ...` 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 2 2 2 2 2 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 2 3 2 2 3 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 2 2 3 3 2 2 2 2 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 2 3 2 2 2 2 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 2 2 2 2 2 2 3 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 3 3 3 2 3 3 3 2 3 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 3 3 2 3 3 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 69 35 27 86 ...` 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 122 73 25 54 1...` view save

Test 21

Group: 5

Verdict: TIME LIMIT EXCEEDED

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

Datatähti 2026 alku

Hypyt

Compiler report

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 (JuusoH)