library_checker/math/
stern_brocot_tree.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algorithm::{SbtNode, SbtPath, SternBrocotTree},
5    num::URational,
6};
7
8#[verify::library_checker("stern_brocot_tree")]
9pub fn stern_brocot_tree(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, t);
13    for _ in 0..t {
14        scan!(scanner, type_: String);
15        match type_.as_str() {
16            "ENCODE_PATH" => {
17                scan!(scanner, a: u32, b: u32);
18                let path = SbtPath::from(URational::new(a, b));
19                let len = if path.path.first() == Some(&0) {
20                    path.path.len() - 1
21                } else {
22                    path.path.len()
23                };
24                write!(writer, "{}", len).ok();
25                for (i, count) in path.into_iter().enumerate() {
26                    if count == 0 {
27                        continue;
28                    }
29                    if i % 2 == 0 {
30                        write!(writer, " R {}", count).ok();
31                    } else {
32                        write!(writer, " L {}", count).ok();
33                    }
34                }
35                writeln!(writer).ok();
36            }
37            "DECODE_PATH" => {
38                scan!(scanner, k, path: [(char, u32); k]);
39                let node: SbtNode<u32> = if path.first().is_some_and(|t| t.0 == 'L') {
40                    [0].into_iter()
41                        .chain(path.into_iter().map(|(_, c)| c))
42                        .collect()
43                } else {
44                    path.into_iter().map(|(_, c)| c).collect()
45                };
46                let val = node.eval();
47                writeln!(writer, "{} {}", val.num, val.den).ok();
48            }
49            "LCA" => {
50                scan!(scanner, [a, b, c, d]: [u32; const 4]);
51                let path1 = SbtPath::from(URational::new(a, b));
52                let path2 = SbtPath::from(URational::new(c, d));
53                let val = SbtNode::lca(path1, path2).eval();
54                writeln!(writer, "{} {}", val.num, val.den).ok();
55            }
56            "ANCESTOR" => {
57                scan!(scanner, [k, a, b]: [u32; const 3]);
58                let mut path = SbtPath::from(URational::new(a, b));
59                let depth = path.depth();
60                if k <= depth {
61                    path.up(depth - k);
62                    let val = path.eval();
63                    writeln!(writer, "{} {}", val.num, val.den).ok();
64                } else {
65                    writeln!(writer, "-1").ok();
66                }
67            }
68            "RANGE" => {
69                scan!(scanner, [a, b]: [u32; const 2]);
70                let node = SbtPath::from(URational::new(a, b)).to_node();
71                writeln!(
72                    writer,
73                    "{} {} {} {}",
74                    node.l.num, node.l.den, node.r.num, node.r.den
75                )
76                .ok();
77            }
78            _ => unreachable!(),
79        }
80    }
81}
library_checker/math/stern_brocot_tree.rs

library_checker/math/
stern_brocot_tree.rs
