use competitive_programming_rs :: graph :: maximum_flow :: dinitz :: Dinitz ; fn main () { let (r , w) = (std :: io :: stdin () , std :: io :: stdout ()) ; let mut sc = IO :: new (r . lock () , w . lock ()) ; let n : usize = sc . read () ; let m : usize = sc . read () ; let mut map : Vec < Vec < char > > = (0 .. n) . map (| _ | sc . chars ()) . collect () ; let mut dinitz = Dinitz :: new (m * n + 2) ; let source = m * n ; let sink = source + 1 ; for i in 0 .. n { for j in 0 .. m { if map [i] [j] == '#' { continue ; } let v = i * m + j ; if (i + j) % 2 == 0 { dinitz . add_edge (source , v , 1) ; for & (di , dj) in [(0 , ! 0) , (0 , 1) , (1 , 0) , (! 0 , 0)] . iter () { let ni = i . wrapping_add (di) ; let nj = j . wrapping_add (dj) ; if ni >= n || nj >= m { continue ; } dinitz . add_edge (v , ni * m + nj , 1) ; } } else { dinitz . add_edge (v , sink , 1) ; } } } let flow = dinitz . max_flow (source , sink) ; for from in 0 .. (m * n) { for e in dinitz . g [from] . iter () { if e . is_reversed || e . cap > 0 || e . to == sink { continue ; } let (from_i , from_j) = (from / m , from % m) ; let (to_i , to_j) = (e . to / m , e . to % m) ; assert_eq ! (map [from_i] [from_j] , '.') ; assert_eq ! (map [to_i] [to_j] , '.') ; if from_i < to_i { map [from_i] [from_j] = 'v' ; map [to_i] [to_j] = '^' ; } else if from_i > to_i { map [from_i] [from_j] = '^' ; map [to_i] [to_j] = 'v' ; } else if from_j < to_j { map [from_i] [from_j] = '>' ; map [to_i] [to_j] = '<' ; } else { map [from_i] [from_j] = '<' ; map [to_i] [to_j] = '>' ; } } } sc . write (flow) ; sc . write ('\n') ; for i in 0 .. n { for j in 0 .. m { sc . write (map [i] [j]) ; } sc . write ('\n') ; } } pub struct IO < R , W : std :: io :: Write > (R , std :: io :: BufWriter < W >) ; impl < R : std :: io :: Read , W : std :: io :: Write > IO < R , W > { pub fn new (r : R , w : W) -> Self { Self (r , std :: io :: BufWriter :: new (w)) } pub fn write < S : ToString > (& mut self , s : S) { use std :: io :: Write ; self . 1 . write_all (s . to_string () . as_bytes ()) . unwrap () ; } pub fn read < T : std :: str :: FromStr > (& mut self) -> T { use std :: io :: Read ; let buf = self . 0 . by_ref () . bytes () . map (| b | b . unwrap ()) . skip_while (| & b | b == b' ' || b == b'\n' || b == b'\r' || b == b'\t') . take_while (| & b | b != b' ' && b != b'\n' && b != b'\r' && b != b'\t') . collect :: < Vec < _ > > () ; unsafe { std :: str :: from_utf8_unchecked (& buf) } . parse () . ok () . expect ("Parse error.") } pub fn vec < T : std :: str :: FromStr > (& mut self , n : usize) -> Vec < T > { (0 .. n) . map (| _ | self . read ()) . collect () } pub fn chars (& mut self) -> Vec < char > { self . read :: < String > () . chars () . collect () } }mod competitive_programming_rs { # ! [doc = " # The Competitive Programming Library in Rust"] # ! [doc = " The Competitive Programming Library in Rust is a set of snippets,"] # ! [doc = " which can be used in programming contests."] # ! [allow (clippy :: module_inception)] # ! [allow (clippy :: suspicious_arithmetic_impl)] # [doc = " Algorithms related to graph theory."] pub mod graph { pub mod bridge_detection { pub struct BridgeDetector { articulations : Vec < usize > , bridges : Vec < (usize , usize) > , visit : Vec < bool > , order : Vec < usize > , low_link : Vec < usize > , k : usize , } impl BridgeDetector { pub fn new (graph : & [Vec < usize >]) -> Self { let n = graph . len () ; let mut d = BridgeDetector { articulations : vec ! [] , bridges : vec ! [] , visit : vec ! [false ; n] , order : vec ! [0 ; n] , low_link : vec ! [0 ; n] , k : 0 , } ; d . run (graph) ; d } fn run (& mut self , graph : & [Vec < usize >]) { let n = graph . len () ; for i in 0 .. n { if ! self . visit [i] { self . dfs (i , 0 , graph , i) ; } } } fn dfs (& mut self , v : usize , previous : usize , graph : & [Vec < usize >] , root : usize) { self . visit [v] = true ; self . order [v] = self . k ; self . k += 1 ; self . low_link [v] = self . order [v] ; let mut is_articulation = false ; let mut dimension = 0 ; for & next in graph [v] . iter () { if ! self . visit [next] { dimension += 1 ; self . dfs (next , v , graph , root) ; self . low_link [v] = std :: cmp :: min (self . low_link [v] , self . low_link [next]) ; if v != root && self . order [v] <= self . low_link [next] { is_articulation = true ; } if self . order [v] < self . low_link [next] { let min = std :: cmp :: min (v , next) ; let max = std :: cmp :: max (v , next) ; self . bridges . push ((min , max)) ; } } else if v == root || next != previous { self . low_link [v] = std :: cmp :: min (self . low_link [v] , self . order [next]) ; } } if v == root && dimension > 1 { is_articulation = true ; } if is_articulation { self . articulations . push (v) ; } } } # [cfg (test)] mod tests { use super :: * ; use crate :: utils :: test_helper :: Tester ; # [test] fn solve_grl_3_a () { let tester = Tester :: new ("./assets/GRL_3_A/in/" , "./assets/GRL_3_A/out/") ; tester . test_solution (| sc | { let n : usize = sc . read () ; let m : usize = sc . read () ; let mut graph = vec ! [vec ! [] ; n] ; for _ in 0 .. m { let u : usize = sc . read () ; let v : usize = sc . read () ; graph [u] . push (v) ; graph [v] . push (u) ; } let mut low_link_link = BridgeDetector :: new (& graph) ; low_link_link . articulations . sort () ; for v in low_link_link . articulations . into_iter () { sc . write (format ! ("{}\n" , v)) ; } }) ; } # [test] fn solve_grl_3_b () { let tester = Tester :: new ("./assets/GRL_3_B/in/" , "./assets/GRL_3_B/out/") ; tester . test_solution (| sc | { let n : usize = sc . read () ; let m : usize = sc . read () ; let mut graph = vec ! [vec ! [] ; n] ; for _ in 0 .. m { let u : usize = sc . read () ; let v : usize = sc . read () ; graph [u] . push (v) ; graph [v] . push (u) ; } let mut low_link_link = BridgeDetector :: new (& graph) ; low_link_link . bridges . sort () ; for (a , b) in low_link_link . bridges . into_iter () { sc . write (format ! ("{} {}\n" , a , b)) ; } }) ; } } } pub mod cost_scaling_push_relabel { pub mod cost_scaling_push_relabel { use std :: collections :: VecDeque ; type Flow = i64 ; type Cost = i64 ; const INF_POTENTIAL : f64 = 1e10 ; const SCALING_FACTOR : f64 = 2.0 ; # [derive (Clone)] struct Edge { to : usize , rev : usize , flow : Flow , capacity : Flow , cost : Cost , is_rev : bool , } impl Edge { fn residual (& self) -> Flow { self . capacity - self . flow } } # [derive (Clone)] struct Node { excess_flow : Flow , potential : f64 , } pub struct Solver { nodes : Vec < Node > , graph : Vec < Vec < Edge > > , active_nodes : VecDeque < usize > , cost_scaling_factor : f64 , eps : f64 , } impl Solver { pub fn new (num_nodes : usize) -> Self { Self { nodes : vec ! [Node { excess_flow : 0 , potential : 0.0 } ; num_nodes] , graph : vec ! [vec ! [] ; num_nodes] , active_nodes : VecDeque :: new () , eps : 1.0 , cost_scaling_factor : num_nodes as f64 * 2.0 , } } pub fn add_edge (& mut self , from : usize , to : usize , capacity : Flow , cost : Cost) { let rev = self . graph [to] . len () ; self . graph [from] . push (Edge { to , rev , flow : 0 , capacity , cost , is_rev : false , }) ; let rev = self . graph [from] . len () - 1 ; self . graph [to] . push (Edge { to : from , rev , flow : capacity , capacity , cost : - cost , is_rev : true , }) ; self . eps = max (self . eps , cost . abs () as f64 * self . cost_scaling_factor) ; } pub fn solve (& mut self , source : usize , sink : usize , flow : Flow) -> Flow { self . nodes [source] . excess_flow = flow ; self . nodes [sink] . excess_flow = - flow ; while self . eps > 1.0 { for node in 0 .. self . nodes . len () { for edge in 0 .. self . graph [node] . len () { if self . graph [node] [edge] . is_rev { continue ; } let reduced_cost = self . calc_reduced_cost (node , edge) ; if reduced_cost < 0.0 && self . graph [node] [edge] . residual () > 0 { let f = self . graph [node] [edge] . residual () ; self . push_flow (node , edge , f) ; } if reduced_cost > 0.0 && self . graph [node] [edge] . flow > 0 { let f = - self . graph [node] [edge] . flow ; self . push_flow (node , edge , f) ; } } } self . get_active_nodes () ; while let Some (node) = self . active_nodes . pop_front () { while self . nodes [node] . excess_flow > 0 { if ! self . push (node) { self . relabel (node) ; self . active_nodes . push_back (node) ; break ; } } } self . eps = max (1.0 , self . eps / SCALING_FACTOR) ; } let mut total_cost = 0 ; for e in self . graph . iter () . flat_map (| g | g . iter ()) { if e . is_rev { continue ; } total_cost += e . flow * e . cost ; } total_cost } fn push_flow (& mut self , node : usize , edge : usize , flow : Flow) { self . graph [node] [edge] . flow += flow ; let to = self . graph [node] [edge] . to ; let rev = self . graph [node] [edge] . rev ; let from = node ; self . graph [to] [rev] . flow -= flow ; self . nodes [from] . excess_flow -= flow ; self . nodes [to] . excess_flow += flow ; } fn calc_reduced_cost (& self , node : usize , edge : usize) -> f64 { let cost = self . graph [node] [edge] . cost ; let from = node ; let to = self . graph [node] [edge] . to ; cost as f64 * self . cost_scaling_factor - self . nodes [from] . potential + self . nodes [to] . potential } fn get_active_nodes (& mut self) { for u in 0 .. self . nodes . len () { if self . nodes [u] . excess_flow > 0 { self . active_nodes . push_back (u) ; } } } fn push (& mut self , from : usize) -> bool { if self . nodes [from] . excess_flow == 0 { return false ; } assert ! (self . nodes [from] . excess_flow > 0) ; for i in (0 .. self . graph [from] . len ()) . rev () { if self . graph [from] [i] . residual () == 0 { continue ; } let reduced_cost = self . calc_reduced_cost (from , i) ; if reduced_cost < 0.0 { let flow = min (self . graph [from] [i] . residual () , self . nodes [from] . excess_flow) ; self . push_flow (from , i , flow) ; let to = self . graph [from] [i] . to ; if self . nodes [to] . excess_flow > 0 && self . nodes [to] . excess_flow <= flow { self . active_nodes . push_back (to) ; } return true ; } } false } fn relabel (& mut self , from : usize) { let mut min_potential = INF_POTENTIAL ; for e in self . graph [from] . iter () { if e . residual () > 0 { min_potential = min (min_potential , e . cost as f64 * self . cost_scaling_factor + self . nodes [e . to] . potential + self . eps ,) ; } } assert ! (min_potential < INF_POTENTIAL) ; self . nodes [from] . potential = min_potential ; } } fn min < T : PartialOrd > (a : T , b : T) -> T { if a > b { b } else { a } } fn max < T : PartialOrd > (a : T , b : T) -> T { if a < b { b } else { a } } } # [cfg (test)] mod tests { use crate :: graph :: cost_scaling_push_relabel :: cost_scaling_push_relabel ; use crate :: graph :: min_cost_flow :: primal_dual ; use crate :: utils :: test_helper :: Tester ; # [test] fn solve_grl_6_b () { let tester = Tester :: new ("./assets/GRL_6_B/in/" , "./assets/GRL_6_B/out/") ; tester . test_solution (| sc | { let v : usize = sc . read () ; let e : usize = sc . read () ; let f : i64 = sc . read () ; let mut solver = cost_scaling_push_relabel :: Solver :: new (v) ; let mut verify = primal_dual :: MinimumCostFlowSolver :: new (v) ; for _ in 0 .. e { let u : usize = sc . read () ; let v : usize = sc . read () ; let c : i64 = sc . read () ; let d : i64 = sc . read () ; solver . add_edge (u , v , c , d) ; verify . add_edge (u , v , c , d) ; } match verify . solve (0 , v - 1 , f) { Some (ans) => { sc . write (format ! ("{}\n" , ans)) ; assert_eq ! (ans , solver . solve (0 , v - 1 , f)) ; } _ => { sc . write ("-1\n") ; } } }) ; } } } pub mod lca { pub mod lca { const MAX_PARENT : usize = 1 << 50 ; pub struct LowestCommonAncestor { parent : Vec < Vec < usize > > , depth : Vec < usize > , log_v : usize , } impl LowestCommonAncestor { pub fn new (graph : & [Vec < usize >]) -> Self { let num_v = graph . len () ; let root = 0 ; let mut depth = vec ! [0 ; num_v] ; let mut log_v = 1 ; let mut i = 1 ; while i <= num_v { i *= 2 ; log_v += 1 ; } let mut parent : Vec < Vec < usize > > = vec ! [vec ! [0 ; num_v] ; log_v] ; let mut depth_vis = vec ! [false ; num_v] ; let mut stack = :: std :: collections :: VecDeque :: new () ; stack . push_front (root) ; parent [0] [root] = MAX_PARENT ; depth [root] = 0 ; depth_vis [root] = true ; while ! stack . is_empty () { let v = stack . pop_front () . unwrap () ; stack . push_front (v) ; for & u in & graph [v] { if depth_vis [u] { continue ; } parent [0] [u] = v ; depth [u] = depth [v] + 1 ; depth_vis [u] = true ; stack . push_front (u) ; } let head = stack . pop_front () . unwrap () ; if head != v { stack . push_front (head) ; } } for k in 0 .. (log_v - 1) { for u in 0 .. num_v { parent [k + 1] [u] = if parent [k] [u] == MAX_PARENT { MAX_PARENT } else { parent [k] [parent [k] [u]] } ; } } LowestCommonAncestor { parent , depth , log_v , } } pub fn get_lca (& self , u : usize , v : usize) -> usize { let (mut u , mut v) = if self . depth [u] <= self . depth [v] { (u , v) } else { (v , u) } ; for k in 0 .. self . log_v { if ((self . depth [v] - self . depth [u]) & (1 << k)) != 0 { v = self . parent [k] [v] ; } } if u == v { return u ; } for k in (0 .. self . log_v) . rev () { if self . parent [k] [u] != self . parent [k] [v] { u = self . parent [k] [u] ; v = self . parent [k] [v] ; } } self . parent [0] [u] } pub fn get_dist (& self , u : usize , v : usize) -> usize { let lca = self . get_lca (u , v) ; self . depth [u] + self . depth [v] - self . depth [lca] * 2 } } } # [cfg (test)] mod tests { use super :: lca :: * ; use crate :: utils :: test_helper :: Tester ; # [test] fn solve_grl_5_c () { let tester = Tester :: new ("./assets/GRL_5_C/in/" , "./assets/GRL_5_C/out/") ; tester . test_solution (| sc | { let n : usize = sc . read () ; let mut graph = (0 .. n) . map (| _ | Vec :: new ()) . collect :: < Vec < _ > > () ; for i in 0 .. n { let k = sc . read () ; for _ in 0 .. k { let c : usize = sc . read () ; graph [i] . push (c) ; graph [c] . push (i) ; } } let lca = LowestCommonAncestor :: new (& graph) ; let q : usize = sc . read () ; for _ in 0 .. q { let u : usize = sc . read () ; let v : usize = sc . read () ; let ans = lca . get_lca (u , v) ; sc . write (format ! ("{}\n" , ans)) ; } }) ; } } } pub mod maximum_flow { pub mod dinitz { pub struct Edge { pub to : usize , pub rev : usize , pub is_reversed : bool , pub cap : i64 , } pub struct Dinitz { pub g : Vec < Vec < Edge > > , } impl Dinitz { pub fn new (v : usize) -> Dinitz { let mut g : Vec < Vec < Edge > > = Vec :: new () ; for _ in 0 .. v { g . push (Vec :: new ()) ; } Dinitz { g } } pub fn add_edge (& mut self , from : usize , to : usize , cap : i64) { let to_len = self . g [to] . len () ; let from_len = self . g [from] . len () ; self . g [from] . push (Edge { to , rev : to_len , is_reversed : false , cap , }) ; self . g [to] . push (Edge { to : from , rev : from_len , is_reversed : true , cap : 0 , }) ; } fn dfs (& mut self , v : usize , sink : usize , flow : i64 , level : & [i32] , iter : & mut [usize] ,) -> i64 { if v == sink { return flow ; } while iter [v] < self . g [v] . len () { let flow = std :: cmp :: min (flow , self . g [v] [iter [v]] . cap) ; let to = self . g [v] [iter [v]] . to ; if flow > 0 && level [v] < level [to] { let flowed = self . dfs (to , sink , flow , level , iter) ; if flowed > 0 { let rev = self . g [v] [iter [v]] . rev ; self . g [v] [iter [v]] . cap -= flowed ; self . g [to] [rev] . cap += flowed ; return flowed ; } } iter [v] += 1 ; } 0 } fn bfs (& self , s : usize) -> Vec < i32 > { let v = self . g . len () ; let mut level = vec ! [- 1 ; v] ; level [s] = 0 ; let mut deque = std :: collections :: VecDeque :: new () ; deque . push_back (s) ; while let Some (v) = deque . pop_front () { for e in self . g [v] . iter () { if e . cap > 0 && level [e . to] < 0 { level [e . to] = level [v] + 1 ; deque . push_back (e . to) ; } } } level } pub fn max_flow (& mut self , s : usize , t : usize) -> i64 { let v = self . g . len () ; let mut flow : i64 = 0 ; loop { let level = self . bfs (s) ; if level [t] < 0 { return flow ; } let mut iter = vec ! [0 ; v] ; loop { let f = self . dfs (s , t , std :: i64 :: MAX , & level , & mut iter) ; if f == 0 { break ; } flow += f ; } } } } } # [cfg (test)] mod tests { use super :: * ; use crate :: utils :: test_helper :: Tester ; # [doc = " Solve http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_6_A"] # [test] fn solve_grl_6_a () { let tester = Tester :: new ("./assets/GRL_6_A/in/" , "./assets/GRL_6_A/out/") ; tester . test_solution (| sc | { let v = sc . read () ; let e = sc . read () ; let mut dinitz = dinitz :: Dinitz :: new (v) ; for _ in 0 .. e { let from = sc . read () ; let to = sc . read () ; let c = sc . read () ; dinitz . add_edge (from , to , c) ; } let flow = dinitz . max_flow (0 , v - 1) ; sc . write (format ! ("{}\n" , flow)) ; }) ; } } } pub mod min_cost_flow { pub mod primal_dual { use std :: cmp ; use std :: collections :: BinaryHeap ; use std :: i64 ; type Flow = i64 ; type Cost = i64 ; const INF : Cost = i64 :: MAX >> 3 ; struct Edge { to : usize , capacity : Flow , flow : Flow , cost : Cost , reverse_to : usize , is_reversed : bool , } impl Edge { fn residue (& self) -> Flow { self . capacity - self . flow } } pub struct MinimumCostFlowSolver { graph : Vec < Vec < Edge > > , previous_edge : Vec < (usize , usize) > , } impl MinimumCostFlowSolver { pub fn new (n : usize) -> Self { MinimumCostFlowSolver { graph : (0 .. n) . map (| _ | Vec :: new ()) . collect () , previous_edge : vec ! [(0 , 0) ; n] , } } pub fn add_edge (& mut self , from : usize , to : usize , capacity : Flow , cost : Cost) { let reverse_from = self . graph [to] . len () ; let reverse_to = self . graph [from] . len () ; self . graph [from] . push (Edge { to , capacity , flow : 0 , cost , reverse_to : reverse_from , is_reversed : false , }) ; self . graph [to] . push (Edge { to : from , capacity , flow : capacity , cost : - cost , reverse_to , is_reversed : true , }) ; } pub fn solve (& mut self , source : usize , sink : usize , mut flow : Flow) -> Option < Flow > { let n = self . graph . len () ; let mut result = 0 ; let mut h = vec ! [0 ; n] ; let mut q : BinaryHeap < (Cost , usize) > = BinaryHeap :: new () ; while flow > 0 { let mut dist = vec ! [INF ; n] ; dist [source] = 0 ; q . push ((0 , source)) ; while let Some ((current_dist , v)) = q . pop () { if dist [v] < current_dist { continue ; } for (i , e) in self . graph [v] . iter () . enumerate () { if e . residue () == 0 { continue ; } if dist [e . to] + h [e . to] > current_dist + h [v] + e . cost { dist [e . to] = current_dist + h [v] + e . cost - h [e . to] ; self . previous_edge [e . to] = (v , i) ; q . push ((dist [e . to] , e . to)) ; } } } if dist [sink] == INF { return None ; } for i in 0 .. n { h [i] += dist [i] ; } let mut df = flow ; let mut v = sink ; while v != source { let (prev_v , prev_e) = self . previous_edge [v] ; df = cmp :: min (df , self . graph [prev_v] [prev_e] . residue ()) ; v = prev_v ; } flow -= df ; result += df * h [sink] ; let mut v = sink ; while v != source { let (prev_v , prev_e) = self . previous_edge [v] ; self . graph [prev_v] [prev_e] . flow += df ; let reversed_edge_id = self . graph [prev_v] [prev_e] . reverse_to ; self . graph [v] [reversed_edge_id] . flow -= df ; v = prev_v ; } } Some (result) } pub fn neg_solve (& mut self , source : usize , sink : usize , mut flow : Flow) -> Option < Flow > { let n = self . graph . len () ; let mut result = 0 ; while flow > 0 { let mut dist = vec ! [INF ; n] ; dist [source] = 0 ; loop { let mut updated = false ; for v in 0 .. n { if dist [v] == INF { continue ; } for (i , e) in self . graph [v] . iter () . enumerate () { if e . residue () == 0 { continue ; } if dist [e . to] > dist [v] + e . cost { dist [e . to] = dist [v] + e . cost ; self . previous_edge [e . to] = (v , i) ; updated = true ; } } } if ! updated { break ; } } if dist [sink] == INF { return None ; } let mut df = flow ; let mut v = sink ; while v != source { let (prev_v , prev_e) = self . previous_edge [v] ; df = cmp :: min (df , self . graph [prev_v] [prev_e] . residue ()) ; v = prev_v ; } flow -= df ; result += df * dist [sink] ; let mut v = sink ; while v != source { let (prev_v , prev_e) = self . previous_edge [v] ; self . graph [prev_v] [prev_e] . flow += df ; let reversed_edge_id = self . graph [prev_v] [prev_e] . reverse_to ; self . graph [v] [reversed_edge_id] . flow -= df ; v = prev_v ; } } Some (result) } } } # [cfg (test)] mod tests { use super :: * ; use crate :: utils :: test_helper :: Tester ; # [test] fn solve_grl_6_b () { let tester = Tester :: new ("./assets/GRL_6_B/in/" , "./assets/GRL_6_B/out/") ; tester . test_solution (| sc | { let v : usize = sc . read () ; let e : usize = sc . read () ; let f : i64 = sc . read () ; let mut solver = primal_dual :: MinimumCostFlowSolver :: new (v) ; for _ in 0 .. e { let u : usize = sc . read () ; let v : usize = sc . read () ; let c : i64 = sc . read () ; let d : i64 = sc . read () ; solver . add_edge (u , v , c , d) ; } let ans = match solver . solve (0 , v - 1 , f) { Some (flow) => flow , None => - 1 , } ; sc . write (format ! ("{}\n" , ans)) ; }) ; } # [test] fn solve_grl_6_b_negative () { let tester = Tester :: new ("./assets/GRL_6_B/in/" , "./assets/GRL_6_B/out/") ; tester . test_solution (| sc | { let v : usize = sc . read () ; let e : usize = sc . read () ; let f : i64 = sc . read () ; let mut solver = primal_dual :: MinimumCostFlowSolver :: new (v) ; for _ in 0 .. e { let u : usize = sc . read () ; let v : usize = sc . read () ; let c : i64 = sc . read () ; let d : i64 = sc . read () ; solver . add_edge (u , v , c , d) ; } let ans = match solver . neg_solve (0 , v - 1 , f) { Some (flow) => flow , None => - 1 , } ; sc . write (format ! ("{}\n" , ans)) ; }) ; } } } pub mod shortest_path { pub mod bellman_ford { pub fn shortest_path (graph : & [Vec < (usize , i64) >] , start : usize , inf : i64 ,) -> (Vec < i64 > , Vec < bool >) { let n = graph . len () ; let mut dist = vec ! [inf ; n] ; dist [start] = 0 ; for _ in 0 .. n { for v in 0 .. n { for & (to , cost) in & graph [v] { if dist [v] == inf || dist [to] <= dist [v] + cost { continue ; } dist [to] = dist [v] + cost ; } } } let mut negative = vec ! [false ; n] ; for _ in 0 .. n { for v in 0 .. n { for & (to , cost) in & graph [v] { if dist [v] == inf { continue ; } if dist [to] > dist [v] + cost { dist [to] = dist [v] + cost ; negative [to] = true ; } if negative [v] { negative [to] = true ; } } } } (dist , negative) } } # [cfg (test)] mod tests { use super :: * ; use crate :: utils :: test_helper :: Tester ; use std ; # [test] fn solve_grl_1_b () { let tester = Tester :: new ("./assets/GRL_1_B/in/" , "./assets/GRL_1_B/out/") ; tester . test_solution (| sc | { let v : usize = sc . read () ; let e : usize = sc . read () ; let r : usize = sc . read () ; let mut graph = vec ! [vec ! [] ; v] ; for _ in 0 .. e { let s : usize = sc . read () ; let t : usize = sc . read () ; let d : i64 = sc . read () ; graph [s] . push ((t , d)) ; } let inf = std :: i64 :: MAX ; let (dist , negative) = bellman_ford :: shortest_path (& graph , r , inf) ; let mut neg = false ; for & b in & negative { neg = neg || b ; } if neg { sc . write ("NEGATIVE CYCLE\n") ; } else { for i in 0 .. v { if dist [i] == inf { sc . write ("INF\n") ; } else { sc . write (format ! ("{}\n" , dist [i])) ; } } } }) ; } } } pub mod strongly_connected_components { pub mod strongly_connected_components { use std :: collections :: VecDeque ; pub fn decompose (graph : & [Vec < usize >]) -> Vec < usize > { let mut vs = Vec :: new () ; let num_v = graph . len () ; let mut cmp = vec ! [0 ; num_v] ; let mut reverse_graph = vec ! [vec ! [] ; num_v] ; for (i , edges) in graph . iter () . enumerate () { for & v in edges . iter () { reverse_graph [v] . push (i) ; } } let mut used = vec ! [false ; num_v] ; let mut stack = VecDeque :: new () ; let mut added = vec ! [false ; num_v] ; for i in 0 .. num_v { if used [i] { continue ; } stack . push_front (i) ; while let Some (v) = stack . pop_front () { stack . push_front (v) ; used [v] = true ; let mut pushed = false ; for & u in graph [v] . iter () . rev () { if ! used [u] { stack . push_front (u) ; pushed = true ; } } if ! pushed { stack . pop_front () ; if ! added [v] { vs . push (v) ; added [v] = true ; } } } } used = vec ! [false ; num_v] ; let mut k = 0 ; vs . reverse () ; for & i in vs . iter () { if used [i] { continue ; } stack . push_front (i) ; used [i] = true ; cmp [i] = k ; while let Some (v) = stack . pop_front () { stack . push_front (v) ; let mut pushed = false ; for & u in reverse_graph [v] . iter () { if used [u] { continue ; } used [u] = true ; cmp [u] = k ; stack . push_front (u) ; pushed = true ; } if ! pushed { stack . pop_front () ; } } k += 1 ; } cmp } } # [cfg (test)] mod tests { use super :: * ; use crate :: utils :: test_helper :: Tester ; # [test] fn solve_grl_3_c () { let tester = Tester :: new ("./assets/GRL_3_C/in/" , "./assets/GRL_3_C/out/") ; tester . test_solution (| sc | { let v : usize = sc . read () ; let e : usize = sc . read () ; let mut graph = vec ! [vec ! [] ; v] ; for _ in 0 .. e { let s : usize = sc . read () ; let t : usize = sc . read () ; graph [s] . push (t) ; } let cmp = strongly_connected_components :: decompose (& graph) ; let q : usize = sc . read () ; for _ in 0 .. q { let u : usize = sc . read () ; let v : usize = sc . read () ; if cmp [u] == cmp [v] { sc . write ("1\n") ; } else { sc . write ("0\n") ; } } }) ; } } } } # [doc = " Structures that can efficiently operate data."] pub mod data_structure { pub mod bitset { pub mod bitset { const ONE_VALUE_LENGTH : usize = 63 ; const MAXIMUM : u64 = (1u64 << ONE_VALUE_LENGTH as u64) - 1 ; pub fn get_bit_position (index : usize) -> (usize , usize) { let data_index = index / ONE_VALUE_LENGTH ; let bit_index = index % ONE_VALUE_LENGTH ; (data_index , bit_index) } # [derive (PartialEq , Clone , Debug)] pub struct BitSet { data : Vec < u64 > , } impl std :: ops :: BitOrAssign for BitSet { fn bitor_assign (& mut self , rhs : Self) { if self . data . len () < rhs . data . len () { self . data . resize (rhs . data . len () , 0) ; } let n = if self . data . len () > rhs . data . len () { rhs . data . len () } else { self . data . len () } ; for i in 0 .. n { assert ! (self . data [i] <= MAXIMUM) ; assert ! (rhs . data [i] <= MAXIMUM) ; self . data [i] |= rhs . data [i] ; } } } impl std :: ops :: Shl < usize > for BitSet { type Output = Self ; fn shl (self , rhs : usize) -> Self { self . shift_left (rhs) } } impl BitSet { pub fn new (n : usize) -> Self { let size = (n + ONE_VALUE_LENGTH - 1) / ONE_VALUE_LENGTH ; BitSet { data : vec ! [0 ; size] , } } pub fn new_from (value : u64) -> Self { BitSet { data : vec ! [value] } } pub fn set (& mut self , index : usize , value : bool) { let (data_index , bit_index) = get_bit_position (index) ; assert ! (self . data . len () > data_index) ; if value { self . data [data_index] |= (1 << bit_index) as u64 ; } else { let tmp = MAXIMUM ^ (1 << bit_index) as u64 ; self . data [data_index] &= tmp ; } } pub fn get (& mut self , index : usize) -> bool { let (data_index , bit_index) = get_bit_position (index) ; assert ! (self . data . len () > data_index) ; self . data [data_index] & (1u64 << bit_index as u64) != 0 } pub fn shift_left (& self , shift : usize) -> Self { let mut next_data = Vec :: new () ; let prefix_empty_count = shift / ONE_VALUE_LENGTH ; let shift_count = (shift % ONE_VALUE_LENGTH) as u64 ; for _ in 0 .. prefix_empty_count { next_data . push (0) ; } let mut from_previous = 0 ; let room = ONE_VALUE_LENGTH as u64 - shift_count ; for & data in self . data . iter () { let overflow = (data >> room) << room ; let rest = data - overflow ; let value = (rest << shift_count) + from_previous ; assert ! (value <= MAXIMUM) ; next_data . push (value) ; from_previous = overflow >> room ; } if from_previous > 0 { next_data . push (from_previous) ; } BitSet { data : next_data } } } } # [cfg (test)] mod test { use super :: bitset :: * ; # [test] fn test_set_bit () { let n = 10 ; let value = 717 ; let mut bitset = BitSet :: new (n) ; for i in 0 .. n { if value & (1 << i) != 0 { bitset . set (i , true) ; } } for i in 0 .. n { if value & (1 << i) != 0 { assert ! (bitset . get (i)) ; } else { assert ! (! bitset . get (i)) ; } } } # [test] fn test_bitset_or () { let mut value1 = 717 ; let mut bitset1 = BitSet :: new_from (value1) ; let value2 = 127 ; let bitset2 = BitSet :: new_from (value2) ; value1 |= value2 ; bitset1 |= bitset2 ; for i in 0 .. 50usize { if value1 & (1u64 << i as u64) != 0 { assert ! (bitset1 . get (i)) ; } else { assert ! (! bitset1 . get (i)) ; } } } # [test] fn test_bitset_shift_left () { let value1 = 717 ; let first_shift = 30 ; let second_shift = 40 ; let bitset1 = BitSet :: new_from (value1) << (first_shift + second_shift) ; let bitset2 = BitSet :: new_from (value1 << first_shift as u64) << second_shift ; assert ! (bitset1 == bitset2) ; } } } pub mod fenwick_tree { pub mod fenwick_tree { # [doc = " `FenwickTree` is a data structure that can efficiently update elements"] # [doc = " and calculate prefix sums in a table of numbers."] # [doc = " [https://en.wikipedia.org/wiki/Fenwick_tree](https://en.wikipedia.org/wiki/Fenwick_tree)"] pub struct FenwickTree < T > { n : usize , data : Vec < T > , init : T , } impl < T : Copy + std :: ops :: AddAssign + std :: ops :: Sub < Output = T > > FenwickTree < T > { # [doc = " Constructs a new `FenwickTree`. The size of `FenwickTree` should be specified by `size`."] pub fn new (size : usize , init : T) -> FenwickTree < T > { FenwickTree { n : size + 1 , data : vec ! [init ; size + 1] , init , } } pub fn add (& mut self , k : usize , value : T) { let mut x = k ; while x < self . n { self . data [x] += value ; x |= x + 1 ; } } # [doc = " Returns a sum of range `[l, r)`"] pub fn sum (& self , l : usize , r : usize) -> T { self . sum_one (r) - self . sum_one (l) } # [doc = " Returns a sum of range `[0, k)`"] pub fn sum_one (& self , k : usize) -> T { assert ! (k < self . n , "k={} n={}" , k , self . n) ; let mut result = self . init ; let mut x = k as i32 - 1 ; while x >= 0 { result += self . data [x as usize] ; x = (x & (x + 1)) - 1 ; } result } } } # [cfg (test)] mod test { use super :: fenwick_tree :: FenwickTree ; use rand :: { thread_rng , Rng } ; # [test] fn random_array () { let n = 1000 ; let mut bit = FenwickTree :: new (n , 0) ; let mut v = vec ! [0 ; n] ; for _ in 0 .. 10000 { let value = thread_rng () . gen_range (0 , 1000) ; let k = thread_rng () . gen_range (0 , n) ; v [k] += value ; bit . add (k , value) ; let mut sum = 0 ; for i in 0 .. n { sum += v [i] ; assert_eq ! (sum , bit . sum (0 , i + 1)) ; } } } } } pub mod fibonacci_heap { pub mod fibonacci_heap { fn store_to_map < T , F > (map : & mut std :: collections :: HashMap < usize , Node < T > > , mut node : Node < T > , ordering : F ,) where T : Copy + PartialEq , F : Fn (T , T) -> T , { let d = node . children . len () ; match map . remove (& d) { Some (mut other) => { let node = if (ordering) (node . key , other . key) == node . key { node . children . push (other) ; node } else { other . children . push (node) ; other } ; store_to_map (map , node , ordering) ; } None => { map . insert (d , node) ; } } } pub struct FibonacciHeap < T , F > { pub nodes : Vec < Node < T > > , min_index : usize , ordering : F , } impl < T , F > FibonacciHeap < T , F > where T : Copy + PartialEq , F : Fn (T , T) -> T + Copy , { pub fn new (ordering : F) -> Self { Self { nodes : Vec :: new () , min_index : 0 , ordering , } } pub fn push (& mut self , x : T) { let node = Node :: new (x) ; self . nodes . push (node) ; let cur_min = self . nodes [self . min_index] . key ; if (self . ordering) (cur_min , x) == x { self . min_index = self . nodes . len () - 1 ; } } pub fn pop (& mut self) -> Option < T > { let mut map = std :: collections :: HashMap :: < usize , Node < T > > :: new () ; let mut popped = None ; let mut nodes = Vec :: new () ; std :: mem :: swap (& mut self . nodes , & mut nodes) ; for (i , node) in nodes . into_iter () . enumerate () { if i == self . min_index { popped = Some (node . key) ; for node in node . children . into_iter () { store_to_map (& mut map , node , self . ordering) ; } } else { store_to_map (& mut map , node , self . ordering) ; } } self . nodes = map . into_iter () . map (| (_ , node) | node) . collect () ; if ! self . nodes . is_empty () { let mut min = self . nodes [0] . key ; for i in 0 .. self . nodes . len () { if (self . ordering) (min , self . nodes [i] . key) == self . nodes [i] . key { min = self . nodes [i] . key ; } } self . min_index = self . nodes . iter () . enumerate () . find (| (_ , node) | node . key == min) . unwrap () . 0 ; } else { self . min_index = 0 ; } popped } } # [derive (Debug)] pub struct Node < T > { pub key : T , pub children : Vec < Node < T > > , } impl < T > Node < T > { fn new (x : T) -> Self { Self { key : x , children : Vec :: new () , } } } } # [cfg (test)] mod tests { use super :: fibonacci_heap :: * ; use rand :: Rng ; use std :: cmp ; use std :: collections :: BinaryHeap ; # [test] fn test_fibonacci_heap () { let mut min_heap = FibonacciHeap :: new (cmp :: min) ; min_heap . push (1) ; assert_eq ! (min_heap . pop () , Some (1)) ; min_heap . push (1) ; min_heap . push (2) ; min_heap . push (3) ; assert_eq ! (min_heap . pop () , Some (1)) ; assert_eq ! (min_heap . pop () , Some (2)) ; assert_eq ! (min_heap . pop () , Some (3)) ; min_heap . push (3) ; min_heap . push (2) ; min_heap . push (1) ; assert_eq ! (min_heap . pop () , Some (1)) ; assert_eq ! (min_heap . pop () , Some (2)) ; assert_eq ! (min_heap . pop () , Some (3)) ; } # [test] fn compare_to_binary_heap () { let mut rng = rand :: thread_rng () ; let mut max_heap = FibonacciHeap :: new (cmp :: max) ; let mut binary_heap = BinaryHeap :: new () ; for _ in 0 .. 2000 { let x = rng . gen :: < usize > () % 10 ; if x == 0 { assert_eq ! (max_heap . pop () , binary_heap . pop ()) ; } else { let v = rng . gen :: < u8 > () ; max_heap . push (v) ; binary_heap . push (v) ; } } } } } pub mod persistent_array { pub mod persistent_array { use std :: rc :: Rc ; const N : usize = 20 ; # [derive (Clone)] pub struct Node < T : Clone > { data : Option < T > , children : [Option < Rc < Node < T > > > ; N] , } impl < T : Clone > Node < T > { pub fn new (data : Option < T > , children : [Option < Rc < Node < T > > > ; N]) -> Self { Self { data , children } } } impl < T : Clone > Default for Node < T > { fn default () -> Self { Self { data : None , children : Default :: default () , } } } pub fn set < T : Clone > (index : usize , data : T , node : Option < Rc < Node < T > > >) -> Rc < Node < T > > { if index == 0 { match node { Some (node) => { let new_node = Node :: new (Some (data) , node . children . clone ()) ; Rc :: new (new_node) } None => Rc :: new (Node :: new (Some (data) , Default :: default ())) , } } else { let child = match node . as_ref () . and_then (| node | node . children [index % N] . as_ref ()) { Some (next_node) => set (index / N , data , Some (next_node . clone ())) , None => set (index / N , data , None) , } ; let mut new_node = match node { Some (node) => node . as_ref () . clone () , None => Node :: default () , } ; new_node . children [index % N] = Some (child) ; Rc :: new (new_node) } } pub fn get < T : Clone > (index : usize , node : & Rc < Node < T > >) -> Option < T > { if index == 0 { node . data . clone () } else { match node . children [index % N] . as_ref () { Some (next_node) => get (index / N , next_node) , None => None , } } } } # [cfg (test)] mod tests { use crate :: data_structure :: persistent_array :: persistent_array :: { get , set , Node } ; use rand :: distributions :: Uniform ; use rand :: { thread_rng , Rng } ; use std :: rc :: Rc ; # [test] fn test_persistent_array () { let mut rng = thread_rng () ; let n : usize = 20 ; let mut vs = vec ! [vec ! [None ; n]] ; let mut nodes = vec ! [Rc :: new (Node :: default ())] ; for _ in 0 .. 10000 { let pick = rng . sample (Uniform :: from (0 .. vs . len ())) ; let mut new_vec = vs [pick] . clone () ; let node = nodes [pick] . clone () ; let pos = rng . sample (Uniform :: from (0 .. n)) ; let value : i64 = rng . gen () ; new_vec [pos] = Some (value) ; let new_node = set (pos , value , Some (node)) ; for i in 0 .. n { let expected = new_vec [i] ; let actual = get (i , & new_node) ; assert_eq ! (expected , actual) ; } vs . push (new_vec . clone ()) ; nodes . push (new_node . clone ()) ; let value : i64 = rng . gen () ; new_vec [pos] = Some (value) ; let new_node = set (pos , value , Some (new_node)) ; for i in 0 .. n { let expected = new_vec [i] ; let actual = get (i , & new_node) ; assert_eq ! (expected , actual) ; } vs . push (new_vec . clone ()) ; nodes . push (new_node) ; } } } } pub mod range_add_segment_tree { pub mod range_add_segment_tree { type Range = std :: ops :: Range < usize > ; pub struct RangeAddSegmentTree < T , F > { data : Vec < T > , lazy : Vec < T > , size : usize , f : F , init : T , } impl < T , F > RangeAddSegmentTree < T , F > where T : PartialOrd + :: std :: ops :: Add < Output = T > + :: std :: ops :: Sub < Output = T > + Copy , F : Fn (T , T) -> T + Copy , { pub fn new (n : usize , init : T , f : F , zero : T) -> Self { let size = n . next_power_of_two () ; RangeAddSegmentTree { data : vec ! [init ; size * 2] , lazy : vec ! [zero ; size * 2] , size , init , f , } } pub fn add (& mut self , range : Range , value : T) { self . add_to_range (range , value , 0 , 0 .. self . size) ; } fn add_to_range (& mut self , add_range : Range , value : T , mut k : usize , seg_range : Range) { if add_range . end <= seg_range . start || seg_range . end <= add_range . start { return ; } if add_range . start <= seg_range . start && seg_range . end <= add_range . end { self . lazy [k] = self . lazy [k] + value ; while k > 0 { k = (k - 1) / 2 ; self . data [k] = (self . f) (self . data [k * 2 + 1] + self . lazy [k * 2 + 1] , self . data [k * 2 + 2] + self . lazy [k * 2 + 2] ,) ; } } else { let mid = (seg_range . start + seg_range . end) / 2 ; self . add_to_range (add_range . clone () , value , k * 2 + 1 , seg_range . start .. mid) ; self . add_to_range (add_range , value , k * 2 + 2 , mid .. seg_range . end) ; } } pub fn update (& mut self , pos : usize , value : T) { let cur = self . get (pos .. (pos + 1)) ; let mut k = pos + self . size - 1 ; let raw = self . data [k] ; self . data [k] = raw + value - cur ; while k > 0 { k = (k - 1) / 2 ; self . data [k] = (self . f) (self . data [k * 2 + 1] , self . data [k * 2 + 2]) ; } } pub fn get (& self , range : Range) -> T { self . get_from_range (range , 0 , 0 .. self . size) } fn get_from_range (& self , get_range : Range , k : usize , seg_range : Range) -> T { if get_range . end <= seg_range . start || seg_range . end <= get_range . start { self . init } else if get_range . start <= seg_range . start && seg_range . end <= get_range . end { self . data [k] + self . lazy [k] } else { let mid = (seg_range . start + seg_range . end) / 2 ; let x = self . get_from_range (get_range . clone () , k * 2 + 1 , seg_range . start .. mid) ; let y = self . get_from_range (get_range , k * 2 + 2 , mid .. seg_range . end) ; (self . f) (x , y) + self . lazy [k] } } } } # [cfg (test)] mod test { use super :: * ; use rand :: Rng ; use std :: cmp ; const INF : i64 = 1 << 60 ; # [test] fn edge_case () { let n = 5 ; let mut seg_min = range_add_segment_tree :: RangeAddSegmentTree :: new (n , INF as usize , | a , b | if a > b { b } else { a } , 0 ,) ; let mut values = vec ! [0 ; n] ; for i in 0 .. n { values [i] = i ; seg_min . update (i , i) ; } let from = 1 ; let to = 4 ; let add = 2 ; for i in from .. to { values [i] += add ; } seg_min . add (from .. to , add) ; let pos = 2 ; let value = 1 ; let cur = seg_min . get (pos .. (pos + 1)) ; seg_min . update (pos , cur - value) ; values [pos] -= value ; for l in 0 .. n { for r in (l + 1) .. (n + 1) { let min1 = seg_min . get (l .. r) ; let & min2 = values [l .. r] . iter () . min () . unwrap () ; assert_eq ! (min1 , min2) ; } } } # [test] fn random_add () { let n = 32 ; let mut array = vec ! [0 ; n] ; let mut seg_min = range_add_segment_tree :: RangeAddSegmentTree :: new (n , INF , | a , b | if a > b { b } else { a } , 0 ,) ; let mut seg_max = range_add_segment_tree :: RangeAddSegmentTree :: new (n , - INF , | a , b | if a < b { b } else { a } , 0 ,) ; for i in 0 .. n { let value = rand :: thread_rng () . gen :: < i16 > () as i64 ; array [i] = value ; seg_min . update (i , value) ; seg_max . update (i , value) ; } for l in 0 .. n { for r in (l + 1) .. n { let value = rand :: thread_rng () . gen :: < i16 > () as i64 ; seg_min . add (l .. r , value) ; seg_max . add (l .. r , value) ; for i in l .. r { array [i] += value ; } for l in 0 .. n { for r in (l + 1) .. n { let mut min = INF ; let mut max = - INF ; for i in l .. r { min = cmp :: min (min , array [i]) ; max = cmp :: max (max , array [i]) ; } assert_eq ! (seg_min . get (l .. r) , min) ; assert_eq ! (seg_max . get (l .. r) , max) ; } } } } } } } pub mod segment_tree { # [doc = " Segment Tree for range queries"] pub struct SegmentTree < T , F > { seg : Vec < T > , n : usize , f : F , initial_value : T , } impl < T : Copy , F > SegmentTree < T , F > where F : Fn (T , T) -> T , { pub fn new (size : usize , initial_value : T , f : F) -> SegmentTree < T , F > { let mut m = 1 ; while m <= size { m <<= 1 ; } SegmentTree { seg : vec ! [initial_value ; m * 2] , n : m , f , initial_value , } } pub fn update (& mut self , k : usize , value : T) { let mut k = k ; k += self . n - 1 ; self . seg [k] = value ; while k > 0 { k = (k - 1) >> 1 ; self . seg [k] = (self . f) (self . seg [k * 2 + 1] , self . seg [k * 2 + 2]) ; } } # [doc = " Get the minimum value in the array in the range"] pub fn query (& self , range : std :: ops :: Range < usize >) -> T { self . query_range (range , 0 , 0 .. self . n) } fn query_range (& self , range : std :: ops :: Range < usize > , k : usize , seg_range : std :: ops :: Range < usize > ,) -> T { if seg_range . end <= range . start || range . end <= seg_range . start { self . initial_value } else if range . start <= seg_range . start && seg_range . end <= range . end { self . seg [k] } else { let mid = (seg_range . start + seg_range . end) >> 1 ; let x = self . query_range (range . clone () , k * 2 + 1 , seg_range . start .. mid) ; let y = self . query_range (range , k * 2 + 2 , mid .. seg_range . end) ; (self . f) (x , y) } } } # [cfg (test)] mod test { use super :: * ; use rand :: Rng ; use std :: cmp ; use std :: i64 :: MAX ; # [test] fn random_array () { let n = 1000 ; let arr = (0 .. n) . map (| _ | { return rand :: thread_rng () . gen :: < i64 > () ; }) . collect :: < Vec < _ > > () ; let mut seg = SegmentTree :: new (n , MAX , | a , b | cmp :: min (a , b)) ; for i in 0 .. n { let mut minimum = MAX ; for j in 0 .. (i + 1) { minimum = cmp :: min (minimum , arr [j]) ; } seg . update (i , arr [i]) ; assert_eq ! (seg . query (0 .. n) , minimum) ; assert_eq ! (seg . query (0 .. (i + 1)) , minimum) ; } } # [test] fn random_array_online_update () { let n = 1000 ; let mut arr = vec ! [MAX ; n] ; let mut seg = SegmentTree :: new (n , MAX , | a , b | cmp :: min (a , b)) ; for _ in 0 .. n { let value = rand :: thread_rng () . gen :: < i64 > () ; let k = rand :: thread_rng () . gen_range (0 , n) ; seg . update (k , value) ; arr [k] = value ; let mut minimum = MAX ; for i in 0 .. n { minimum = cmp :: min (minimum , arr [i]) ; } assert_eq ! (seg . query (0 .. n) , minimum) ; } } } } pub mod sparse_table { pub mod sparse_table { pub struct SparseTable < T , F > { data : Vec < Vec < T > > , op : F , } impl < T , F > SparseTable < T , F > where T : Copy , F : Fn (T , T) -> T , { pub fn from (v : & [T] , init : T , op : F) -> Self { let size = v . len () . next_power_of_two () ; let count = size . trailing_zeros () as usize + 1 ; let mut data = vec ! [vec ! [init ; size] ; count] ; for (i , v) in v . iter () . cloned () . enumerate () { data [0] [i] = v ; } for c in 1 .. count { for i in 0 .. size { let next = std :: cmp :: min (size - 1 , i + (1 << (c - 1))) ; data [c] [i] = op (data [c - 1] [i] , data [c - 1] [next]) ; } } Self { data , op } } # [doc = " get the result for [l, r)"] pub fn get (& self , l : usize , r : usize) -> T { assert ! (l < r) ; let length = r - l ; if length == 1 { return self . data [0] [l] ; } let block_size = length . next_power_of_two () >> 1 ; let c = block_size . trailing_zeros () as usize ; let left = self . data [c] [l] ; let right = self . data [c] [r - block_size] ; (self . op) (left , right) } } } # [cfg (test)] mod test { use super :: * ; use rand :: { thread_rng , Rng } ; use std :: cmp ; # [test] fn test_small () { let v = vec ! [1 , 9 , 9 , 1 , 0 , 7 , 1 , 7] ; let sparse_table = sparse_table :: SparseTable :: from (& v , 0 , | a , b | cmp :: min (a , b)) ; for l in 0 .. 8 { for r in (l + 1) .. 9 { let & min = v [l .. r] . iter () . min () . unwrap () ; assert_eq ! (sparse_table . get (l , r) , min) ; } } } # [test] fn test_sparse_table_with_random_array () { let n = 1000 ; let v : Vec < u64 > = (0 .. n) . map (| _ | thread_rng () . gen_range (0 , 1000000000)) . collect () ; let sparse_table = sparse_table :: SparseTable :: from (& v , 0 , cmp :: min) ; for l in 0 .. n { for r in (l + 1) .. (n + 1) { let & min = v [l .. r] . iter () . min () . unwrap () ; assert_eq ! (sparse_table . get (l , r) , min) ; } } } } } pub mod suffix_array { pub struct SuffixArray { n : usize , s : Vec < u8 > , array : Vec < usize > , } fn compare_node (i : usize , j : usize , k : usize , rank : & [i32]) -> std :: cmp :: Ordering { if rank [i] != rank [j] { rank [i] . cmp (& rank [j]) } else { let ri = if i + k <= rank . len () { rank [i + k] } else { - 1 } ; let rj = if j + k <= rank . len () { rank [j + k] } else { - 1 } ; ri . cmp (& rj) } } impl SuffixArray { pub fn new (s : & [u8]) -> SuffixArray { let n = s . len () ; let mut rank = vec ! [0 ; n + 1] ; let mut array = vec ! [0 ; n + 1] ; for i in 0 .. (n + 1) { array [i] = i ; rank [i] = if i < n { s [i] as i32 } else { - 1 } ; } let mut tmp = vec ! [0 ; n + 1] ; let mut k = 1 ; while k <= n { array . sort_by (| a , b | compare_node (* a , * b , k , & rank)) ; tmp [array [0]] = 0 ; for i in 1 .. (n + 1) { tmp [array [i]] = tmp [array [i - 1]] + if compare_node (array [i - 1] , array [i] , k , & rank) == std :: cmp :: Ordering :: Less { 1 } else { 0 } } rank [.. (n + 1)] . clone_from_slice (& tmp [.. (n + 1)]) ; k *= 2 ; } SuffixArray { n , array , s : Vec :: from (s) , } } pub fn contains (& self , t : & [u8]) -> bool { let b = self . lower_bound (t) ; if b >= self . array . len () { false } else { let start = self . array [b] ; let end = std :: cmp :: min (t . len () + start , self . s . len ()) ; let sub = & self . s [start .. end] ; sub . cmp (t) == std :: cmp :: Ordering :: Equal } } fn binary_search < F > (& self , string : & [u8] , f : F) -> usize where F : Fn (& [u8] , & [u8]) -> bool , { let (mut ng , mut ok) = (- 1 , self . n as i32 + 1) ; while ok - ng > 1 { let pos = (ng + ok) / 2 ; let start = self . array [pos as usize] ; let end = std :: cmp :: min (start + string . len () , self . s . len ()) ; let substring = & self . s [start .. end] ; if f (substring , string) { ng = pos ; } else { ok = pos ; } } ok as usize } pub fn lower_bound (& self , t : & [u8]) -> usize { let check_function = | sub : & [u8] , s : & [u8] | sub . cmp (s) == std :: cmp :: Ordering :: Less ; self . binary_search (t , check_function) } pub fn upper_bound (& self , t : & [u8]) -> usize { let check_function = | sub : & [u8] , s : & [u8] | sub . cmp (s) != std :: cmp :: Ordering :: Greater ; self . binary_search (t , check_function) } } # [cfg (test)] mod test { use super :: * ; use crate :: data_structure :: segment_tree :: SegmentTree ; use crate :: utils :: test_helper :: Tester ; use std ; use std :: cmp ; # [test] fn small_test () { let string = "abcdeabcde" . to_owned () . bytes () . collect :: < Vec < _ > > () ; let sa = SuffixArray :: new (& string) ; assert_eq ! (sa . lower_bound (& "a" . to_owned () . bytes () . collect ::< Vec < _ >> ()) , 1) ; assert_eq ! (sa . upper_bound (& "a" . to_owned () . bytes () . collect ::< Vec < _ >> ()) , 3) ; assert ! (sa . contains (& "abcde" . to_owned () . bytes () . collect ::< Vec < _ >> ())) ; assert ! (! sa . contains (& "abce" . to_owned () . bytes () . collect ::< Vec < _ >> ())) ; } # [test] fn corner_case () { let string = "cba" . to_owned () . bytes () . collect :: < Vec < _ > > () ; let sa = SuffixArray :: new (& string) ; assert_eq ! (sa . lower_bound (& "c" . to_owned () . bytes () . collect ::< Vec < _ >> ()) , 3) ; assert_eq ! (sa . upper_bound (& "c" . to_owned () . bytes () . collect ::< Vec < _ >> ()) , 4) ; } # [test] fn jag2014summer_day4_f () { let tester = Tester :: new ("./assets/jag2014summer-day4/F/in/" , "./assets/jag2014summer-day4/F/out/" ,) ; tester . test_solution (| sc | { let s : Vec < u8 > = sc . read :: < String > () . bytes () . collect () ; let n = s . len () ; let reverse_s = { let mut r = s . clone () ; r . reverse () ; r } ; let sa = SuffixArray :: new (& s) ; let reverse_sa = SuffixArray :: new (& reverse_s) ; let mut rmq = SegmentTree :: new (n + 1 , std :: i64 :: MAX , | a , b | cmp :: min (a , b)) ; let mut reverse_rmq = SegmentTree :: new (n + 1 , std :: i64 :: MAX , | a , b | cmp :: min (a , b)) ; for i in 0 .. (n + 1) { rmq . update (i , sa . array [i] as i64) ; reverse_rmq . update (i , reverse_sa . array [i] as i64) ; } let m : usize = sc . read () ; for _ in 0 .. m { let x = sc . read :: < String > () . bytes () . collect :: < Vec < _ > > () ; let y = { let mut y : Vec < u8 > = sc . read :: < String > () . bytes () . collect :: < Vec < _ > > () ; y . reverse () ; y } ; if ! sa . contains (& x) { sc . write ("0\n") ; continue ; } let low = sa . lower_bound (& x) ; let up = sa . upper_bound (& x) ; if ! reverse_sa . contains (& y) { sc . write ("0\n") ; continue ; } let reverse_low = reverse_sa . lower_bound (& y) ; let reverse_up = reverse_sa . upper_bound (& y) ; if low >= up || reverse_low >= reverse_up { sc . write ("0\n") ; } let s = rmq . query (low .. up) as usize ; let t = n - reverse_rmq . query (reverse_low .. reverse_up) as usize ; if s + x . len () <= t && s <= t - y . len () { sc . write (format ! ("{}\n" , t - s)) ; } else { sc . write ("0\n") ; } } }) ; } } } pub mod treap { pub mod treap { use std :: cmp :: Ordering :: * ; type Link < T > = Option < Box < Node < T > > > ; # [derive (Debug)] struct Node < T > { left : Link < T > , right : Link < T > , key : T , priority : u32 , count : usize , } impl < T > Node < T > { fn new (key : T , priority : u32) -> Link < T > { Some (Box :: new (Node { left : None , right : None , key , priority , count : 1 , })) } fn update (& mut self) { self . count = 1 + count (& self . left) + count (& self . right) ; } } # [doc = " `Treap` is a binary search tree data structure that maintain a dynamic set"] # [doc = " of ordered keys and allow binary searches among the keys,"] # [doc = " [https://en.wikipedia.org/wiki/Treap](https://en.wikipedia.org/wiki/Treap)"] # [derive (Debug)] pub struct Treap < T > { random_state : XorShift , root : Link < T > , } impl < T : PartialOrd > Treap < T > where T : Clone , { pub fn new (seed : u32) -> Self { Treap { random_state : XorShift { state : seed } , root : None , } } pub fn clear (& mut self) { self . root = None } pub fn is_empty (& self) -> bool { count (& self . root) == 0 } pub fn insert (& mut self , key : T) { if ! self . contains (& key) { self . root = insert (self . root . take () , key , & mut self . random_state) ; } } pub fn contains (& self , key : & T) -> bool { find (& self . root , key) . is_some () } pub fn erase (& mut self , key : & T) { self . root = erase (self . root . take () , key) ; } pub fn nth (& self , n : usize) -> & T { match rank (& self . root , n) { Some (r) => & r . key , None => panic ! () , } } } fn find < T : PartialOrd > (node : & Link < T > , key : & T) -> Option < usize > { match node { None => None , Some (node) => match node . key . partial_cmp (key) . unwrap () { Equal => Some (count (& node . left)) , Greater => find (& node . left , key) , Less => match find (& node . right , key) { None => None , Some (pos) => Some (count (& node . left) + 1 + pos) , } , } , } } fn count < T > (node : & Link < T >) -> usize { match node { None => 0 , Some (node) => node . count , } } fn rotate_left < T > (node : Link < T >) -> Link < T > { let mut node = node . unwrap () ; let mut r = node . right . take () . unwrap () ; node . right = r . left . take () ; node . update () ; r . left = Some (node) ; Some (r) } fn rotate_right < T > (node : Link < T >) -> Link < T > { let mut node = node . unwrap () ; let mut l = node . left . take () . unwrap () ; node . left = l . right . take () ; node . update () ; l . right = Some (node) ; Some (l) } fn insert < T : PartialOrd > (node : Link < T > , key : T , rand : & mut XorShift) -> Link < T > { match node { None => Node :: new (key , rand . next ()) , Some (mut node) => { match node . key . partial_cmp (& key) . unwrap () { Less => { node . right = insert (node . right . take () , key , rand) ; if priority (& node . right) < node . priority { node = rotate_left (Some (node)) . unwrap () ; } } _ => { node . left = insert (node . left . take () , key , rand) ; if priority (& node . left) < node . priority { node = rotate_right (Some (node)) . unwrap () ; } } } node . update () ; Some (node) } } } fn priority < T > (node : & Link < T >) -> u32 { match * node { None => panic ! () , Some (ref node) => node . priority , } } fn min < T > (node : & Link < T >) -> & Link < T > { match node { Some (x) => match x . left { Some (_) => min (& x . left) , None => node , } , None => panic ! () , } } fn erase < T : PartialOrd > (node : Link < T > , key : & T) -> Link < T > where T : Clone , { match node { None => panic ! () , Some (mut node) => match node . key . partial_cmp (key) . unwrap () { Equal => { if node . left . is_none () { node . right } else if node . right . is_none () { node . left } else { node . key = match min (& node . right) { Some (m) => m . key . clone () , None => panic ! () , } ; node . right = erase (node . right . take () , & node . key) ; node . update () ; Some (node) } } Less => { node . right = erase (node . right . take () , key) ; node . update () ; Some (node) } Greater => { node . left = erase (node . left . take () , key) ; node . update () ; Some (node) } } , } } fn rank < T > (node : & Link < T > , r : usize) -> & Link < T > { match node { Some (c) => { let left = count (& c . left) ; match left . cmp (& r) { std :: cmp :: Ordering :: Equal => node , std :: cmp :: Ordering :: Less => rank (& c . right , r - left - 1) , std :: cmp :: Ordering :: Greater => rank (& c . left , r) , } } None => panic ! () , } } # [derive (Debug)] struct XorShift { state : u32 , } impl XorShift { fn next (& mut self) -> u32 { self . state = xor_shift (self . state) ; self . state } } fn xor_shift (state : u32) -> u32 { let mut x = state ; x ^= x << 13 ; x ^= x >> 17 ; x ^= x << 5 ; x } } # [cfg (test)] mod test { use super :: * ; # [test] fn test_treap_insert_erase () { let mut treap = treap :: Treap :: new (71) ; let max = 1000000 ; for i in 0 .. max { assert ! (! treap . contains (& i)) ; treap . insert (i) ; assert ! (treap . contains (& i)) ; } for i in 0 .. max { assert ! (treap . contains (& i)) ; treap . erase (& i) ; assert ! (! treap . contains (& i)) ; } } # [test] fn test_treap_nth () { let mut treap = treap :: Treap :: new (71) ; let max = 100000 ; for i in 0 .. max { treap . insert (i * 2) ; } for i in 0 .. max { assert_eq ! (treap . nth (i) , & (i * 2)) ; } } } } pub mod union_find { pub struct UnionFind { parent : Vec < usize > , sizes : Vec < usize > , size : usize , } impl UnionFind { pub fn new (n : usize) -> UnionFind { UnionFind { parent : (0 .. n) . map (| i | i) . collect :: < Vec < usize > > () , sizes : vec ! [1 ; n] , size : n , } } pub fn find (& mut self , x : usize) -> usize { if x == self . parent [x] { x } else { let px = self . parent [x] ; self . parent [x] = self . find (px) ; self . parent [x] } } pub fn unite (& mut self , x : usize , y : usize) -> bool { let parent_x = self . find (x) ; let parent_y = self . find (y) ; if parent_x == parent_y { return false ; } let (large , small) = if self . sizes [parent_x] < self . sizes [parent_y] { (parent_y , parent_x) } else { (parent_x , parent_y) } ; self . parent [small] = large ; self . sizes [large] += self . sizes [small] ; self . sizes [small] = 0 ; self . size -= 1 ; true } } # [cfg (test)] mod test { use super :: * ; use crate :: utils :: test_helper :: Tester ; # [doc = " Solve http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A"] # [test] fn solve_dsl_1_a () { let tester = Tester :: new ("./assets/DSL_1_A/in/" , "./assets/DSL_1_A/out/") ; tester . test_solution (| sc | { let n = sc . read () ; let q = sc . read () ; let mut uf = UnionFind :: new (n) ; for _ in 0 .. q { let com : usize = sc . read () ; let x = sc . read () ; let y = sc . read () ; if com == 0 { uf . unite (x , y) ; } else { let ans = if uf . find (x) == uf . find (y) { 1 } else { 0 } ; sc . write (format ! ("{}\n" , ans)) ; } } }) ; } } } } # [doc = " Mathematical algorithms."] pub mod math { pub mod chinese_remainder_theorem { pub fn extended_gcd (a : i64 , b : i64 , p : & mut i64 , q : & mut i64) -> i64 { if b == 0 { * p = 1 ; * q = 0 ; a } else { let d = extended_gcd (b , a % b , q , p) ; * q -= a / b * * p ; d } } pub fn chinese_remainder_theorem (b : & [i64] , modulo : & [i64]) -> Option < (i64 , i64) > { let (mut result , mut m) = (0 , 1) ; for i in 0 .. b . len () { let (mut p , mut q) = (0 , 0) ; let d = extended_gcd (m , modulo [i] , & mut p , & mut q) ; if (b [i] - result) % d != 0 { return None ; } let tmp = ((b [i] - result) / d * p) % (modulo [i] / d) ; result += m * tmp ; m *= modulo [i] / d ; } Some (((result % m + m) % m , m)) } # [cfg (test)] mod tests { use super :: * ; use rand ; use rand :: Rng ; # [test] fn test_crt () { let mut rng = rand :: thread_rng () ; let n = 10 ; let max_m = 100 ; for _ in 0 .. 1000 { let ans = rng . gen :: < u32 > () as i64 ; let mut b = vec ! [0 ; n] ; let mut m = vec ! [0 ; n] ; for i in 0 .. n { m [i] = rng . gen :: < u8 > () as i64 ; m [i] %= max_m ; m [i] += 1 ; b [i] = ans % m [i] ; } let (a , _) = chinese_remainder_theorem (& b , & m) . unwrap () ; for i in 0 .. n { assert_eq ! (a % m [i] , b [i]) ; } } } } } pub mod combination { pub struct Combination { fact : Vec < usize > , inv_fact : Vec < usize > , modulo : usize , } impl Combination { pub fn new (max : usize , modulo : usize) -> Self { let mut inv = vec ! [0 ; max + 1] ; let mut fact = vec ! [0 ; max + 1] ; let mut inv_fact = vec ! [0 ; max + 1] ; inv [1] = 1 ; for i in 2 .. (max + 1) { inv [i] = inv [modulo % i] * (modulo - modulo / i) % modulo ; } fact [0] = 1 ; inv_fact [0] = 1 ; for i in 0 .. max { fact [i + 1] = fact [i] * (i + 1) % modulo ; } for i in 0 .. max { inv_fact [i + 1] = inv_fact [i] * inv [i + 1] % modulo ; } Self { fact , inv_fact , modulo , } } pub fn get (& self , x : usize , y : usize) -> usize { assert ! (x >= y) ; self . fact [x] * self . inv_fact [y] % self . modulo * self . inv_fact [x - y] % self . modulo } pub fn h (& self , n : usize , r : usize) -> usize { self . get (n + r - 1 , r) } } # [cfg (test)] mod test { use super :: * ; fn gcd (a : usize , b : usize) -> usize { if b == 0 { a } else { gcd (b , a % b) } } # [test] fn random_combination () { let modulo = 1_000_000_007 ; for n in 100 .. 200 { let comb = Combination :: new (n , modulo) ; for m in 0 .. (n + 1) { let mut upper = (0 .. m) . map (| i | n - i) . collect :: < Vec < _ > > () ; for i in 0 .. m { let mut divisor = i + 1 ; for j in 0 .. (i + 1) { if divisor == 1 { break ; } let g = gcd (divisor , upper [j]) ; upper [j] /= g ; divisor /= g ; } } let mut check = 1 ; for u in & upper { check = (check * u) % modulo ; } assert_eq ! (comb . get (n , m) , check) ; } } } } } pub mod cumulative_sum { pub struct CumulativeSum < T > (Vec < Vec < T > >) ; impl < T > CumulativeSum < T > where T : Copy + std :: ops :: Add < Output = T > + std :: ops :: Sub < Output = T > , { pub fn new (a : & [Vec < T >] , init : T) -> CumulativeSum < T > { assert ! (! a . is_empty ()) ; let h = a . len () ; let w = a [0] . len () ; let mut sum = vec ! [vec ! [init ; w + 1] ; h + 1] ; for i in 0 .. h { for j in 0 .. w { sum [i + 1] [j + 1] = a [i] [j] + sum [i] [j + 1] + sum [i + 1] [j] - sum [i] [j] ; } } CumulativeSum (sum) } pub fn get_sum (& self , h_range : std :: ops :: Range < usize > , w_range : std :: ops :: Range < usize >) -> T { assert ! (h_range . end <= self . 0 . len ()) ; assert ! (w_range . end <= self . 0 [0] . len ()) ; self . 0 [h_range . end] [w_range . end] + self . 0 [h_range . start] [w_range . start] - self . 0 [h_range . start] [w_range . end] - self . 0 [h_range . end] [w_range . start] } } # [cfg (test)] mod test { use super :: * ; use rand :: distributions :: Uniform ; use rand :: Rng ; # [test] fn random_array () { let h = 30 ; let w = 20 ; let mut rng = rand :: thread_rng () ; for _ in 0 .. 10 { let mut array = vec ! [vec ! [0 ; w] ; h] ; for i in 0 .. h { for j in 0 .. w { array [i] [j] = rng . sample (Uniform :: from (10 .. 10000)) ; } } let sum = CumulativeSum :: new (& array , 0) ; for from_i in 0 .. h { for to_i in (from_i + 1) ..= h { for from_j in 0 .. w { for to_j in (from_j + 1) ..= w { let mut check = 0 ; for i in from_i .. to_i { for j in from_j .. to_j { check += array [i] [j] ; } } assert_eq ! (check , sum . get_sum (from_i .. to_i , from_j .. to_j)) ; } } } } } } } } pub mod floor_sum { pub fn floor_sum (n : i64 , m : i64 , mut a : i64 , mut b : i64) -> i64 { let mut ans = 0 ; if a >= m { ans += (n - 1) * n * (a / m) / 2 ; a %= m ; } if b >= m { ans += n * (b / m) ; b %= m ; } let y_max = (a * n + b) / m ; let x_max = y_max * m - b ; if y_max == 0 { ans } else { ans += (n - (x_max + a - 1) / a) * y_max ; ans += floor_sum (y_max , a , m , (a - x_max % a) % a) ; ans } } # [cfg (test)] mod tests { use super :: * ; # [test] fn test_floor_sum () { assert_eq ! (3 , floor_sum (4 , 10 , 6 , 3)) ; assert_eq ! (13 , floor_sum (6 , 5 , 4 , 3)) ; assert_eq ! (0 , floor_sum (1 , 1 , 0 , 0)) ; assert_eq ! (314095480 , floor_sum (31415 , 92653 , 58979 , 32384)) ; assert_eq ! (499999999500000000 , floor_sum (1000000000 , 1000000000 , 999999999 , 999999999)) ; } } } pub mod lagrange_interpolation { pub fn lagrange_interpolation < T > (xs : & [T] , ys : & [T] , one : T , zero : T) -> Vec < T > where T : Clone + Copy + std :: ops :: Sub < Output = T > + std :: ops :: Mul < Output = T > + std :: ops :: Div < Output = T > + std :: ops :: AddAssign + std :: ops :: SubAssign + std :: ops :: MulAssign , { let n = xs . len () ; let mut all_c = vec ! [zero ; n + 1] ; all_c [0] = one ; for & x in xs . iter () { let mut next = vec ! [zero ; n + 1] ; next [1 .. (n + 1)] . clone_from_slice (& all_c [.. n]) ; for j in 0 .. n { next [j] -= x * all_c [j] ; } all_c = next ; } let mut c = vec ! [zero ; n] ; for i in 0 .. n { let mut qi = one ; for j in 0 .. n { if i == j { continue ; } qi *= xs [i] - xs [j] ; } let ri = ys [i] / qi ; let mut tmp_c = all_c . clone () ; for j in (0 .. n) . rev () { c [j] += ri * tmp_c [j + 1] ; let next_c = tmp_c [j + 1] * xs [i] ; tmp_c [j] += next_c ; } } c } # [cfg (test)] mod tests { use super :: * ; use crate :: math :: mod_int :: mod_int :: ModInt ; use rand :: { thread_rng , Rng } ; const MOD : u64 = 1e9 as u64 + 7 ; # [test] fn test_lagrange_interpolation () { let mut rng = thread_rng () ; let n = 500 ; for _ in 0 .. 10 { let mut xs = vec ! [] ; let mut ys = vec ! [] ; for _ in 0 .. n { xs . push (ModInt :: new (rng . gen () , MOD)) ; ys . push (ModInt :: new (rng . gen () , MOD)) ; } let c = lagrange_interpolation (& xs , & ys , ModInt :: new (1 , MOD) , ModInt :: new (0 , MOD)) ; for i in 0 .. n { let mut y = ModInt :: new (0 , MOD) ; let x = xs [i] ; for i in 0 .. n { y += x . pow (i as u64) * c [i] ; } assert_eq ! (y . value () , ys [i] . value ()) ; } } } } } pub mod max_rectangle { pub mod max_rectangle { use std :: cmp ; use std :: collections :: VecDeque ; fn calc (hist : & [usize]) -> usize { let n = hist . len () ; let mut ans = 0 ; let mut q : VecDeque < (usize , usize) > = VecDeque :: new () ; for (i , & hist) in hist . iter () . enumerate () { let mut reachable_min = i ; while let Some ((pos , height)) = q . pop_front () { if height <= hist { q . push_front ((pos , height)) ; break ; } reachable_min = pos ; ans = cmp :: max (ans , (i - reachable_min) * height) ; } if q . is_empty () || q . iter () . next () . unwrap () . 1 < hist { q . push_front ((reachable_min , hist)) ; } } while let Some ((pos , height)) = q . pop_front () { ans = cmp :: max (ans , (n - pos) * height) ; } ans } pub fn maximize (map : & [Vec < bool >]) -> usize { let h = map . len () ; let w = map [0] . len () ; let mut hist = vec ! [vec ! [0 ; w] ; h] ; for i in 0 .. h { for j in 0 .. w { if ! map [i] [j] { continue ; } if i == 0 { hist [i] [j] = 1 ; } else { hist [i] [j] = hist [i - 1] [j] + 1 ; } } } let mut ans = 0 ; for hist in hist . iter () { ans = cmp :: max (ans , calc (hist)) ; } ans } } # [cfg (test)] mod test { use super :: * ; use crate :: utils :: test_helper :: Tester ; # [test] fn solve_dpl_3_b () { let tester = Tester :: new ("./assets/DPL_3_B/in/" , "./assets/DPL_3_B/out/") ; tester . test_solution (| sc | { let h : usize = sc . read () ; let w : usize = sc . read () ; let mut c = vec ! [vec ! [false ; w] ; h] ; for i in 0 .. h { for j in 0 .. w { c [i] [j] = sc . read :: < usize > () == 0 ; } } let ans = max_rectangle :: maximize (& c) ; sc . write (format ! ("{}\n" , ans)) ; }) ; } } } pub mod mod_int { pub mod mod_int { use std :: ops :: { Add , AddAssign , BitAnd , Div , DivAssign , Mul , MulAssign , RemAssign , ShrAssign , Sub , SubAssign , } ; pub struct ModInt < T > { v : T , m : T , } impl < T > ModInt < T > where T : Copy , { pub fn value (& self) -> T { self . v } pub fn modulo (& self) -> T { self . m } } impl < T > ModInt < T > { fn new_unchecked (v : T , modulo : T) -> Self { Self { v , m : modulo } } } impl < T > ModInt < T > where T : Copy + RemAssign + PartialOrd , { pub fn new (mut v : T , modulo : T) -> Self { if v >= modulo { v %= modulo ; } Self :: new_unchecked (v , modulo) } } impl < T > ModInt < T > where T : Copy + Sub < Output = T > + ShrAssign + BitAnd < Output = T > + PartialEq + PartialOrd + Div < Output = T > + RemAssign , ModInt < T > : MulAssign , { pub fn pow (self , e : T) -> Self { let zero = self . modulo () - self . modulo () ; let one = self . modulo () / self . modulo () ; let mut e = e ; let mut result = Self :: new_unchecked (one , self . modulo ()) ; let mut cur = self ; while e > zero { if e & one == one { result *= cur ; } e >>= one ; cur *= cur ; } result } } impl < T > Copy for ModInt < T > where T : Copy { } impl < T > Clone for ModInt < T > where T : Copy , { fn clone (& self) -> Self { Self :: new_unchecked (self . value () , self . modulo ()) } } impl < T > Add < T > for ModInt < T > where T : AddAssign + SubAssign + RemAssign + Copy + PartialOrd , { type Output = Self ; fn add (self , mut rhs : T) -> Self :: Output { if rhs >= self . modulo () { rhs %= self . modulo () ; } rhs += self . value () ; if rhs >= self . modulo () { rhs -= self . modulo () ; } Self :: new_unchecked (rhs , self . modulo ()) } } impl < T > Sub < T > for ModInt < T > where T : AddAssign + SubAssign + RemAssign + Copy + PartialOrd , { type Output = Self ; fn sub (self , mut rhs : T) -> Self :: Output { if rhs >= self . modulo () { rhs %= self . modulo () ; } let mut result = self . value () ; result += self . modulo () ; result -= rhs ; if result >= self . modulo () { result -= self . modulo () ; } Self :: new_unchecked (result , self . modulo ()) } } impl < T > Mul < T > for ModInt < T > where T : MulAssign + RemAssign + Copy + PartialOrd , { type Output = Self ; fn mul (self , mut rhs : T) -> Self :: Output { if rhs >= self . modulo () { rhs %= self . modulo () ; } rhs *= self . value () ; rhs %= self . modulo () ; Self :: new_unchecked (rhs , self . modulo ()) } } impl < T > Add < ModInt < T > > for ModInt < T > where T : Copy , ModInt < T > : Add < T , Output = ModInt < T > > , { type Output = Self ; fn add (self , rhs : ModInt < T >) -> Self :: Output { self + rhs . value () } } impl < T > Sub < ModInt < T > > for ModInt < T > where T : Copy , ModInt < T > : Sub < T , Output = ModInt < T > > , { type Output = Self ; fn sub (self , rhs : ModInt < T >) -> Self :: Output { self - rhs . value () } } impl < T > Mul < ModInt < T > > for ModInt < T > where T : Copy , ModInt < T > : Mul < T , Output = ModInt < T > > , { type Output = Self ; fn mul (self , rhs : ModInt < T >) -> Self :: Output { self * rhs . value () } } impl < T > Div < ModInt < T > > for ModInt < T > where T : Copy , ModInt < T > : Div < T , Output = ModInt < T > > , { type Output = Self ; fn div (self , rhs : ModInt < T >) -> Self :: Output { self / rhs . value () } } impl < T > AddAssign < T > for ModInt < T > where T : Copy , ModInt < T > : Add < T , Output = ModInt < T > > , { fn add_assign (& mut self , other : T) { * self = * self + other ; } } impl < T > AddAssign < ModInt < T > > for ModInt < T > where T : Copy , ModInt < T > : Add < ModInt < T > , Output = ModInt < T > > , { fn add_assign (& mut self , other : ModInt < T >) { * self = * self + other ; } } impl < T > SubAssign < T > for ModInt < T > where T : Copy , ModInt < T > : Sub < T , Output = ModInt < T > > , { fn sub_assign (& mut self , other : T) { * self = * self - other ; } } impl < T > SubAssign < ModInt < T > > for ModInt < T > where T : Copy , ModInt < T > : Sub < ModInt < T > , Output = ModInt < T > > , { fn sub_assign (& mut self , other : ModInt < T >) { * self = * self - other ; } } impl < T > DivAssign < T > for ModInt < T > where T : Copy , ModInt < T > : Div < T , Output = ModInt < T > > , { fn div_assign (& mut self , rhs : T) { * self = * self / rhs } } impl < T > DivAssign < ModInt < T > > for ModInt < T > where T : Copy , ModInt < T > : Div < ModInt < T > , Output = ModInt < T > > , { fn div_assign (& mut self , rhs : ModInt < T >) { * self = * self / rhs } } impl < T > MulAssign < T > for ModInt < T > where T : Copy , ModInt < T > : Mul < T , Output = ModInt < T > > , { fn mul_assign (& mut self , rhs : T) { * self = * self * rhs ; } } impl < T > MulAssign < ModInt < T > > for ModInt < T > where T : Copy , ModInt < T > : Mul < ModInt < T > , Output = ModInt < T > > , { fn mul_assign (& mut self , rhs : ModInt < T >) { * self = * self * rhs ; } } impl < T > Div < T > for ModInt < T > where T : Copy + Add < Output = T > + Sub < Output = T > + Div < Output = T > + BitAnd < Output = T > + PartialEq + PartialOrd + ShrAssign + RemAssign + MulAssign , { type Output = Self ; fn div (self , mut rhs : T) -> Self :: Output { if rhs >= self . modulo () { rhs %= self . modulo () ; } let one = self . modulo () / self . modulo () ; let two = one + one ; self * Self :: new_unchecked (rhs , self . modulo ()) . pow (self . modulo () - two) } } } # [cfg (test)] mod test { use super :: mod_int :: * ; use rand :: distributions :: Uniform ; use rand :: Rng ; const MOD : u64 = 1_000_000_007 ; # [test] fn random_add_sub () { let mut rng = rand :: thread_rng () ; for _ in 0 .. 1000 { let x : u64 = rng . sample (Uniform :: from (0 .. MOD)) ; let y : u64 = rng . sample (Uniform :: from (0 .. MOD)) ; let mx = ModInt :: new (x , MOD) ; let my = ModInt :: new (y , MOD) ; assert_eq ! ((mx + my) . value () , (x + y) % MOD) ; assert_eq ! ((mx + y) . value () , (x + y) % MOD) ; assert_eq ! ((mx - my) . value () , (x + MOD - y) % MOD) ; assert_eq ! ((mx - y) . value () , (x + MOD - y) % MOD) ; let mut x = x ; let mut mx = mx ; x += y ; mx += my ; assert_eq ! (mx . value () , x % MOD) ; mx += y ; x += y ; assert_eq ! (mx . value () , x % MOD) ; mx -= my ; x = (x + MOD - y % MOD) % MOD ; assert_eq ! (mx . value () , x) ; mx -= y ; x = (x + MOD - y % MOD) % MOD ; assert_eq ! (mx . value () , x) ; } } # [test] fn random_mul () { let mut rng = rand :: thread_rng () ; for _ in 0 .. 1000 { let x : u64 = rng . sample (Uniform :: from (0 .. MOD)) ; let y : u64 = rng . sample (Uniform :: from (0 .. MOD)) ; let mx = ModInt :: new (x , MOD) ; let my = ModInt :: new (y , MOD) ; assert_eq ! ((mx * my) . value () , (x * y) % MOD) ; assert_eq ! ((mx * y) . value () , (x * y) % MOD) ; } } # [test] fn zero_test () { let a = ModInt :: new (1_000_000_000 , MOD) ; let b = ModInt :: new (7 , MOD) ; let c = a + b ; assert_eq ! (c . value () , 0) ; } # [test] fn pow_test () { let a = ModInt :: new (3 , MOD) ; let a = a . pow (4) ; assert_eq ! (a . value () , 81) ; } # [test] fn div_test () { for i in 1 .. 100000 { let mut a = ModInt :: new (1 , MOD) ; a /= i ; a *= i ; assert_eq ! (a . value () , 1) ; } } # [test] fn edge_cases () { let a = ModInt :: new (1_000_000_000 , MOD) * std :: u64 :: MAX ; assert_eq ! (a . value () , 923591986) ; let mut a = ModInt :: new (1_000_000_000 , MOD) ; a *= std :: u64 :: MAX ; assert_eq ! (a . value () , 923591986) ; let a = ModInt :: new (1_000_000_000 , MOD) + std :: u64 :: MAX ; assert_eq ! (a . value () , 582344000) ; let mut a = ModInt :: new (1_000_000_000 , MOD) ; a += std :: u64 :: MAX ; assert_eq ! (a . value () , 582344000) ; let a = ModInt :: new (1_000_000_000 , MOD) - std :: u64 :: MAX ; assert_eq ! (a . value () , 417655993) ; let mut a = ModInt :: new (1_000_000_000 , MOD) ; a -= std :: u64 :: MAX ; assert_eq ! (a . value () , 417655993) ; let a = ModInt :: new (1_000_000_000 , MOD) / std :: u64 :: MAX ; assert_eq ! (a . value () , 605455209) ; let mut a = ModInt :: new (1_000_000_000 , MOD) ; a /= std :: u64 :: MAX ; assert_eq ! (a . value () , 605455209) ; } # [test] fn overflow_guard () { let a = ModInt :: new (MOD * 10 , MOD) ; assert_eq ! (a . value () , 0) ; } } } pub mod next_permutation { pub trait NextPermutation { fn next_permutation (& mut self) -> bool ; } impl < T > NextPermutation for [T] where T : PartialOrd , { fn next_permutation (& mut self) -> bool { if self . len () < 2 { return false ; } let mut i = self . len () - 1 ; while i > 0 && self [i - 1] >= self [i] { i -= 1 ; } if i == 0 { return false ; } let mut j = self . len () - 1 ; while j >= i && self [j] <= self [i - 1] { j -= 1 ; } self . swap (j , i - 1) ; self [i ..] . reverse () ; true } } # [cfg (test)] mod tests { use super :: NextPermutation ; use std :: collections :: BTreeSet ; # [test] fn test_next_permutation () { let mut x = vec ! [1 , 2 , 3 , 4 , 5] ; let mut set = BTreeSet :: new () ; let mut count = 0 ; while x . next_permutation () { count += 1 ; set . insert (x . clone ()) ; } assert_eq ! (count + 1 , 5 * 4 * 3 * 2) ; assert_eq ! (set . len () , count) ; } } } } # [doc = " Geometry algorithms."] pub mod geometry { pub mod circle { pub fn cc_intersect ((p1 , r1) : (Point , f64) , (p2 , r2) : (Point , f64)) -> Vec < Point > { let dist = (p1 - p2) . abs () ; if dist > r1 + r2 { return Vec :: new () ; } let rc = (dist * dist + r1 * r1 - r2 * r2) / (2. * dist) ; let rs = (r1 * r1 - rc * rc) . sqrt () ; let diff = (p2 - p1) / dist ; vec ! [p1 + diff * Point (rc , rs) , p1 + diff * Point (rc , - rs)] } # [derive (Copy , Clone)] pub struct Point (f64 , f64) ; impl Point { fn abs (self) -> f64 { let x = self . 0 ; let y = self . 1 ; (x * x + y * y) . sqrt () } } impl :: std :: ops :: Add < Point > for Point { type Output = Point ; fn add (self , rhs : Point) -> Point { Point (self . 0 + rhs . 0 , self . 1 + rhs . 1) } } impl :: std :: ops :: Sub < Point > for Point { type Output = Point ; fn sub (self , rhs : Point) -> Point { Point (self . 0 - rhs . 0 , self . 1 - rhs . 1) } } impl :: std :: ops :: Div < f64 > for Point { type Output = Point ; fn div (self , rhs : f64) -> Point { Point (self . 0 / rhs , self . 1 / rhs) } } impl :: std :: ops :: Mul < Point > for Point { type Output = Point ; fn mul (self , rhs : Point) -> Point { let Point (x1 , y1) = self ; let Point (x2 , y2) = rhs ; Point (x1 * x2 - y1 * y2 , x1 * y2 + y1 * x2) } } # [cfg (test)] mod tests { use super :: * ; use crate :: utils :: test_helper :: Tester ; # [test] fn solve_cgl_7_e () { let tester = Tester :: new ("./assets/CGL_7_E/in/" , "./assets/CGL_7_E/out/") ; tester . test_solution_with (| sc | { let c1 = (Point (sc . read () , sc . read ()) , sc . read ()) ; let c2 = (Point (sc . read () , sc . read ()) , sc . read ()) ; let mut points = cc_intersect (c1 , c2) . into_iter () . map (| Point (x , y) | (x , y)) . collect :: < Vec < _ > > () ; if points [0] > points [1] { points . swap (0 , 1) ; } sc . write (format ! ("{} {} {} {}\n" , points [0] . 0 , points [0] . 1 , points [1] . 0 , points [1] . 1)) ; } , | expected , actual | { assert ! ((expected . read ::< f64 > () - actual . read ::< f64 > ()) . abs () < 1e-6) ; assert ! ((expected . read ::< f64 > () - actual . read ::< f64 > ()) . abs () < 1e-6) ; assert ! ((expected . read ::< f64 > () - actual . read ::< f64 > ()) . abs () < 1e-6) ; assert ! ((expected . read ::< f64 > () - actual . read ::< f64 > ()) . abs () < 1e-6) ; } ,) ; } } } pub mod convex_hull { pub fn extract_convex_hull (points : & [Point] , contain_on_segment : bool) -> Vec < usize > { let n = points . len () ; if n <= 1 { return vec ! [0] ; } let mut ps : Vec < usize > = (0 .. n) . collect () ; ps . sort_by (| & a , & b | { if (points [a] . x - points [b] . x) . abs () < std :: f64 :: EPSILON { points [a] . y . partial_cmp (& points [b] . y) . unwrap () } else { points [a] . x . partial_cmp (& points [b] . x) . unwrap () } }) ; let mut qs : Vec < usize > = Vec :: new () ; for & i in & ps { while qs . len () > 1 { let k = qs . len () ; let det = (points [qs [k - 1]] - points [qs [k - 2]]) . det (& (points [i] - points [qs [k - 1]])) ; if det < 0.0 || (det <= 0.0 && ! contain_on_segment) { qs . pop () ; } else { break ; } } qs . push (i) ; } let t = qs . len () ; for i in (0 .. (n - 1)) . rev () { let i = ps [i] ; while qs . len () > t { let k = qs . len () ; let det = (points [qs [k - 1]] - points [qs [k - 2]]) . det (& (points [i] - points [qs [k - 1]])) ; if det < 0.0 || (det <= 0.0 && ! contain_on_segment) { qs . pop () ; } else { break ; } } qs . push (i) ; } qs . pop () ; qs } # [derive (Debug , Copy , Clone)] pub struct Point { x : f64 , y : f64 , } impl std :: ops :: Sub for Point { type Output = Point ; fn sub (self , other : Point) -> Point { Point { x : self . x - other . x , y : self . y - other . y , } } } impl Point { pub fn det (& self , other : & Point) -> f64 { self . x * other . y - self . y * other . x } } # [cfg (test)] mod test { use super :: * ; use crate :: utils :: test_helper :: Tester ; # [doc = " Solve http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_A"] # [test] fn solve_cgl_4_a () { let tester = Tester :: new ("./assets/CGL_4_A/in/" , "./assets/CGL_4_A/out/") ; tester . test_solution (| sc | { let n : usize = sc . read () ; let mut points = Vec :: new () ; for _ in 0 .. n { let x : f64 = sc . read () ; let y : f64 = sc . read () ; points . push (Point { x , y }) ; } let convex_hull = extract_convex_hull (& points , true) ; sc . write (format ! ("{}\n" , convex_hull . len ())) ; let n = convex_hull . len () ; let mut start = 0 ; for i in 0 .. n { if points [convex_hull [i]] . y < points [convex_hull [start]] . y || (points [convex_hull [i]] . y == points [convex_hull [start]] . y && points [convex_hull [i]] . x < points [convex_hull [start]] . x) { start = i ; } } for i in 0 .. n { let i = (i + start) % n ; let i = convex_hull [i] ; sc . write (format ! ("{} {}\n" , points [i] . x , points [i] . y)) ; } }) ; } } } pub mod minimum_bounding_circle { pub mod minimum_bounding_circle { pub fn make_circle (ps : & [Point < f64 >]) -> (Point < f64 > , f64) { let n = ps . len () ; assert ! (n >= 2) ; let mut c = make_circle2 (ps [0] , ps [1]) ; for i in 2 .. n { if is_included (ps [i] , c) { continue ; } c = make_circle2 (ps [0] , ps [i]) ; for j in 1 .. i { if is_included (ps [j] , c) { continue ; } c = make_circle2 (ps [i] , ps [j]) ; for k in 0 .. j { if is_included (ps [k] , c) { continue ; } c = make_circle3 (ps [i] , ps [j] , ps [k]) ; } } } c } fn make_circle3 (a : Point < f64 > , b : Point < f64 > , c : Point < f64 >) -> (Point < f64 > , f64) { let ea = (b - c) . norm () ; let eb = (c - a) . norm () ; let ec = (a - b) . norm () ; let s = (b - a) . det (& (c - a)) ; let center = (a * ea * (eb + ec - ea) + b * eb * (ec + ea - eb) + c * ec * (ea + eb - ec)) / (s * s * 4.0) ; let r2 = (center - a) . norm () ; (center , r2) } fn make_circle2 (a : Point < f64 > , b : Point < f64 >) -> (Point < f64 > , f64) { let c = (a + b) / 2.0 ; let r2 = (a - c) . norm () ; (c , r2) } fn is_included (a : Point < f64 > , circle : (Point < f64 > , f64)) -> bool { let (center , r2) = circle ; (a - center) . norm () <= r2 } pub struct Point < T > { pub x : T , pub y : T , } impl < T > Copy for Point < T > where T : Copy { } impl < T > Clone for Point < T > where T : Clone , { fn clone (& self) -> Point < T > { Point { x : self . x . clone () , y : self . y . clone () , } } } impl < T > std :: ops :: Sub for Point < T > where T : std :: ops :: Sub < Output = T > , { type Output = Point < T > ; fn sub (self , other : Point < T >) -> Point < T > { Point { x : self . x - other . x , y : self . y - other . y , } } } impl < T > std :: ops :: Mul < T > for Point < T > where T : Copy + std :: ops :: Mul < Output = T > , { type Output = Point < T > ; fn mul (self , rhs : T) -> Point < T > { Point { x : self . x * rhs , y : self . y * rhs , } } } impl < T > std :: ops :: Div < T > for Point < T > where T : Copy + std :: ops :: Div < Output = T > , { type Output = Point < T > ; fn div (self , rhs : T) -> Point < T > { Point { x : self . x / rhs , y : self . y / rhs , } } } impl < T > std :: ops :: Add < Point < T > > for Point < T > where T : std :: ops :: Add < Output = T > , { type Output = Point < T > ; fn add (self , rhs : Point < T >) -> Point < T > { Point { x : self . x + rhs . x , y : self . y + rhs . y , } } } impl < T > Point < T > where T : Copy + std :: ops :: Mul < Output = T > + std :: ops :: Sub < Output = T > + std :: ops :: Add < Output = T > , { pub fn det (& self , other : & Point < T >) -> T { self . x * other . y - self . y * other . x } pub fn norm (& self) -> T { self . x * self . x + self . y * self . y } } } # [cfg (test)] mod tests { use super :: minimum_bounding_circle :: * ; use crate :: utils :: test_helper :: Tester ; # [test] fn solve_aoj2423 () { let tester = Tester :: new ("./assets/AOJ2423/in/" , "./assets/AOJ2423/out/") ; tester . test_solution (| sc | { let circles : usize = sc . read () ; let people : usize = sc . read () ; let rs : Vec < f64 > = sc . vec (circles) ; let mut people_r2 = vec ! [0.0 ; people] ; let mut people_list = vec ! [] ; for i in 0 .. people { let n : usize = sc . read () ; let mut ps = vec ! [] ; for _ in 0 .. n { let x : f64 = sc . read () ; let y : f64 = sc . read () ; ps . push (Point { x , y }) ; } let (_ , r2) = make_circle (& ps) ; people_list . push ((r2 , i)) ; people_r2 [i] = r2 ; } let mut circle_list = rs . iter () . enumerate () . map (| (i , & r) | (r , i)) . collect :: < Vec < _ > > () ; circle_list . sort_by (| a , b | a . 0 . partial_cmp (& b . 0) . unwrap ()) ; people_list . sort_by (| a , b | a . 0 . partial_cmp (& b . 0) . unwrap ()) ; let mut ans = vec ! [0 ; people] ; for _ in 0 .. people { let mut circle_buf = 0 ; let mut people_buf = people_list . len () ; for p_pos in (0 .. people_list . len ()) . rev () { for c_pos in (0 .. (circle_list . len () - circle_buf)) . rev () { if circle_list [c_pos] . 0 * circle_list [c_pos] . 0 >= people_list [p_pos] . 0 { circle_buf += 1 ; } else { break ; } } if people_list . len () - p_pos > circle_buf { sc . write ("NG\n") ; return ; } else if people_list . len () - p_pos == circle_buf { people_buf = people_list . len () - p_pos ; break ; } } let youngest_people = people_list . iter () . rev () . take (people_buf) . map (| p | p . 1) . min () . unwrap () ; let youngest_circle = circle_list . iter () . rev () . take (circle_buf) . map (| c | c . 1) . filter (| & i | rs [i] * rs [i] >= people_r2 [youngest_people]) . min () . unwrap () ; ans [youngest_people] = youngest_circle ; people_list = people_list . into_iter () . filter (| p | p . 1 != youngest_people) . collect :: < Vec < _ > > () ; circle_list = circle_list . into_iter () . filter (| c | c . 1 != youngest_circle) . collect :: < Vec < _ > > () ; } for i in ans . into_iter () { sc . write (format ! ("{}\n" , i + 1)) ; } }) ; } } } } # [doc = " Utilities for tests, stdin, and so on."] pub mod utils { # [doc = " Functions to test this library with contest-style IO files."] # [cfg (test)] pub (crate) mod test_helper { use crate :: utils :: scanner :: IO ; use std :: fs ; use std :: fs :: File ; use std :: io :: Read ; use std :: str ; pub (crate) struct Tester { input : Vec < (String , Vec < u8 >) > , output : Vec < (String , Vec < u8 >) > , } impl Tester { pub (crate) fn new (input_directory : & str , output_directory : & str) -> Tester { let input = read_from_directory (input_directory) ; let output = read_from_directory (output_directory) ; Tester { input , output } } pub (crate) fn test_solution < F > (self , solution : F) where F : Fn (& mut IO < & [u8] , & mut Vec < u8 > >) , { for ((input_label , input) , (output_label , output)) in self . input . into_iter () . zip (self . output) { eprintln ! ("Testing {} {}" , input_label , output_label) ; let mut writer = vec ! [] ; { let mut sc = IO :: new (& input [..] , & mut writer) ; solution (& mut sc) ; } assert_eq ! (writer , output) ; } } pub (crate) fn test_solution_with < F1 , F2 > (self , solution : F1 , assertion : F2) where F1 : Fn (& mut IO < & [u8] , & mut Vec < u8 > >) , F2 : Fn (& mut IO < & [u8] , & mut Vec < u8 > > , & mut IO < & [u8] , & mut Vec < u8 > >) , { for ((input_label , input) , (output_label , output)) in self . input . into_iter () . zip (self . output) { eprintln ! ("Testing {} {}" , input_label , output_label) ; let mut writer = vec ! [] ; { let mut sc = IO :: new (& input [..] , & mut writer) ; solution (& mut sc) ; } let mut actual_writer = vec ! [] ; let mut expected_writer = vec ! [] ; let mut actual = IO :: new (& writer [..] , & mut actual_writer) ; let mut expected = IO :: new (& output [..] , & mut expected_writer) ; assertion (& mut expected , & mut actual) ; } } } fn read_file (filepath : & str) -> Vec < u8 > { let mut file = File :: open (filepath) . unwrap () ; let mut buf = Vec :: new () ; file . read_to_end (& mut buf) . unwrap () ; buf } fn read_from_directory (directory_path : & str) -> Vec < (String , Vec < u8 >) > { let mut filenames : Vec < String > = fs :: read_dir (directory_path) . unwrap () . map (| result | result . unwrap () . path () . display () . to_string ()) . collect () ; filenames . sort () ; filenames . into_iter () . map (| file | { let data = read_file (& file) ; (file , data) }) . collect () } } pub mod scanner { pub struct IO < R , W : std :: io :: Write > (R , std :: io :: BufWriter < W >) ; impl < R : std :: io :: Read , W : std :: io :: Write > IO < R , W > { pub fn new (r : R , w : W) -> IO < R , W > { IO (r , std :: io :: BufWriter :: new (w)) } pub fn write < S : ToString > (& mut self , s : S) { use std :: io :: Write ; self . 1 . write_all (s . to_string () . as_bytes ()) . unwrap () ; } pub fn read < T : std :: str :: FromStr > (& mut self) -> T { use std :: io :: Read ; let buf = self . 0 . by_ref () . bytes () . map (| b | b . unwrap ()) . skip_while (| & b | b == b' ' || b == b'\n' || b == b'\r' || b == b'\t') . take_while (| & b | b != b' ' && b != b'\n' && b != b'\r' && b != b'\t') . collect :: < Vec < _ > > () ; unsafe { std :: str :: from_utf8_unchecked (& buf) } . parse () . ok () . expect ("Parse error.") } pub fn vec < T : std :: str :: FromStr > (& mut self , n : usize) -> Vec < T > { (0 .. n) . map (| _ | self . read ()) . collect () } pub fn chars (& mut self) -> Vec < char > { self . read :: < String > () . chars () . collect () } } # [cfg (test)] mod tests { use super :: * ; # [test] fn test_io () { let input = br"10
        1 2 3 4 5 6 7 8 9 10
        abcde fghij
        
        3.14 -1592
        no_empty_line" ; let mut sc = IO :: new (& input [..] , Vec :: new ()) ; let n : usize = sc . read () ; assert_eq ! (n , 10) ; let a : Vec < u64 > = sc . vec (n) ; assert_eq ! (& a , & [1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10]) ; let s = sc . chars () ; let t = sc . chars () ; assert_eq ! (& s , & ['a' , 'b' , 'c' , 'd' , 'e']) ; assert_eq ! (& t , & ['f' , 'g' , 'h' , 'i' , 'j']) ; let f : f64 = sc . read () ; assert_eq ! (f , 3.14) ; let neg : i64 = sc . read () ; assert_eq ! (neg , - 1592) ; let s = sc . read :: < String > () ; assert_eq ! (& s , "no_empty_line") ; sc . write (format ! ("1\n")) ; let mut output = Vec :: new () ; { let mut sc = IO :: new (& b"" [..] , & mut output) ; sc . write (format ! ("{}\n" , 1)) ; sc . write (format ! ("{}\n" , 2)) ; sc . write (format ! ("{}\n" , 3)) ; } let output = String :: from_utf8 (output) . expect ("Not UTF-8") ; assert_eq ! (& output , "1\n2\n3\n") ; } } } } # [doc = " String algorithms."] pub mod string { pub mod rolling_hash { pub mod rolling_hash { const MASK_30 : u64 = (1 << 30) - 1 ; const MASK_31 : u64 = (1 << 31) - 1 ; const MOD : u64 = (1 << 61) - 1 ; pub struct RollingHash { hash : Vec < u64 > , pow : Vec < u64 > , } impl RollingHash { pub fn new (s : & [u8] , base : u64) -> RollingHash { let n = s . len () ; let mut hash : Vec < u64 > = vec ! [0 ; n + 1] ; let mut pow : Vec < u64 > = vec ! [0 ; n + 1] ; pow [0] = 1 ; for i in 0 .. n { pow [i + 1] = modulo (mod_mul (pow [i] , base)) ; hash [i + 1] = modulo (mod_mul (hash [i] , base) + s [i] as u64) ; } RollingHash { hash , pow } } # [doc = " Get hash of [l, r)"] pub fn get_hash (& self , l : usize , r : usize) -> u64 { modulo (self . hash [r] + MOD - mod_mul (self . hash [l] , self . pow [r - l])) } } fn mod_mul (a : u64 , b : u64) -> u64 { let (a_prefix , a_suffix) = (a >> 31 , a & MASK_31) ; let (b_prefix , b_suffix) = (b >> 31 , b & MASK_31) ; let m = a_suffix * b_prefix + a_prefix * b_suffix ; modulo (a_prefix * b_prefix * 2 + (m >> 30) + ((m & MASK_30) << 31) + a_suffix * b_suffix) } fn modulo (v : u64) -> u64 { let v = (v & MOD) + (v >> 61) ; if v >= MOD { v - MOD } else { v } } } # [cfg (test)] mod tests { use super :: * ; use rand :: distributions :: Uniform ; use rand :: Rng ; const BASE : u64 = 1_000_000_007 ; # [test] fn test_rolling_hash () { let n = 30 ; let mut rng = rand :: thread_rng () ; for _ in 0 .. 100 { let mut s = String :: new () ; for _ in 0 .. n { let c = (rng . sample (Uniform :: from (0 .. 26)) as u8 + 'a' as u8) as char ; s . push (c) ; } let t = String :: new () + s . as_str () + s . as_str () ; let n = t . len () ; let rolling_hash = rolling_hash :: RollingHash :: new (& t . as_bytes () , BASE) ; for i in 0 .. n { for j in i .. n { for k in (j + 1) .. n { let same = t [i .. k] == t [j .. k] ; let same_hash = rolling_hash . get_hash (i , k) == rolling_hash . get_hash (j , k) ; assert_eq ! (same , same_hash , "{:?} {:?} {} {}" , & t [i .. k] , & t [j .. k] , rolling_hash . get_hash (i , k) , rolling_hash . get_hash (j , k)) ; } } } } } } } pub mod z_algorithm { pub mod z_algorithm { pub fn calc_z_array < T : PartialEq > (s : & [T]) -> Vec < usize > { let n = s . len () ; let mut z_array = vec ! [0 ; n] ; let mut l = 0 ; let mut r = 1 ; for i in 1 .. n { if i >= r { l = i ; r = i + 1 ; while r <= n && s [r - 1 - l] == s [r - 1] { r += 1 ; } z_array [i] = r - l - 1 ; r -= 1 ; } else if z_array [i - l] < r - i { z_array [i] = z_array [i - l] ; } else { l = i ; while r <= n && s [r - 1 - l] == s [r - 1] { r += 1 ; } z_array [i] = r - l - 1 ; r -= 1 ; } } z_array [0] = n ; z_array } } # [cfg (test)] mod tests { use super :: * ; use rand :: distributions :: Uniform ; use rand :: Rng ; # [test] fn test_z () { let n = 1000 ; let mut rng = rand :: thread_rng () ; for _ in 0 .. 100 { let mut s = String :: new () ; for _ in 0 .. n { let c = (rng . sample (Uniform :: from (0 .. 26)) as u8 + 'a' as u8) as char ; s . push (c) ; } let t = String :: new () + s . as_str () + s . as_str () ; let z_array = z_algorithm :: calc_z_array (& t . as_bytes ()) ; let n = t . len () ; for i in 0 .. n { let l = z_array [i] ; assert_eq ! (& t [0 .. l] , & t [i .. (i + l)]) ; assert ! (i + l >= t . len () || t [l .. (l + 1)] != t [(i + l) .. (i + l + 1)]) ; } } } } } } }

Measured memory_bytes: 5404