API tools faq
paste
Advertisement
3th1ca14aX0r

Untitled

3th1ca14aX0r
Jun 15th, 2025
21
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 91.97 KB | None | 0 0
raw download clone embed print report
  1. {"lang": "Rust", "source_code": "use std::{\n io::{self, BufRead},\n str::FromStr,\n};\n\nstruct LineBuf(String);\n\nimpl LineBuf {\n fn new() -> Self {\n Self(String::new())\n }\n\n #[allow(dead_code)]\n fn get(&self) -> &String {\n &self.0\n }\n\n fn offer(&mut self) -> &mut String {\n self.0.clear();\n &mut self.0\n }\n\n fn parse_item<T>(s: &str) -> JoyResult<T>\n where\n T: FromStr,\n {\n s.parse().or_else(|_| Err(JoyError::ParseError))\n }\n\n #[allow(dead_code)]\n fn parse<T>(&self) -> JoyResult<T>\n where\n T: FromStr,\n {\n Self::parse_item(self.0.trim())\n }\n\n #[allow(dead_code)]\n fn parse2<T1, T2>(&self) -> JoyResult<(T1, T2)>\n where\n T1: FromStr,\n T2: FromStr,\n {\n let mut it = self.0.split_whitespace();\n let a = Self::parse_item(it.next().ok_or(JoyError::LineItemExhausted)?)?;\n let b = Self::parse_item(it.next().ok_or(JoyError::LineItemExhausted)?)?;\n Ok((a, b))\n }\n\n #[allow(dead_code)]\n fn parse_vec<T>(&self) -> JoyResult<Vec<T>>\n where\n T: FromStr,\n {\n self.0\n .split_whitespace()\n .map(|s| s.parse().or(Err(JoyError::ParseError)))\n .collect()\n }\n}\n\n#[derive(Debug)]\nenum JoyError {\n IOError(io::Error),\n LineItemExhausted,\n ParseError,\n}\n\ntype JoyResult<T> = Result<T, JoyError>;\n\nimpl std::convert::From<io::Error> for JoyError {\n fn from(err: io::Error) -> Self {\n Self::IOError(err)\n }\n}\n\nfn main() -> JoyResult<()> {\n let mut buf = LineBuf::new();\n let stdin = io::stdin();\n let mut stdin = stdin.lock();\n\n stdin.read_line(buf.offer())?;\n let t: usize = buf.parse()?;\n\n for _ in 0..t {\n stdin.read_line(buf.offer())?;\n let (h, n): (i32, usize) = buf.parse2()?;\n\n stdin.read_line(buf.offer())?;\n\n let mut q: Vec<i32> = buf.parse_vec()?;\n q.push(0);\n\n assert_eq!(q.len(), n + 1);\n assert_eq!(q[0], h);\n\n // println!(\"{:?}\", q);\n\n let mut i = 0;\n let mut c = 0;\n while i < n - 1 {\n let now = q[i + 1] + 1;\n if q[i + 2] == now - 2 {\n i += 2;\n } else {\n // println!(\"q[i] = {}\", q[i]);\n c += 1;\n i += 1;\n }\n }\n\n println!(\"{}\", c);\n }\n\n Ok(())\n}\n", "lang_cluster": "Rust", "compilation_error": true, "code_uid": "91c173e6f252216b1c96d13ead8ba5a5", "src_uid": "d0c50562764f2008045fe57e5da5de1c", "difficulty": 1600}
  2. {"lang": "Rust", "source_code": "use std::{\n io::{self, BufRead},\n str::FromStr,\n};\n\nstruct LineBuf(String);\n\nimpl LineBuf {\n fn new() -> Self {\n Self(String::new())\n }\n\n #[allow(dead_code)]\n fn get(&self) -> &String {\n &self.0\n }\n\n fn offer(&mut self) -> &mut String {\n self.0.clear();\n &mut self.0\n }\n\n fn parse_item<T>(s: &str) -> JoyResult<T>\n where\n T: FromStr,\n {\n s.parse().or_else(|_| Err(JoyError::ParseError))\n }\n\n #[allow(dead_code)]\n fn parse<T>(&self) -> JoyResult<T>\n where\n T: FromStr,\n {\n Self::parse_item(self.0.trim())\n }\n\n #[allow(dead_code)]\n fn parse2<T1, T2>(&self) -> JoyResult<(T1, T2)>\n where\n T1: FromStr,\n T2: FromStr,\n {\n let mut it = self.0.split_whitespace();\n let a = Self::parse_item(it.next().ok_or(JoyError::LineItemExhausted)?)?;\n let b = Self::parse_item(it.next().ok_or(JoyError::LineItemExhausted)?)?;\n Ok((a, b))\n }\n\n #[allow(dead_code)]\n fn parse_vec<T>(&self) -> JoyResult<Vec<T>>\n where\n T: FromStr,\n {\n self.0\n .split_whitespace()\n .map(|s| s.parse().or(Err(JoyError::ParseError)))\n .collect()\n }\n}\n\n#[derive(Debug)]\nenum JoyError {\n IOError(io::Error),\n LineItemExhausted,\n ParseError,\n}\n\ntype JoyResult<T> = Result<T, JoyError>;\n\nimpl std::convert::From<io::Error> for JoyError {\n fn from(err: io::Error) -> Self {\n JoyError::IOError(err)\n }\n}\n\nfn main() -> JoyResult<()> {\n let mut buf = LineBuf::new();\n let stdin = io::stdin();\n let mut stdin = stdin.lock();\n\n stdin.read_line(buf.offer())?;\n let t: usize = buf.parse()?;\n\n for _ in 0..t {\n stdin.read_line(buf.offer())?;\n let (h, n): (i32, usize) = buf.parse2()?;\n\n stdin.read_line(buf.offer())?;\n\n let mut q: Vec<i32> = buf.parse_vec()?;\n q.push(0);\n\n assert_eq!(q.len(), n + 1);\n assert_eq!(q[0], h);\n\n // println!(\"{:?}\", q);\n\n let mut i = 0;\n let mut c = 0;\n while i < n - 1 {\n let now = q[i + 1] + 1;\n if q[i + 2] == now - 2 {\n i += 2;\n } else {\n // println!(\"q[i] = {}\", q[i]);\n c += 1;\n i += 1;\n }\n }\n\n println!(\"{}\", c);\n }\n\n Ok(())\n}\n", "lang_cluster": "Rust", "compilation_error": false, "code_uid": "70789e739b58d8e093081e204f804983", "src_uid": "d0c50562764f2008045fe57e5da5de1c", "difficulty": 1600}
  3. {"lang": "Rust", "source_code": "pub trait Readable {\n type Output;\n fn words_count() -> usize;\n fn read_words(words: &[&str]) -> Result<Self::Output, String>;\n}\n#[macro_export]\nmacro_rules! readable {\n ( $ t : ty , $ words_count : expr , |$ words : ident | $ read_words : expr ) => {\n impl Readable for $t {\n type Output = $t;\n fn words_count() -> usize {\n $words_count\n }\n fn read_words($words: &[&str]) -> Result<$t, String> {\n Ok($read_words)\n }\n }\n };\n}\nreadable!((), 1, |_ss| ());\nreadable!(String, 1, |ss| ss[0].to_string());\nimpl Readable for char {\n type Output = char;\n fn words_count() -> usize {\n 1\n }\n fn read_words(words: &[&str]) -> Result<char, String> {\n let chars: Vec<char> = words[0].chars().collect();\n if chars.len() == 1 {\n Ok(chars[0])\n } else {\n Err(format!(\"cannot parse `{}` as a char\", words[0]))\n }\n }\n}\npub struct Chars();\nimpl Readable for Chars {\n type Output = Vec<char>;\n fn words_count() -> usize {\n 1\n }\n fn read_words(words: &[&str]) -> Result<Vec<char>, String> {\n Ok(words[0].chars().collect())\n }\n}\nmacro_rules ! impl_readable_for_ints { ( $ ( $ t : ty ) * ) => { $ ( impl Readable for $ t { type Output = Self ; fn words_count ( ) -> usize { 1 } fn read_words ( words : & [ & str ] ) -> Result <$ t , String > { use std :: str :: FromStr ; <$ t >:: from_str ( words [ 0 ] ) . map_err ( | _ | { format ! ( \"cannot parse `{}` as {}\" , words [ 0 ] , stringify ! ( $ t ) ) } ) } } ) * } ; }\nimpl_readable_for_ints ! ( i8 u8 i16 u16 i32 u32 i64 u64 isize usize f32 f64 ) ;\nmacro_rules ! define_one_origin_int_types { ( $ new_t : ident $ int_t : ty ) => { # [ doc = \" Converts 1-origin integer into 0-origin when read from stdin.\" ] # [ doc = \"\" ] # [ doc = \" # Example\" ] # [ doc = \"\" ] # [ doc = \" ```no_run\" ] # [ doc = \" # #[macro_use] extern crate atcoder_snippets;\" ] # [ doc = \" # use atcoder_snippets::read::*;\" ] # [ doc = \" // Stdin: \\\"1\\\"\" ] # [ doc = \" read!(a = usize_);\" ] # [ doc = \" assert_eq!(a, 0);\" ] # [ doc = \" ```\" ] # [ allow ( non_camel_case_types ) ] pub struct $ new_t ; impl Readable for $ new_t { type Output = $ int_t ; fn words_count ( ) -> usize { 1 } fn read_words ( words : & [ & str ] ) -> Result < Self :: Output , String > { <$ int_t >:: read_words ( words ) . map ( | n | n - 1 ) } } } ; ( $ new_t : ident $ int_t : ty ; $ ( $ inner_new_t : ident $ inner_int_t : ty ) ;* ) => { define_one_origin_int_types ! ( $ new_t $ int_t ) ; define_one_origin_int_types ! ( $ ( $ inner_new_t $ inner_int_t ) ;* ) ; } ; }\ndefine_one_origin_int_types ! ( u8_ u8 ; u16_ u16 ; u32_ u32 ; u64_ u64 ; usize_ usize ) ;\nmacro_rules ! impl_readable_for_tuples { ( $ t : ident $ var : ident ) => ( ) ; ( $ t : ident $ var : ident ; $ ( $ inner_t : ident $ inner_var : ident ) ;* ) => { impl_readable_for_tuples ! ( $ ( $ inner_t $ inner_var ) ;* ) ; impl <$ t : Readable , $ ( $ inner_t : Readable ) ,*> Readable for ( $ t , $ ( $ inner_t ) ,* ) { type Output = ( <$ t >:: Output , $ ( <$ inner_t >:: Output ) ,* ) ; fn words_count ( ) -> usize { let mut n = <$ t >:: words_count ( ) ; $ ( n += <$ inner_t >:: words_count ( ) ; ) * n } # [ allow ( unused_assignments ) ] fn read_words ( words : & [ & str ] ) -> Result < Self :: Output , String > { let mut start = 0 ; let $ var = <$ t >:: read_words ( & words [ start .. start +<$ t >:: words_count ( ) ] ) ?; start += <$ t >:: words_count ( ) ; $ ( let $ inner_var = <$ inner_t >:: read_words ( & words [ start .. start +<$ inner_t >:: words_count ( ) ] ) ?; start += <$ inner_t >:: words_count ( ) ; ) * Ok ( ( $ var , $ ( $ inner_var ) ,* ) ) } } } ; }\nimpl_readable_for_tuples ! ( T8 x8 ; T7 x7 ; T6 x6 ; T5 x5 ; T4 x4 ; T3 x3 ; T2 x2 ; T1 x1 ) ;\npub trait ReadableFromLine {\n type Output;\n fn read_line(line: &str) -> Result<Self::Output, String>;\n}\nfn split_into_words(line: &str) -> Vec<&str> {\n #[allow(deprecated)]\n line.trim_right_matches('\\n').split_whitespace().collect()\n}\nimpl<T: Readable> ReadableFromLine for T {\n type Output = T::Output;\n fn read_line(line: &str) -> Result<T::Output, String> {\n let words = split_into_words(line);\n if words.len() != T::words_count() {\n return Err(format!(\n \"line `{}` has {} words, expected {}\",\n line,\n words.len(),\n T::words_count()\n ));\n }\n T::read_words(&words)\n }\n}\nmacro_rules ! impl_readable_from_line_for_tuples_with_from_iterator { ( $ u : ident : $ ( + $ bound : path ) * => $ seq_in : ty , $ seq_out : ty ; $ t : ident $ var : ident ) => { impl <$ u : Readable > ReadableFromLine for $ seq_in where <$ u as Readable >:: Output : Sized $ ( + $ bound ) * { type Output = $ seq_out ; fn read_line ( line : & str ) -> Result <$ seq_out , String > { let n = $ u :: words_count ( ) ; let words = split_into_words ( line ) ; if words . len ( ) % n != 0 { return Err ( format ! ( \"line `{}` has {} words, expected multiple of {}\" , line , words . len ( ) , n ) ) ; } let mut result = Vec :: new ( ) ; for chunk in words . chunks ( n ) { match $ u :: read_words ( chunk ) { Ok ( v ) => result . push ( v ) , Err ( msg ) => { let flagment_msg = if n == 1 { format ! ( \"word {}\" , result . len ( ) ) } else { let l = result . len ( ) ; format ! ( \"words {}-{}\" , n * l + 1 , ( n + 1 ) * l ) } ; return Err ( format ! ( \"{} of line `{}`: {}\" , flagment_msg , line , msg ) ) ; } } } Ok ( result . into_iter ( ) . collect ( ) ) } } impl < T : Readable , $ u : Readable > ReadableFromLine for ( T , $ seq_in ) where <$ u as Readable >:: Output : Sized $ ( + $ bound ) * { type Output = ( T :: Output , $ seq_out ) ; fn read_line ( line : & str ) -> Result < Self :: Output , String > { let n = T :: words_count ( ) ; # [ allow ( deprecated ) ] let trimmed = line . trim_right_matches ( '\\n' ) ; let words_and_rest : Vec <& str > = trimmed . splitn ( n + 1 , ' ' ) . collect ( ) ; if words_and_rest . len ( ) < n { return Err ( format ! ( \"line `{}` has {} words, expected at least {}\" , line , words_and_rest . len ( ) , n ) ) ; } let words = & words_and_rest [ .. n ] ; let empty_str = \"\" ; let rest = words_and_rest . get ( n ) . unwrap_or ( & empty_str ) ; Ok ( ( T :: read_words ( words ) ?, <$ seq_in >:: read_line ( rest ) ? ) ) } } } ; ( $ u : ident : $ ( + $ bound : path ) * => $ seq_in : ty , $ seq_out : ty ; $ t : ident $ var : ident , $ ( $ inner_t : ident $ inner_var : ident ) ,+ ) => { impl_readable_from_line_for_tuples_with_from_iterator ! ( $ u : $ ( + $ bound ) * => $ seq_in , $ seq_out ; $ ( $ inner_t $ inner_var ) ,+ ) ; impl <$ t : Readable , $ ( $ inner_t : Readable ) ,+ , $ u : Readable > ReadableFromLine for ( $ t , $ ( $ inner_t ) ,+ , $ seq_in ) where <$ u as Readable >:: Output : Sized $ ( + $ bound ) * { type Output = ( $ t :: Output , $ ( $ inner_t :: Output ) ,+ , $ seq_out ) ; fn read_line ( line : & str ) -> Result < Self :: Output , String > { let mut n = $ t :: words_count ( ) ; $ ( n += $ inner_t :: words_count ( ) ; ) + # [ allow ( deprecated ) ] let trimmed = line . trim_right_matches ( '\\n' ) ; let words_and_rest : Vec <& str > = trimmed . splitn ( n + 1 , ' ' ) . collect ( ) ; if words_and_rest . len ( ) < n { return Err ( format ! ( \"line `{}` has {} words, expected at least {}\" , line , words_and_rest . len ( ) , n ) ) ; } let words = & words_and_rest [ .. n ] ; let empty_str = \"\" ; let rest = words_and_rest . get ( n ) . unwrap_or ( & empty_str ) ; let ( $ var , $ ( $ inner_var ) ,* ) = < ( $ t , $ ( $ inner_t ) ,+ ) >:: read_words ( words ) ?; Ok ( ( $ var , $ ( $ inner_var ) ,* , <$ seq_in >:: read_line ( rest ) ? ) ) } } } ; }\n#[macro_export]\nmacro_rules ! readable_collection { ( $ u : ident => $ collection_in : ty , $ collection_out : ty ) => { impl_readable_from_line_for_tuples_with_from_iterator ! ( $ u : => $ collection_in , $ collection_out ; T8 x8 , T7 x7 , T6 x6 , T5 x5 , T4 x4 , T3 x3 , T2 x2 , T1 x1 ) ; } ; ( $ u : ident : $ ( $ bound : path ) ,* => $ collection_in : ty , $ collection_out : ty ) => { impl_readable_from_line_for_tuples_with_from_iterator ! ( $ u : $ ( + $ bound ) * => $ collection_in , $ collection_out ; T8 x8 , T7 x7 , T6 x6 , T5 x5 , T4 x4 , T3 x3 , T2 x2 , T1 x1 ) ; } }\nreadable_collection ! ( U => Vec < U >, Vec < U :: Output > ) ;\nreadable_collection ! ( U => std :: collections :: VecDeque < U >, std :: collections :: VecDeque < U :: Output > ) ;\nreadable_collection ! ( U : Eq , std :: hash :: Hash => std :: collections :: HashSet < U >, std :: collections :: HashSet < U :: Output > ) ;\nreadable_collection ! ( U : Ord => std :: collections :: BTreeSet < U >, std :: collections :: BTreeSet < U :: Output > ) ;\nreadable_collection ! ( U : Ord => std :: collections :: BinaryHeap < U >, std :: collections :: BinaryHeap < U :: Output > ) ;\npub fn read<T: ReadableFromLine>() -> T::Output {\n let mut line = String::new();\n std::io::stdin().read_line(&mut line).unwrap();\n T::read_line(&line).unwrap()\n}\n#[macro_export]\nmacro_rules ! read { ( ) => { let mut line = String :: new ( ) ; std :: io :: stdin ( ) . read_line ( & mut line ) . unwrap ( ) ; } ; ( $ pat : pat = $ t : ty ) => { let $ pat = read ::<$ t > ( ) ; } ; ( $ ( $ pat : pat = $ t : ty ) ,+ ) => { read ! ( ( $ ( $ pat ) ,* ) = ( $ ( $ t ) ,* ) ) ; } ; }\n#[macro_export]\nmacro_rules ! readls { ( $ ( $ pat : pat = $ t : ty ) ,+ ) => { $ ( read ! ( $ pat = $ t ) ; ) * } ; }\npub fn readx<T: ReadableFromLine>() -> Vec<T::Output> {\n use std::io::{self, BufRead};\n let stdin = io::stdin();\n let result = stdin\n .lock()\n .lines()\n .map(|line_result| {\n let line = line_result.expect(\"read from stdin failed\");\n T::read_line(&line).unwrap()\n })\n .collect();\n result\n}\n#[macro_export]\nmacro_rules ! readx_loop { ( |$ pat : pat = $ t : ty | $ body : expr ) => { { use std :: io :: BufRead ; let stdin = std :: io :: stdin ( ) ; for line in stdin . lock ( ) . lines ( ) { let line = line . expect ( \"read from stdin failed\" ) ; let $ pat = <$ t >:: read_line ( & line ) . unwrap ( ) ; $ body } } } ; ( |$ ( $ pat : pat = $ t : ty ) ,*| $ body : expr ) => { readx_loop ! ( | ( $ ( $ pat ) ,* ) = ( $ ( $ t ) ,* ) | $ body ) ; } ; }\npub fn readn<T: ReadableFromLine>(n: usize) -> Vec<T::Output> {\n use std::io::{self, BufRead};\n let stdin = io::stdin();\n let result: Vec<T::Output> = stdin\n .lock()\n .lines()\n .take(n)\n .map(|line_result| {\n let line = line_result.expect(\"read from stdin failed\");\n T::read_line(&line).unwrap()\n })\n .collect();\n if result.len() < n {\n panic!(\n \"expected reading {} lines, but only {} lines are read\",\n n,\n result.len()\n );\n }\n result\n}\n#[macro_export]\nmacro_rules ! readn_loop { ( $ n : expr , |$ pat : pat = $ t : ty | $ body : expr ) => { { use std :: io :: BufRead ; let stdin = std :: io :: stdin ( ) ; let mut lock = stdin . lock ( ) ; for _ in 0 ..$ n { let mut line = String :: new ( ) ; lock . read_line ( & mut line ) . expect ( \"read from stdin failed\" ) ; let $ pat = <$ t >:: read_line ( & line ) . unwrap ( ) ; $ body } } } ; ( $ n : expr , |$ ( $ pat : pat = $ t : ty ) ,*| $ body : expr ) => { readn_loop ! ( $ n , | ( $ ( $ pat ) ,* ) = ( $ ( $ t ) ,* ) | $ body ) ; } ; }\npub trait Words {\n fn read<T: Readable>(&self) -> T::Output;\n}\nimpl<'a> Words for [&'a str] {\n fn read<T: Readable>(&self) -> T::Output {\n T::read_words(self).unwrap()\n }\n}\nimpl<'a> Words for &'a str {\n fn read<T: Readable>(&self) -> T::Output {\n T::read_words(&[self]).unwrap()\n }\n}\n\npub struct SliceGroupBy<'a, T: 'a, K: Eq, F: Fn(&T) -> K> {\n key_fn: F,\n rest: &'a [T],\n}\nimpl<'a, T, K: Eq, F: Fn(&T) -> K> Iterator for SliceGroupBy<'a, T, K, F> {\n type Item = (K, &'a [T]);\n fn next(&mut self) -> Option<(K, &'a [T])> {\n if self.rest.is_empty() {\n return None;\n }\n let key = (self.key_fn)(&self.rest[0]);\n let mut end = 1;\n while end < self.rest.len() && (self.key_fn)(&self.rest[end]) == key {\n end += 1;\n }\n let (left, right) = self.rest.split_at(end);\n self.rest = right;\n Some((key, left))\n }\n}\npub struct SplitByGap<'a, T: 'a, F: Fn(&T, &T) -> bool> {\n gap_fn: F,\n rest: &'a [T],\n}\nimpl<'a, T, F: Fn(&T, &T) -> bool> Iterator for SplitByGap<'a, T, F> {\n type Item = &'a [T];\n fn next(&mut self) -> Option<&'a [T]> {\n if self.rest.is_empty() {\n return None;\n }\n let mut r = 1;\n while r < self.rest.len() && !(self.gap_fn)(&self.rest[r - 1], &self.rest[r]) {\n r += 1;\n }\n let (result, rest) = self.rest.split_at(r);\n self.rest = rest;\n Some(result)\n }\n}\npub struct Permutations<'a, T: 'a> {\n items: &'a [T],\n indices: Option<Vec<usize>>,\n is_first: bool,\n}\nimpl<'a, T: 'a> Iterator for Permutations<'a, T> {\n type Item = Vec<&'a T>;\n fn next(&mut self) -> Option<Vec<&'a T>> {\n if !self.is_first {\n let indices_opt = self.indices.take();\n if let Some(indices) = indices_opt {\n self.indices = next_permutation(indices);\n }\n } else {\n self.is_first = false;\n }\n self.indices\n .as_ref()\n .map(|indices| indices.into_iter().map(|&i| &self.items[i]).collect())\n }\n}\nfn next_permutation(mut indices: Vec<usize>) -> Option<Vec<usize>> {\n (0..indices.len().saturating_sub(1))\n .rev()\n .find(|&left| indices[left] < indices[left + 1])\n .map(|left| {\n let right = (0..indices.len())\n .rev()\n .find(|&right| indices[left] < indices[right])\n .unwrap();\n indices.swap(left, right);\n indices[left + 1..].reverse();\n indices\n })\n}\nfn count_inversions_sub<T: Clone + Ord>(seq: &[T]) -> (Vec<T>, usize) {\n if seq.len() <= 1 {\n (seq.to_vec(), 0)\n } else {\n let mid = seq.len() / 2;\n let (sub1, inv1) = count_inversions_sub(&seq[..mid]);\n let (sub2, inv2) = count_inversions_sub(&seq[mid..]);\n let mut sorted = Vec::new();\n let (mut i1, mut i2) = (0, 0);\n let mut inv = 0;\n loop {\n match (sub1.get(i1), sub2.get(i2)) {\n (Some(x1), Some(x2)) => {\n if x1 <= x2 {\n sorted.push(x1.clone());\n i1 += 1;\n } else {\n inv += sub1.len() - i1;\n sorted.push(x2.clone());\n i2 += 1;\n }\n }\n (Some(_), None) => {\n sorted.extend(sub1[i1..].iter().cloned());\n break;\n }\n (None, Some(_)) => {\n sorted.extend(sub2[i2..].iter().cloned());\n break;\n }\n (None, None) => break,\n }\n }\n (sorted, inv + inv1 + inv2)\n }\n}\npub trait SliceExt<T> {\n fn group_by<K: Eq, F: Fn(&T) -> K>(&self, key_fn: F) -> SliceGroupBy<T, K, F>;\n fn split_by_gap<F: Fn(&T, &T) -> bool>(&self, gap_fn: F) -> SplitByGap<T, F>;\n fn permutations(&self) -> Permutations<T>;\n fn count_inversions(&self) -> usize\n where\n T: Clone + Ord;\n}\nimpl<T> SliceExt<T> for [T] {\n fn group_by<K: Eq, F: Fn(&T) -> K>(&self, key_fn: F) -> SliceGroupBy<T, K, F> {\n SliceGroupBy {\n key_fn: key_fn,\n rest: self,\n }\n }\n fn split_by_gap<F: Fn(&T, &T) -> bool>(&self, gap_fn: F) -> SplitByGap<T, F> {\n SplitByGap {\n gap_fn: gap_fn,\n rest: self,\n }\n }\n fn permutations(&self) -> Permutations<T> {\n let indices = if self.is_empty() {\n None\n } else {\n Some((0..self.len()).collect())\n };\n Permutations {\n items: self,\n indices: indices,\n is_first: true,\n }\n }\n fn count_inversions(&self) -> usize\n where\n T: Clone + Ord,\n {\n count_inversions_sub(self).1\n }\n}\npub trait SliceOfVecsExt<T> {\n fn transpose_clone(&self) -> Option<Vec<Vec<T>>>\n where\n T: Clone;\n}\nimpl<T> SliceOfVecsExt<T> for [Vec<T>] {\n fn transpose_clone(&self) -> Option<Vec<Vec<T>>>\n where\n T: Clone,\n {\n if self.iter().any(|row| row.is_empty()) {\n return None;\n }\n if self.windows(2).any(|rows| rows[0].len() < rows[1].len()) {\n return None;\n }\n let mut result = Vec::new();\n let n = self.get(0).map_or(0, |first| first.len());\n for i in 0..n {\n let mut result_row = Vec::new();\n for j in 0..self.len() {\n if self[j].len() <= i {\n break;\n }\n result_row.push(self[j][i].clone());\n }\n result.push(result_row);\n }\n Some(result)\n }\n}\n\nfn main() {\n read!(query_count = usize);\n for _ in 0..query_count {\n read!();\n read!(mut ps = Vec<u32>);\n ps.reverse();\n ps.pop();\n let ans = ps.split_by_gap(|&a, &b| b - a > 1)\n .filter(|s| s[0] != 1 && s.len() % 2 == 1)\n .count();\n println!(\"{}\", ans);\n }\n}\n", "lang_cluster": "Rust", "compilation_error": false, "code_uid": "5f6895157f8c0c699e27ff089d147113", "src_uid": "d0c50562764f2008045fe57e5da5de1c", "difficulty": 1600}
  4. {"lang": "Rust", "source_code": "// ---------- begin scannner ----------\n#[allow(dead_code)]\nmod scanner {\n use std::str::FromStr;\n use std::str::SplitWhitespace;\n use std::io::Read;\n use std;\n pub struct Scanner<'a> {\n it: SplitWhitespace<'a>\n }\n impl<'a> Scanner<'a> {\n pub fn new(s: &'a String) -> Scanner<'a> {\n Scanner {\n it: s.split_whitespace()\n }\n }\n pub fn next<T: FromStr>(&mut self) -> T {\n match self.it.next().unwrap().parse::<T>() {\n Ok(v) => v,\n _ => panic!(\"Scanner error\")\n }\n }\n pub fn next_chars(&mut self) -> Vec<char> {\n self.next::<String>().chars().collect()\n }\n }\n pub fn read_string() -> String {\n let mut s = String::new();\n std::io::stdin().read_to_string(&mut s).unwrap();\n s\n }\n}\n// ---------- end scannner ----------\n\nuse std::io::Write;\n\nfn main() {\n let sc = scanner::read_string();\n let mut sc = scanner::Scanner::new(&sc);\n let out = std::io::stdout();\n let mut out = std::io::BufWriter::new(out.lock());\n run(&mut sc, &mut out);\n}\n\nfn run(sc: &mut scanner::Scanner, out: &mut std::io::BufWriter<std::io::StdoutLock>) {\n let q: usize = sc.next();\n for _ in 0..q {\n let _h: u32 = sc.next();\n let n: usize = sc.next();\n let mut p: Vec<u32> = (0..n).map(|_| sc.next()).collect();\n p.push(0);\n p.push(0);\n let mut ans = 0;\n let mut i = 0;\n while i < n {\n p[i] = p[i + 1] + 1;\n if i + 2 < p.len() && p[i + 2] + 1 >= p[i + 1] {\n i += 2;\n } else {\n i += 1;\n ans += 1;\n }\n }\n writeln!(out, \"{}\", ans).ok();\n }\n}\n", "lang_cluster": "Rust", "compilation_error": false, "code_uid": "355e27b87e816fa74f612387d7eb121f", "src_uid": "d0c50562764f2008045fe57e5da5de1c", "difficulty": 1600}
  5. {"lang": "Rust", "source_code": "#[doc = \" https://github.com/hatoo/competitive-rust-snippets\"]\n#[allow(unused_imports)]\nuse std::cmp::{max, min, Ordering};\n#[allow(unused_imports)]\nuse std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};\n#[allow(unused_imports)]\nuse std::io::{stdin, stdout, BufWriter, Write};\n#[allow(unused_imports)]\nuse std::iter::FromIterator;\n#[macro_export]\nmacro_rules ! dvec { ( $ t : expr ; $ len : expr ) => { vec ! [ $ t ; $ len ] } ; ( $ t : expr ; $ len : expr , $ ( $ rest : expr ) ,* ) => { vec ! [ dvec ! ( $ t ; $ ( $ rest ) ,* ) ; $ len ] } ; }\n#[allow(unused_macros)]\nmacro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , \" = {:?}, \" ) ,* ) , $ ( $ a ) ,* ) ; } }\n#[macro_export]\nmacro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut parser = Parser :: from_str ( $ s ) ; input_inner ! { parser , $ ( $ r ) * } } ; ( parser = $ parser : ident , $ ( $ r : tt ) * ) => { input_inner ! { $ parser , $ ( $ r ) * } } ; ( new_stdin_parser = $ parser : ident , $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let reader = std :: io :: BufReader :: new ( stdin . lock ( ) ) ; let mut $ parser = Parser :: new ( reader ) ; input_inner ! { $ parser , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { input ! { new_stdin_parser = parser , $ ( $ r ) * } } ; }\n#[macro_export]\nmacro_rules ! input_inner { ( $ parser : ident ) => { } ; ( $ parser : ident , ) => { } ; ( $ parser : ident , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ parser , $ t ) ; input_inner ! { $ parser $ ( $ r ) * } } ; }\n#[macro_export]\nmacro_rules ! read_value { ( $ parser : ident , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ parser , $ t ) ) ,* ) } ; ( $ parser : ident , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ parser , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ parser : ident , chars ) => { read_value ! ( $ parser , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ parser : ident , usize1 ) => { read_value ! ( $ parser , usize ) - 1 } ; ( $ parser : ident , $ t : ty ) => { $ parser . next ::<$ t > ( ) . expect ( \"Parse error\" ) } ; }\nuse std::io;\nuse std::io::BufRead;\nuse std::str;\npub struct Parser<R> {\n reader: R,\n buf: Vec<u8>,\n pos: usize,\n}\nimpl Parser<io::Empty> {\n pub fn from_str(s: &str) -> Parser<io::Empty> {\n Parser {\n reader: io::empty(),\n buf: s.as_bytes().to_vec(),\n pos: 0,\n }\n }\n}\nimpl<R: BufRead> Parser<R> {\n pub fn new(reader: R) -> Parser<R> {\n Parser {\n reader: reader,\n buf: vec![],\n pos: 0,\n }\n }\n pub fn update_buf(&mut self) {\n self.buf.clear();\n self.pos = 0;\n loop {\n let (len, complete) = {\n let buf2 = self.reader.fill_buf().unwrap();\n self.buf.extend_from_slice(buf2);\n let len = buf2.len();\n if len == 0 {\n break;\n }\n (len, buf2[len - 1] <= 0x20)\n };\n self.reader.consume(len);\n if complete {\n break;\n }\n }\n }\n pub fn next<T: str::FromStr>(&mut self) -> Result<T, T::Err> {\n loop {\n let mut begin = self.pos;\n while begin < self.buf.len() && (self.buf[begin] <= 0x20) {\n begin += 1;\n }\n let mut end = begin;\n while end < self.buf.len() && (self.buf[end] > 0x20) {\n end += 1;\n }\n if begin != self.buf.len() {\n self.pos = end;\n return str::from_utf8(&self.buf[begin..end]).unwrap().parse::<T>();\n } else {\n self.update_buf();\n }\n }\n }\n}\n#[allow(unused_macros)]\nmacro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , \" = {:?}, \" ) ,* ) , $ ( $ a ) ,* ) ; } }\n#[doc = \" https://github.com/hatoo/competitive-rust-snippets\"]\nconst BIG_STACK_SIZE: bool = true;\n#[allow(dead_code)]\nfn main() {\n use std::thread;\n if BIG_STACK_SIZE {\n thread::Builder::new()\n .stack_size(32 * 1024 * 1024)\n .name(\"solve\".into())\n .spawn(solve)\n .unwrap()\n .join()\n .unwrap();\n } else {\n solve();\n }\n}\nfn solve() {\n let out = stdout();\n let mut out = BufWriter::new(out.lock());\n input!{\n new_stdin_parser = parser,\n q: usize\n }\n for _ in 0..q {\n input!{\n parser = parser,\n h: usize, n: usize,\n x: [usize; n],\n }\n let mut sl = skiplist::Skiplist::new();\n for xi in x {\n sl.insert(xi);\n }\n let mut n_magic = 0;\n let mut cur = h;\n while cur > 2 {\n let mut it = sl.le_iter(&(cur-1));\n if let Some(next1) = it.next() {\n if cur-next1==1 { // fall\n if let Some(next2) = it.next() {\n if cur-next2 > 2 {\n n_magic += 1;\n let magic = cur-2;\n sl.remove(&cur);\n sl.remove(&next1);\n sl.insert(magic);\n cur = magic;\n }\n else {\n sl.remove(&cur);\n sl.remove(&next1);\n cur = next2;\n }\n }\n else {\n n_magic += 1;\n let magic = cur-2;\n sl.remove(&cur);\n sl.remove(&next1);\n sl.insert(magic);\n cur = magic;\n }\n } \n else {\n sl.remove(&cur);\n sl.insert(cur-1);\n cur = cur-1;\n }\n }\n else {\n sl.remove(&cur);\n sl.insert(cur-1);\n cur = cur-1;\n }\n }\n println!(\"{}\", n_magic);\n }\n}\nmod skiplist {\n use std;\n use std::cell::{Cell, RefCell};\n use std::collections::{BTreeMap, BTreeSet};\n use std::fmt;\n use std::rc::Rc;\n struct RandGen {\n x: u64,\n }\n impl RandGen {\n fn new(seed: u64) -> RandGen {\n RandGen { x: seed }\n }\n fn next(&mut self) -> u64 {\n const a: u64 = 1103515245;\n const b: u64 = 12345;\n const m: u64 = 1 << 32;\n self.x = (a * self.x + b) % m;\n self.x\n }\n }\n pub struct Skiplist<T> {\n max_height: Option<usize>,\n left_sentinel: Rc<RefCell<SkipNode<T>>>,\n right_sentinel: Rc<RefCell<SkipNode<T>>>,\n rand_gen: RandGen,\n traverse_stat: Cell<usize>,\n connect_stat: Cell<usize>,\n }\n impl Skiplist<usize> {\n fn print_graph(&self) {\n for level in (0..self.height()).rev() {\n let mut line = vec![];\n let mut cur = self.left_sentinel.clone();\n loop {\n let next0 = cur.borrow().next[level].clone();\n let next = next0.unwrap().clone();\n if next.borrow().value.is_none() {\n break;\n } else {\n cur = next.clone();\n let v = cur.borrow().value.clone().unwrap();\n line.push(v);\n }\n }\n let mut ss = vec![];\n for x in line {\n while ss.len() < x {\n ss.push(\"--\".to_string());\n }\n ss.push(format!(\"{:>02}\", x));\n }\n println!(\"{}\", ss.connect(\",\"));\n }\n println!(\"\");\n }\n }\n impl<T> Skiplist<T>\n where\n T: std::cmp::Ord + fmt::Debug + Clone,\n {\n pub fn new() -> Skiplist<T> {\n let left_sentinel = Rc::new(RefCell::new(SkipNode::sentinel()));\n let right_sentinel = Rc::new(RefCell::new(SkipNode::sentinel()));\n let sentinel_height = left_sentinel.borrow().height();\n for level in 0..sentinel_height {\n left_sentinel.borrow_mut().next[level] = Some(right_sentinel.clone());\n right_sentinel.borrow_mut().prev[level] = Some(left_sentinel.clone());\n }\n Skiplist {\n max_height: None,\n left_sentinel: left_sentinel,\n right_sentinel: right_sentinel,\n rand_gen: RandGen::new(0),\n traverse_stat: Cell::new(0),\n connect_stat: Cell::new(0),\n }\n }\n fn height(&self) -> usize {\n self.max_height.unwrap_or(33)\n }\n fn pick_height(&mut self) -> usize {\n let z = self.rand_gen.next();\n let mut k = 0;\n let mut m = 1;\n while z & m != 0 {\n k += 1;\n m <<= 1;\n }\n k + 1\n }\n pub fn insert(&mut self, x: T) -> bool {\n let mut paths = self.traverse(&x);\n if !paths.is_empty() {\n let next0 = paths[0].borrow().next[0].clone();\n let next = next0.unwrap();\n let found = next.borrow().value.as_ref() == Some(&x);\n if found {\n return false;\n }\n }\n let new_height = self.pick_height();\n self.max_height = Some(std::cmp::max(self.max_height.unwrap_or(0), new_height));\n while paths.len() < new_height {\n paths.push(self.left_sentinel.clone());\n }\n let new_node = Rc::new(RefCell::new(SkipNode::new(x, new_height)));\n for level in 0..new_height {\n let prev = &paths[level];\n self.connect_stat.set(self.connect_stat.get() + 1);\n SkipNode::connect(prev, &new_node, level);\n }\n true\n }\n fn find_node(&self, x: &T) -> Option<Rc<RefCell<SkipNode<T>>>> {\n let paths = self.traverse(x);\n if paths.is_empty() {\n return None;\n }\n let next0 = paths[0].borrow().next[0].clone();\n let next = next0.unwrap();\n if next.borrow().value.as_ref() == Some(x) {\n Some(next)\n } else {\n None\n }\n }\n pub fn find(&self, x: &T) -> bool {\n self.find_node(x).is_some()\n }\n pub fn reset_stat(&self) {\n self.traverse_stat.set(0);\n self.connect_stat.set(0);\n }\n pub fn show_stat(&self) {\n println!(\"traverse: {}\", self.traverse_stat.get());\n println!(\"connect: {}\", self.connect_stat.get());\n }\n fn traverse(&self, x: &T) -> Vec<Rc<RefCell<SkipNode<T>>>> {\n if self.height() == 0 {\n return vec![];\n }\n let mut cur = self.left_sentinel.clone();\n let mut acc = vec![self.left_sentinel.clone(); self.height()];\n let mut level = self.height() - 1;\n loop {\n if level == 0 {\n loop {\n acc[level] = cur.clone();\n let next0 = cur.borrow().next[level].clone();\n let next = next0.unwrap();\n if next.borrow().value.is_none()\n || next.borrow().value.as_ref().unwrap() >= x\n {\n break;\n } else {\n cur = next.clone();\n self.traverse_stat.set(self.traverse_stat.get() + 1);\n }\n }\n break;\n }\n let next0 = cur.borrow().next[level].clone();\n let next = next0.unwrap();\n if next.borrow().value.is_none() || next.borrow().value.as_ref().unwrap() >= x {\n acc[level] = cur.clone();\n level -= 1;\n continue;\n } else {\n cur = next;\n self.traverse_stat.set(self.traverse_stat.get() + 1);\n }\n }\n acc\n }\n fn traverse_rev(&self, x: &T) -> Vec<Rc<RefCell<SkipNode<T>>>> {\n if self.height() == 0 {\n return vec![];\n }\n let mut cur = self.right_sentinel.clone();\n let mut acc = vec![self.right_sentinel.clone(); self.height()];\n let mut level = self.height() - 1;\n loop {\n if level == 0 {\n loop {\n acc[level] = cur.clone();\n let next = cur.borrow().prev[level].clone().unwrap();\n if next.borrow().value.is_none()\n || next.borrow().value.as_ref().unwrap() <= x\n {\n break;\n } else {\n cur = next.clone();\n }\n }\n break;\n }\n let next = cur.borrow().prev[level].clone().unwrap();\n if next.borrow().value.is_none() || next.borrow().value.as_ref().unwrap() <= x {\n acc[level] = cur.clone();\n level -= 1;\n continue;\n } else {\n cur = next;\n }\n }\n acc\n }\n pub fn remove(&mut self, x: &T) -> bool {\n let node = self.find_node(x);\n if node.is_none() {\n return false;\n }\n let node = node.unwrap();\n node.borrow_mut().remove();\n true\n }\n #[doc = \"iterator in range [x,]\"]\n pub fn ge_iter(&self, x: &T) -> Range<T> {\n let f = self.traverse(x)[0].clone();\n Range {\n forward: true,\n f: f,\n b: self.right_sentinel.clone(),\n }\n }\n #[doc = \"iterator in range [,x]\"]\n pub fn le_iter(&self, x: &T) -> Range<T> {\n let b = self.traverse_rev(x)[0].clone();\n Range {\n forward: false,\n f: self.left_sentinel.clone(),\n b: b,\n }\n }\n #[doc = \"iterator in range [..]\"]\n pub fn iter(&self) -> Range<T> {\n Range {\n forward: true,\n f: self.left_sentinel.clone(),\n b: self.right_sentinel.clone(),\n }\n }\n }\n pub struct Range<T> {\n forward: bool,\n f: Rc<RefCell<SkipNode<T>>>,\n b: Rc<RefCell<SkipNode<T>>>,\n }\n impl<T: Clone> Iterator for Range<T> {\n type Item = T;\n fn next(&mut self) -> Option<Self::Item> {\n let next0 = if self.forward {\n self.f.borrow().next[0].clone()\n } else {\n self.b.borrow().prev[0].clone()\n };\n if next0.is_none() {\n return None;\n }\n let next = next0.unwrap();\n if self.forward {\n self.f = next;\n self.f.borrow().value.clone()\n } else {\n self.b = next;\n self.b.borrow().value.clone()\n }\n }\n }\n impl<T: Clone> DoubleEndedIterator for Range<T> {\n fn next_back(&mut self) -> Option<Self::Item> {\n let next0 = if self.forward {\n self.b.borrow().prev[0].clone()\n } else {\n self.f.borrow().next[0].clone()\n };\n if next0.is_none() {\n return None;\n }\n let next = next0.unwrap();\n if self.forward {\n self.b = next;\n self.b.borrow().value.clone()\n } else {\n self.f = next;\n self.f.borrow().value.clone()\n }\n }\n }\n impl<T> fmt::Debug for Skiplist<T>\n where\n T: fmt::Debug + Clone + std::cmp::Ord,\n {\n fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {\n let v: Vec<T> = self.iter().collect();\n writeln!(f, \"{:?}\", v);\n Ok(())\n }\n }\n struct SkipNode<T> {\n value: Option<T>,\n prev: Vec<Option<Rc<RefCell<SkipNode<T>>>>>,\n next: Vec<Option<Rc<RefCell<SkipNode<T>>>>>,\n }\n impl<T> fmt::Debug for SkipNode<T>\n where\n T: fmt::Debug + std::cmp::Ord,\n {\n fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {\n writeln!(f, \"{:?}, {:?}\", self.value, self.height());\n Ok(())\n }\n }\n impl<T> SkipNode<T>\n where\n T: std::cmp::Ord + fmt::Debug,\n {\n fn sentinel() -> SkipNode<T> {\n SkipNode {\n value: None,\n prev: vec![None; 33],\n next: vec![None; 33],\n }\n }\n fn new(value: T, height: usize) -> SkipNode<T> {\n SkipNode {\n value: Some(value),\n prev: vec![None; height],\n next: vec![None; height],\n }\n }\n fn height(&self) -> usize {\n self.next.len()\n }\n fn remove(&mut self) {\n for level in 0..self.height() {\n let prev_node = self.prev[level].clone().unwrap();\n let next_node = self.next[level].clone().unwrap();\n next_node.borrow_mut().prev[level] = Some(prev_node.clone());\n prev_node.borrow_mut().next[level] = Some(next_node.clone());\n }\n }\n fn connect(x: &Rc<RefCell<Self>>, y: &Rc<RefCell<Self>>, level: usize) {\n let x_next = x.borrow().next[level].clone().unwrap();\n x.borrow_mut().next[level] = Some(y.clone());\n y.borrow_mut().prev[level] = Some(x.clone());\n y.borrow_mut().next[level] = Some(x_next.clone());\n x_next.borrow_mut().prev[level] = Some(y.clone());\n }\n }\n #[test]\n fn test_iter() {\n let mut sl = Skiplist::new();\n for i in 1..6 {\n sl.insert(i);\n }\n for x in sl.iter() {\n println!(\"{}\", x);\n }\n for x in sl.ge_iter(&2) {\n println!(\"{}\", x);\n }\n for x in sl.le_iter(&2) {\n println!(\"{}\", x);\n }\n }\n #[test]\n fn test_pick_height() {\n let mut sl = Skiplist::<i64>::new();\n let mut cnt = vec![0; 60];\n for _ in 0..1_000 {\n cnt[sl.pick_height()] += 1;\n }\n println!(\"{:?}\", cnt);\n }\n #[test]\n fn test_insert() {\n let mut s = Skiplist::new();\n assert_eq!(s.find(&10), false);\n s.insert(10);\n assert_eq!(s.find(&8), false);\n assert_eq!(s.find(&10), true);\n }\n #[test]\n fn test_debug0() {\n let mut s = Skiplist::new();\n let mut data = vec![920, 265, 659];\n for x in data {\n s.insert(x);\n assert!(s.find(&x));\n }\n s.insert(660);\n dbg!(&s);\n assert!(s.find(&660));\n }\n #[test]\n fn test_debug1() {\n let mut s = Skiplist::new();\n s.insert(0);\n assert!(s.find(&0));\n s.insert(5);\n assert!(s.find(&5));\n }\n #[test]\n fn test_debug2() {\n let mut s = Skiplist::new();\n s.insert(0);\n s.insert(5);\n s.print_graph();\n s.insert(9);\n s.print_graph();\n assert_eq!(s.find(&5), true);\n s.remove(&4);\n assert_eq!(s.find(&5), true);\n s.remove(&5);\n s.print_graph();\n assert_eq!(s.find(&5), false);\n s.remove(&9);\n s.print_graph();\n assert_eq!(s.find(&9), false);\n assert_eq!(s.find(&0), true);\n }\n #[test]\n fn test_compare_reference_insert_and_find() {\n use rand::{Rng, SeedableRng, StdRng};\n let mut rng = StdRng::from_seed(&[3, 2, 1]);\n let mut ts = BTreeSet::new();\n let mut sl = Skiplist::new();\n let size = 10000;\n let mut data1 = vec![];\n for _ in 0..size {\n let x = rng.next_u64() % size;\n data1.push(x as usize);\n }\n let mut data2 = vec![];\n for _ in 0..size {\n let x = rng.next_u64() % size;\n data2.push(x as usize);\n }\n let mut data3 = vec![];\n for _ in 0..size {\n let x = rng.next_u64() % size;\n data3.push(x as usize);\n }\n println!(\"insert and find phase\");\n for x in data1 {\n ts.insert(x);\n sl.insert(x);\n assert_eq!(sl.find(&x), ts.contains(&x));\n }\n sl.print_graph();\n println!(\"find phase\");\n for x in data2 {\n assert_eq!(sl.find(&x), ts.contains(&x));\n }\n println!(\"remove phase\");\n for x in data3 {\n assert_eq!(sl.remove(&x), ts.remove(&x));\n assert_eq!(sl.find(&x), ts.contains(&x));\n }\n }\n #[test]\n fn test_skiplist_stat() {\n use rand::{Rng, SeedableRng, StdRng};\n let size = 1000;\n let mut rng = StdRng::from_seed(&[3, 2, 1]);\n let mut s = Skiplist::new();\n println!(\"insert\");\n for _ in 0..size {\n s.insert(rng.next_u64());\n }\n s.show_stat();\n s.reset_stat();\n println!(\"connect\");\n for _ in 0..size {\n s.find(&rng.next_u64());\n }\n s.show_stat();\n }\n #[bench]\n fn bench_skiplist_insert_random(b: &mut test::Bencher) {\n use rand::{Rng, SeedableRng, StdRng};\n let size = 10000;\n let mut s = Skiplist::new();\n let mut rng = StdRng::from_seed(&[3, 2, 1]);\n b.iter(|| {\n for _ in 0..size {\n s.insert(rng.next_u64());\n }\n });\n }\n #[bench]\n fn bench_skiplist_find_random(b: &mut test::Bencher) {\n use rand::{Rng, SeedableRng, StdRng};\n let size = 10000;\n let mut s = Skiplist::new();\n let mut rng = StdRng::from_seed(&[3, 2, 1]);\n for _ in 0..size {\n s.insert(rng.next_u64());\n }\n b.iter(|| {\n for _ in 0..size {\n s.find(&rng.next_u64());\n }\n });\n }\n #[bench]\n fn bench_skiplist_insert_forward(b: &mut test::Bencher) {\n let mut s = Skiplist::new();\n let size = 10000;\n let mut data = vec![];\n for i in 0..size {\n data.push(i);\n }\n b.iter(|| {\n for &x in &data {\n s.insert(x);\n }\n });\n }\n #[bench]\n fn bench_skiplist_insert_reverse(b: &mut test::Bencher) {\n let mut s = Skiplist::new();\n let size = 10000;\n let mut data = vec![];\n for i in 0..size {\n data.push(i);\n }\n data.reverse();\n b.iter(|| {\n for &x in &data {\n s.insert(x);\n }\n });\n }\n #[bench]\n fn bench_skiplist_connect_simple(b: &mut test::Bencher) {\n let left = Rc::new(RefCell::new(SkipNode::new(0, 2)));\n let right = Rc::new(RefCell::new(SkipNode::new(10000000, 2)));\n for l in 0..2 {\n left.borrow_mut().next[l] = Some(right.clone());\n right.borrow_mut().prev[l] = Some(left.clone());\n }\n let mut data = vec![];\n for i in 0..10000 {\n let n = Rc::new(RefCell::new(SkipNode::new(i + 1, 2)));\n data.push(n)\n }\n b.iter(|| {\n for n in &data {\n for l in 0..2 {\n SkipNode::connect(&left, n, l);\n }\n }\n })\n }\n #[bench]\n fn bench_skiplist_connect_random(b: &mut test::Bencher) {\n use rand::{Rng, SeedableRng, StdRng};\n let mut rng = StdRng::from_seed(&[3, 2, 1]);\n let left = Rc::new(RefCell::new(SkipNode::new(0, 2)));\n let right = Rc::new(RefCell::new(SkipNode::new(10000000, 2)));\n for l in 0..2 {\n left.borrow_mut().next[l] = Some(right.clone());\n right.borrow_mut().prev[l] = Some(left.clone());\n }\n let mut prev_cands = vec![left.clone()];\n let mut data = vec![];\n for i in 0..10000 {\n let n = Rc::new(RefCell::new(SkipNode::new(i + 1, 2)));\n let i = rng.next_u64() as usize % prev_cands.len();\n let prev = prev_cands[i].clone();\n data.push((prev, n.clone()));\n prev_cands.push(n.clone());\n }\n b.iter(|| {\n for (prev, n) in &data {\n for l in 0..2 {\n SkipNode::connect(&prev, &n, l);\n }\n }\n })\n }\n #[bench]\n fn bench_skiplist_alloc_new_node(b: &mut test::Bencher) {\n b.iter(|| {\n for _ in 0..10000 {\n Rc::new(RefCell::new(SkipNode::new(0, 2)));\n }\n })\n }\n #[bench]\n fn bench_skiplist_pick_height(b: &mut test::Bencher) {\n let mut sl = Skiplist::<i64>::new();\n b.iter(|| {\n for _ in 0..10000 {\n sl.pick_height();\n }\n })\n }\n #[bench]\n fn bench_btree_insert_random(b: &mut test::Bencher) {\n use rand::{Rng, SeedableRng, StdRng};\n let size = 10000;\n let mut s = BTreeSet::new();\n let mut rng = StdRng::from_seed(&[3, 2, 1]);\n b.iter(|| {\n for _ in 0..size {\n s.insert(rng.next_u64());\n }\n });\n }\n #[bench]\n fn bench_btree_find_random(b: &mut test::Bencher) {\n use rand::{Rng, SeedableRng, StdRng};\n let size = 10000;\n let mut s = BTreeSet::new();\n let mut rng = StdRng::from_seed(&[3, 2, 1]);\n for _ in 0..size {\n s.insert(rng.next_u64());\n }\n b.iter(|| {\n for _ in 0..size {\n s.contains(&rng.next_u64());\n }\n });\n }\n use std::collections::HashMap;\n pub struct Multiset<T> {\n sl: Skiplist<T>,\n counting: HashMap<T, usize>,\n }\n impl<T> Multiset<T>\n where\n T: Ord + fmt::Debug + Clone + std::hash::Hash,\n {\n pub fn new() -> Multiset<T> {\n Multiset {\n sl: Skiplist::new(),\n counting: HashMap::new(),\n }\n }\n pub fn insert(&mut self, x: T) {\n self.sl.insert(x.clone());\n *self.counting.entry(x).or_insert(0) += 1;\n }\n pub fn counting(&self, x: &T) -> usize {\n self.counting.get(x).cloned().unwrap_or(0)\n }\n pub fn remove(&mut self, x: &T) -> bool {\n let cnt = self.counting(x);\n if cnt == 0 {\n return false;\n }\n if cnt >= 2 {\n *self.counting.get_mut(x).unwrap() -= 1;\n } else if cnt == 1 {\n self.counting.remove(x);\n self.sl.remove(x);\n }\n return true;\n }\n pub fn unwrap(&self) -> &Skiplist<T> {\n &self.sl\n }\n }\n #[test]\n fn test_multiset() {\n let mut s = Multiset::new();\n assert_eq!(s.counting(&1), 0);\n s.insert(1);\n assert_eq!(s.counting(&1), 1);\n s.insert(1);\n assert_eq!(s.counting(&1), 2);\n assert!(s.remove(&1));\n assert_eq!(s.unwrap().ge_iter(&1).next().unwrap(), 1);\n assert_eq!(s.counting(&1), 1);\n assert!(s.remove(&1));\n assert_eq!(s.counting(&1), 0);\n assert_eq!(s.unwrap().ge_iter(&1).next(), None);\n }\n}", "lang_cluster": "Rust", "compilation_error": false, "code_uid": "e05ec0a3265586a6789d2d46f8e0f61e", "src_uid": "d0c50562764f2008045fe57e5da5de1c", "difficulty": 1600}
  6. {"lang": "Rust", "source_code": "#[doc = \" https://github.com/hatoo/competitive-rust-snippets\"]\n#[allow(unused_imports)]\nuse std::cmp::{max, min, Ordering};\n#[allow(unused_imports)]\nuse std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};\n#[allow(unused_imports)]\nuse std::iter::FromIterator;\n#[macro_export]\nmacro_rules ! chmax { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: max ( $ x ,$ v ) ; ) + } ; }\n#[macro_export]\nmacro_rules ! chmin { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: min ( $ x ,$ v ) ; ) + } ; }\n#[macro_export]\nmacro_rules ! max { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: max ( $ x , max ! ( $ ( $ xs ) ,+ ) ) } ; }\n#[macro_export]\nmacro_rules ! min { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: min ( $ x , min ! ( $ ( $ xs ) ,+ ) ) } ; }\n#[macro_export]\nmacro_rules ! dvec { ( $ t : expr ; $ len : expr ) => { vec ! [ $ t ; $ len ] } ; ( $ t : expr ; $ len : expr , $ ( $ rest : expr ) ,* ) => { vec ! [ dvec ! ( $ t ; $ ( $ rest ) ,* ) ; $ len ] } ; }\n#[doc = \" main\"]\n#[allow(unused_imports)]\nuse std::io::{stdin, stdout, BufWriter, Write};\n#[macro_export]\nmacro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut parser = Parser :: from_str ( $ s ) ; input_inner ! { parser , $ ( $ r ) * } } ; ( parser = $ parser : ident , $ ( $ r : tt ) * ) => { input_inner ! { $ parser , $ ( $ r ) * } } ; ( new_stdin_parser = $ parser : ident , $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let reader = std :: io :: BufReader :: new ( stdin . lock ( ) ) ; let mut $ parser = Parser :: new ( reader ) ; input_inner ! { $ parser , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { input ! { new_stdin_parser = parser , $ ( $ r ) * } } ; }\n#[macro_export]\nmacro_rules ! input_inner { ( $ parser : ident ) => { } ; ( $ parser : ident , ) => { } ; ( $ parser : ident , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ parser , $ t ) ; input_inner ! { $ parser $ ( $ r ) * } } ; }\n#[macro_export]\nmacro_rules ! read_value { ( $ parser : ident , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ parser , $ t ) ) ,* ) } ; ( $ parser : ident , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ parser , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ parser : ident , chars ) => { read_value ! ( $ parser , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ parser : ident , usize1 ) => { read_value ! ( $ parser , usize ) - 1 } ; ( $ parser : ident , $ t : ty ) => { $ parser . next ::<$ t > ( ) . expect ( \"Parse error\" ) } ; }\nuse std::io;\nuse std::io::BufRead;\nuse std::str;\npub struct Parser<R> {\n reader: R,\n buf: Vec<u8>,\n pos: usize,\n}\nimpl Parser<io::Empty> {\n pub fn from_str(s: &str) -> Parser<io::Empty> {\n Parser {\n reader: io::empty(),\n buf: s.as_bytes().to_vec(),\n pos: 0,\n }\n }\n}\nimpl<R: BufRead> Parser<R> {\n pub fn new(reader: R) -> Parser<R> {\n Parser {\n reader: reader,\n buf: vec![],\n pos: 0,\n }\n }\n pub fn update_buf(&mut self) {\n self.buf.clear();\n self.pos = 0;\n loop {\n let (len, complete) = {\n let buf2 = self.reader.fill_buf().unwrap();\n self.buf.extend_from_slice(buf2);\n let len = buf2.len();\n if len == 0 {\n break;\n }\n (len, buf2[len - 1] <= 0x20)\n };\n self.reader.consume(len);\n if complete {\n break;\n }\n }\n }\n pub fn next<T: str::FromStr>(&mut self) -> Result<T, T::Err> {\n loop {\n let mut begin = self.pos;\n while begin < self.buf.len() && (self.buf[begin] <= 0x20) {\n begin += 1;\n }\n let mut end = begin;\n while end < self.buf.len() && (self.buf[end] > 0x20) {\n end += 1;\n }\n if begin != self.buf.len() {\n self.pos = end;\n return str::from_utf8(&self.buf[begin..end]).unwrap().parse::<T>();\n } else {\n self.update_buf();\n }\n }\n }\n}\n#[allow(unused_macros)]\nmacro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , \" = {:?}, \" ) ,* ) , $ ( $ a ) ,* ) ; } }\n#[doc = \" https://github.com/hatoo/competitive-rust-snippets\"]\nconst BIG_STACK_SIZE: bool = true;\n#[allow(dead_code)]\nfn main() {\n use std::thread;\n if BIG_STACK_SIZE {\n thread::Builder::new()\n .stack_size(32 * 1024 * 1024)\n .name(\"solve\".into())\n .spawn(solve)\n .unwrap()\n .join()\n .unwrap();\n } else {\n solve();\n }\n}\nfn solve() {\n let out = stdout();\n let mut out = BufWriter::new(out.lock());\n input!{\n new_stdin_parser = parser,\n q:usize,\n }\n for _ in 0..q {\n input!{\n parser = parser,\n h:usize,n:usize,\n p:[usize;n],\n }\n let mut state = vec![false; h+1];\n for pi in p {\n state[pi] = true;\n }\n let mut magic = 0;\n let mut cur = h;\n while cur > 2 {\n assert!(state[cur]);\n\n let jump1 = cur-1;\n let jump2 = cur-2;\n // 2jump case\n if state[jump1] && state[jump2] {\n cur = jump2;\n }\n else if !state[jump1] {\n state[jump1] = true;\n cur = jump1;\n }\n else {\n magic += 1;\n state[jump2] = true;\n cur = jump2;\n }\n }\n println!(\"{}\",magic);\n }\n}", "lang_cluster": "Rust", "compilation_error": false, "code_uid": "b3249dddb57f553525d6b858ab92ce28", "src_uid": "d0c50562764f2008045fe57e5da5de1c", "difficulty": 1600}
  7. {"lang": "Rust", "source_code": "#[doc = \" https://github.com/hatoo/competitive-rust-snippets\"]\n#[allow(unused_imports)]\nuse std::cmp::{max, min, Ordering};\n#[allow(unused_imports)]\nuse std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};\n#[allow(unused_imports)]\nuse std::iter::FromIterator;\n#[macro_export]\nmacro_rules ! chmax { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: max ( $ x ,$ v ) ; ) + } ; }\n#[macro_export]\nmacro_rules ! chmin { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: min ( $ x ,$ v ) ; ) + } ; }\n#[macro_export]\nmacro_rules ! max { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: max ( $ x , max ! ( $ ( $ xs ) ,+ ) ) } ; }\n#[macro_export]\nmacro_rules ! min { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: min ( $ x , min ! ( $ ( $ xs ) ,+ ) ) } ; }\n#[macro_export]\nmacro_rules ! dvec { ( $ t : expr ; $ len : expr ) => { vec ! [ $ t ; $ len ] } ; ( $ t : expr ; $ len : expr , $ ( $ rest : expr ) ,* ) => { vec ! [ dvec ! ( $ t ; $ ( $ rest ) ,* ) ; $ len ] } ; }\n#[doc = \" main\"]\n#[allow(unused_imports)]\nuse std::io::{stdin, stdout, BufWriter, Write};\n#[macro_export]\nmacro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut parser = Parser :: from_str ( $ s ) ; input_inner ! { parser , $ ( $ r ) * } } ; ( parser = $ parser : ident , $ ( $ r : tt ) * ) => { input_inner ! { $ parser , $ ( $ r ) * } } ; ( new_stdin_parser = $ parser : ident , $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let reader = std :: io :: BufReader :: new ( stdin . lock ( ) ) ; let mut $ parser = Parser :: new ( reader ) ; input_inner ! { $ parser , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { input ! { new_stdin_parser = parser , $ ( $ r ) * } } ; }\n#[macro_export]\nmacro_rules ! input_inner { ( $ parser : ident ) => { } ; ( $ parser : ident , ) => { } ; ( $ parser : ident , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ parser , $ t ) ; input_inner ! { $ parser $ ( $ r ) * } } ; }\n#[macro_export]\nmacro_rules ! read_value { ( $ parser : ident , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ parser , $ t ) ) ,* ) } ; ( $ parser : ident , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ parser , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ parser : ident , chars ) => { read_value ! ( $ parser , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ parser : ident , usize1 ) => { read_value ! ( $ parser , usize ) - 1 } ; ( $ parser : ident , $ t : ty ) => { $ parser . next ::<$ t > ( ) . expect ( \"Parse error\" ) } ; }\nuse std::io;\nuse std::io::BufRead;\nuse std::str;\npub struct Parser<R> {\n reader: R,\n buf: Vec<u8>,\n pos: usize,\n}\nimpl Parser<io::Empty> {\n pub fn from_str(s: &str) -> Parser<io::Empty> {\n Parser {\n reader: io::empty(),\n buf: s.as_bytes().to_vec(),\n pos: 0,\n }\n }\n}\nimpl<R: BufRead> Parser<R> {\n pub fn new(reader: R) -> Parser<R> {\n Parser {\n reader: reader,\n buf: vec![],\n pos: 0,\n }\n }\n pub fn update_buf(&mut self) {\n self.buf.clear();\n self.pos = 0;\n loop {\n let (len, complete) = {\n let buf2 = self.reader.fill_buf().unwrap();\n self.buf.extend_from_slice(buf2);\n let len = buf2.len();\n if len == 0 {\n break;\n }\n (len, buf2[len - 1] <= 0x20)\n };\n self.reader.consume(len);\n if complete {\n break;\n }\n }\n }\n pub fn next<T: str::FromStr>(&mut self) -> Result<T, T::Err> {\n loop {\n let mut begin = self.pos;\n while begin < self.buf.len() && (self.buf[begin] <= 0x20) {\n begin += 1;\n }\n let mut end = begin;\n while end < self.buf.len() && (self.buf[end] > 0x20) {\n end += 1;\n }\n if begin != self.buf.len() {\n self.pos = end;\n return str::from_utf8(&self.buf[begin..end]).unwrap().parse::<T>();\n } else {\n self.update_buf();\n }\n }\n }\n}\n#[allow(unused_macros)]\nmacro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , \" = {:?}, \" ) ,* ) , $ ( $ a ) ,* ) ; } }\n#[doc = \" https://github.com/hatoo/competitive-rust-snippets\"]\nconst BIG_STACK_SIZE: bool = true;\n#[allow(dead_code)]\nfn main() {\n use std::thread;\n if BIG_STACK_SIZE {\n thread::Builder::new()\n .stack_size(32 * 1024 * 1024)\n .name(\"solve\".into())\n .spawn(solve)\n .unwrap()\n .join()\n .unwrap();\n } else {\n solve();\n }\n}\nfn solve() {\n let out = stdout();\n let mut out = BufWriter::new(out.lock());\n input!{\n new_stdin_parser = parser,\n q:usize,\n }\n for _ in 0..q {\n input!{\n parser = parser,\n h:usize,n:usize,\n p:[usize;n],\n }\n let mut state = HashSet::new();\n for pi in p {\n state.insert(pi);\n }\n let mut magic = 0;\n let mut cur = h;\n while cur > 2 {\n assert!(state.contains(&cur));\n\n let jump1 = cur-1;\n let jump2 = cur-2;\n // 2jump case\n if state.contains(&jump1) && state.contains(&jump2) {\n state.remove(&cur);\n state.remove(&jump1);\n cur = jump2;\n }\n else if !state.contains(&jump1) {\n state.remove(&cur);\n state.insert(jump1);\n cur = jump1;\n }\n else {\n magic += 1;\n state.remove(&cur);\n state.remove(&jump1);\n state.insert(jump2); // magic\n cur = jump2;\n }\n }\n writeln!(out,\"{}\",magic);\n }\n}", "lang_cluster": "Rust", "compilation_error": false, "code_uid": "50f2554e9f0a95b376b645f7649cb31a", "src_uid": "d0c50562764f2008045fe57e5da5de1c", "difficulty": 1600}
  8. {"lang": "Rust", "source_code": "#[doc = \" https://github.com/hatoo/competitive-rust-snippets\"]\n#[allow(unused_imports)]\nuse std::cmp::{max, min, Ordering};\n#[allow(unused_imports)]\nuse std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};\n#[allow(unused_imports)]\nuse std::iter::FromIterator;\n#[macro_export]\nmacro_rules ! chmax { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: max ( $ x ,$ v ) ; ) + } ; }\n#[macro_export]\nmacro_rules ! chmin { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: min ( $ x ,$ v ) ; ) + } ; }\n#[macro_export]\nmacro_rules ! max { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: max ( $ x , max ! ( $ ( $ xs ) ,+ ) ) } ; }\n#[macro_export]\nmacro_rules ! min { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: min ( $ x , min ! ( $ ( $ xs ) ,+ ) ) } ; }\n#[macro_export]\nmacro_rules ! dvec { ( $ t : expr ; $ len : expr ) => { vec ! [ $ t ; $ len ] } ; ( $ t : expr ; $ len : expr , $ ( $ rest : expr ) ,* ) => { vec ! [ dvec ! ( $ t ; $ ( $ rest ) ,* ) ; $ len ] } ; }\n#[doc = \" main\"]\n#[allow(unused_imports)]\nuse std::io::{stdin, stdout, BufWriter, Write};\n#[macro_export]\nmacro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut parser = Parser :: from_str ( $ s ) ; input_inner ! { parser , $ ( $ r ) * } } ; ( parser = $ parser : ident , $ ( $ r : tt ) * ) => { input_inner ! { $ parser , $ ( $ r ) * } } ; ( new_stdin_parser = $ parser : ident , $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let reader = std :: io :: BufReader :: new ( stdin . lock ( ) ) ; let mut $ parser = Parser :: new ( reader ) ; input_inner ! { $ parser , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { input ! { new_stdin_parser = parser , $ ( $ r ) * } } ; }\n#[macro_export]\nmacro_rules ! input_inner { ( $ parser : ident ) => { } ; ( $ parser : ident , ) => { } ; ( $ parser : ident , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ parser , $ t ) ; input_inner ! { $ parser $ ( $ r ) * } } ; }\n#[macro_export]\nmacro_rules ! read_value { ( $ parser : ident , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ parser , $ t ) ) ,* ) } ; ( $ parser : ident , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ parser , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ parser : ident , chars ) => { read_value ! ( $ parser , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ parser : ident , usize1 ) => { read_value ! ( $ parser , usize ) - 1 } ; ( $ parser : ident , $ t : ty ) => { $ parser . next ::<$ t > ( ) . expect ( \"Parse error\" ) } ; }\nuse std::io;\nuse std::io::BufRead;\nuse std::str;\npub struct Parser<R> {\n reader: R,\n buf: Vec<u8>,\n pos: usize,\n}\nimpl Parser<io::Empty> {\n pub fn from_str(s: &str) -> Parser<io::Empty> {\n Parser {\n reader: io::empty(),\n buf: s.as_bytes().to_vec(),\n pos: 0,\n }\n }\n}\nimpl<R: BufRead> Parser<R> {\n pub fn new(reader: R) -> Parser<R> {\n Parser {\n reader: reader,\n buf: vec![],\n pos: 0,\n }\n }\n pub fn update_buf(&mut self) {\n self.buf.clear();\n self.pos = 0;\n loop {\n let (len, complete) = {\n let buf2 = self.reader.fill_buf().unwrap();\n self.buf.extend_from_slice(buf2);\n let len = buf2.len();\n if len == 0 {\n break;\n }\n (len, buf2[len - 1] <= 0x20)\n };\n self.reader.consume(len);\n if complete {\n break;\n }\n }\n }\n pub fn next<T: str::FromStr>(&mut self) -> Result<T, T::Err> {\n loop {\n let mut begin = self.pos;\n while begin < self.buf.len() && (self.buf[begin] <= 0x20) {\n begin += 1;\n }\n let mut end = begin;\n while end < self.buf.len() && (self.buf[end] > 0x20) {\n end += 1;\n }\n if begin != self.buf.len() {\n self.pos = end;\n return str::from_utf8(&self.buf[begin..end]).unwrap().parse::<T>();\n } else {\n self.update_buf();\n }\n }\n }\n}\n#[allow(unused_macros)]\nmacro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , \" = {:?}, \" ) ,* ) , $ ( $ a ) ,* ) ; } }\n#[doc = \" https://github.com/hatoo/competitive-rust-snippets\"]\nconst BIG_STACK_SIZE: bool = true;\n#[allow(dead_code)]\nfn main() {\n use std::thread;\n if BIG_STACK_SIZE {\n thread::Builder::new()\n .stack_size(32 * 1024 * 1024)\n .name(\"solve\".into())\n .spawn(solve)\n .unwrap()\n .join()\n .unwrap();\n } else {\n solve();\n }\n}\nfn solve() {\n let out = stdout();\n let mut out = BufWriter::new(out.lock());\n input!{\n new_stdin_parser = parser,\n q:usize,\n }\n for _ in 0..q {\n input!{\n parser = parser,\n h:usize,n:usize,\n p:[usize;n],\n }\n let mut state = vec![false; h+1];\n for pi in p {\n state[pi] = true;\n }\n let mut magic = 0;\n let mut cur = h;\n while cur > 2 {\n assert!(state[cur]);\n\n let jump1 = cur-1;\n let jump2 = cur-2;\n // 2jump case\n if state[jump1] && state[jump2] {\n cur = jump2;\n }\n else if !state[jump1] {\n state[jump1] = true;\n cur = jump1;\n }\n else {\n magic += 1;\n state[jump2] = true;\n cur = jump2;\n }\n }\n writeln!(out,\"{}\",magic);\n }\n}", "lang_cluster": "Rust", "compilation_error": false, "code_uid": "19419ef1b8b2bad1daa96817856656ea", "src_uid": "d0c50562764f2008045fe57e5da5de1c", "difficulty": 1600}
  9. {"lang": "Rust", "source_code": "#[doc = \" https://github.com/hatoo/competitive-rust-snippets\"]\n#[allow(unused_imports)]\nuse std::cmp::{max, min, Ordering};\n#[allow(unused_imports)]\nuse std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};\n#[allow(unused_imports)]\nuse std::iter::FromIterator;\n#[macro_export]\nmacro_rules ! chmax { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: max ( $ x ,$ v ) ; ) + } ; }\n#[macro_export]\nmacro_rules ! chmin { ( $ x : expr , $ ( $ v : expr ) ,+ ) => { $ ( $ x = std :: cmp :: min ( $ x ,$ v ) ; ) + } ; }\n#[macro_export]\nmacro_rules ! max { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: max ( $ x , max ! ( $ ( $ xs ) ,+ ) ) } ; }\n#[macro_export]\nmacro_rules ! min { ( $ x : expr ) => ( $ x ) ; ( $ x : expr , $ ( $ xs : expr ) ,+ ) => { std :: cmp :: min ( $ x , min ! ( $ ( $ xs ) ,+ ) ) } ; }\n#[macro_export]\nmacro_rules ! dvec { ( $ t : expr ; $ len : expr ) => { vec ! [ $ t ; $ len ] } ; ( $ t : expr ; $ len : expr , $ ( $ rest : expr ) ,* ) => { vec ! [ dvec ! ( $ t ; $ ( $ rest ) ,* ) ; $ len ] } ; }\n#[doc = \" main\"]\n#[allow(unused_imports)]\nuse std::io::{stdin, stdout, BufWriter, Write};\n#[macro_export]\nmacro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut parser = Parser :: from_str ( $ s ) ; input_inner ! { parser , $ ( $ r ) * } } ; ( parser = $ parser : ident , $ ( $ r : tt ) * ) => { input_inner ! { $ parser , $ ( $ r ) * } } ; ( new_stdin_parser = $ parser : ident , $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let reader = std :: io :: BufReader :: new ( stdin . lock ( ) ) ; let mut $ parser = Parser :: new ( reader ) ; input_inner ! { $ parser , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { input ! { new_stdin_parser = parser , $ ( $ r ) * } } ; }\n#[macro_export]\nmacro_rules ! input_inner { ( $ parser : ident ) => { } ; ( $ parser : ident , ) => { } ; ( $ parser : ident , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ parser , $ t ) ; input_inner ! { $ parser $ ( $ r ) * } } ; }\n#[macro_export]\nmacro_rules ! read_value { ( $ parser : ident , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ parser , $ t ) ) ,* ) } ; ( $ parser : ident , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ parser , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ parser : ident , chars ) => { read_value ! ( $ parser , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ parser : ident , usize1 ) => { read_value ! ( $ parser , usize ) - 1 } ; ( $ parser : ident , $ t : ty ) => { $ parser . next ::<$ t > ( ) . expect ( \"Parse error\" ) } ; }\nuse std::io;\nuse std::io::BufRead;\nuse std::str;\npub struct Parser<R> {\n reader: R,\n buf: Vec<u8>,\n pos: usize,\n}\nimpl Parser<io::Empty> {\n pub fn from_str(s: &str) -> Parser<io::Empty> {\n Parser {\n reader: io::empty(),\n buf: s.as_bytes().to_vec(),\n pos: 0,\n }\n }\n}\nimpl<R: BufRead> Parser<R> {\n pub fn new(reader: R) -> Parser<R> {\n Parser {\n reader: reader,\n buf: vec![],\n pos: 0,\n }\n }\n pub fn update_buf(&mut self) {\n self.buf.clear();\n self.pos = 0;\n loop {\n let (len, complete) = {\n let buf2 = self.reader.fill_buf().unwrap();\n self.buf.extend_from_slice(buf2);\n let len = buf2.len();\n if len == 0 {\n break;\n }\n (len, buf2[len - 1] <= 0x20)\n };\n self.reader.consume(len);\n if complete {\n break;\n }\n }\n }\n pub fn next<T: str::FromStr>(&mut self) -> Result<T, T::Err> {\n loop {\n let mut begin = self.pos;\n while begin < self.buf.len() && (self.buf[begin] <= 0x20) {\n begin += 1;\n }\n let mut end = begin;\n while end < self.buf.len() && (self.buf[end] > 0x20) {\n end += 1;\n }\n if begin != self.buf.len() {\n self.pos = end;\n return str::from_utf8(&self.buf[begin..end]).unwrap().parse::<T>();\n } else {\n self.update_buf();\n }\n }\n }\n}\n#[allow(unused_macros)]\nmacro_rules ! debug { ( $ ( $ a : expr ) ,* ) => { eprintln ! ( concat ! ( $ ( stringify ! ( $ a ) , \" = {:?}, \" ) ,* ) , $ ( $ a ) ,* ) ; } }\n#[doc = \" https://github.com/hatoo/competitive-rust-snippets\"]\nconst BIG_STACK_SIZE: bool = true;\n#[allow(dead_code)]\nfn main() {\n use std::thread;\n if BIG_STACK_SIZE {\n thread::Builder::new()\n .stack_size(32 * 1024 * 1024)\n .name(\"solve\".into())\n .spawn(solve)\n .unwrap()\n .join()\n .unwrap();\n } else {\n solve();\n }\n}\nfn solve() {\n let out = stdout();\n let mut out = BufWriter::new(out.lock());\n input!{\n new_stdin_parser = parser,\n q:usize,\n }\n for _ in 0..q {\n input!{\n parser = parser,\n h:usize,n:usize,\n P:[usize;n],\n }\n let mut P = P;\n P.push(0);\n let mut state = HashSet::new();\n for &Pi in &P {\n state.insert(Pi);\n }\n let mut magic = 0;\n let mut cur = h;\n while cur > 2 {\n assert!(state.contains(&cur));\n\n let jump1 = cur-1;\n let jump2 = cur-2;\n // 2jump case\n if state.contains(&jump1) && state.contains(&jump2) {\n state.remove(&cur);\n state.remove(&jump1);\n cur = jump2;\n }\n else if !state.contains(&jump1) {\n let bs = BinarySearch {\n lower: 0,\n upper: (n-1) as i64,\n p: |i:i64| {\n let i = i as usize;\n P[i] < cur\n },\n };\n let r = bs.lower_bound() as usize;\n state.remove(&cur);\n cur = P[r] + 1;\n state.insert(cur);\n }\n else {\n magic += 1;\n state.remove(&cur);\n state.remove(&jump1);\n state.insert(jump2); // magic\n cur = jump2;\n }\n // dbg!(cur);\n }\n // println!(\"{}\",magic);\n writeln!(out,\"{}\",magic);\n }\n}\n\n#[doc = \"lower,upper are inclusive range\"]\npub struct BinarySearch<F> {\n pub p: F,\n pub lower: i64,\n pub upper: i64,\n}\nimpl<F: Fn(i64) -> bool> BinarySearch<F> {\n #[doc = \"O(log(upper-lower))\"]\n pub fn lower_bound(&self) -> i64 {\n let lower = self.lower;\n let upper = self.upper;\n assert!(lower <= upper);\n let mut lb = lower - 1;\n let mut ub = upper + 1;\n while ub - lb > 1 {\n let mid = (lb + ub) / 2;\n if (self.p)(mid) {\n ub = mid;\n } else {\n lb = mid;\n }\n }\n let latter = ub;\n latter\n }\n}", "lang_cluster": "Rust", "compilation_error": false, "code_uid": "3d16e1247c3d3b72aaa241055c123a56", "src_uid": "d0c50562764f2008045fe57e5da5de1c", "difficulty": 1600}
  10. {"lang": "Rust", "source_code": "mod union_find {\n pub struct UF {\n p: Vec<i32>,\n }\n #[allow(dead_code)]\n impl UF {\n pub fn new(n: usize) -> UF {\n UF {p: vec![-1; n] }\n }\n pub fn root(&mut self, mut x: usize) -> usize {\n while self.p[x] >= 0 {\n x = self.p[x] as usize;\n }\n x\n }\n pub fn same(&mut self, x: usize, y: usize) -> bool {\n self.root(x) == self.root(y)\n }\n pub fn unite(&mut self, mut x: usize, mut y: usize) {\n x = self.root(x);\n y = self.root(y);\n if x == y {\n return;\n }\n if self.p[x] > self.p[y] {\n std::mem::swap(&mut x, &mut y);\n }\n self.p[x] += self.p[y];\n self.p[y] = x as i32;\n }\n pub fn get_size(&mut self, x: usize) -> usize {\n let r = self.root(x);\n (-self.p[r]) as usize\n }\n }\n}\n//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 \u3088\u308a\nmacro_rules! input {\n (source = $s:expr, $($r:tt)*) => {\n let mut iter = $s.split_whitespace();\n input_inner!{iter, $($r)*}\n };\n ($($r:tt)*) => {\n let s = {\n use std::io::Read;\n let mut s = String::new();\n std::io::stdin().read_to_string(&mut s).unwrap();\n s\n };\n let mut iter = s.split_whitespace();\n input_inner!{iter, $($r)*}\n };\n}\n\nmacro_rules! input_inner {\n ($iter:expr) => {};\n ($iter:expr, ) => {};\n ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {\n let $var = read_value!($iter, $t);\n input_inner!{$iter $($r)*}\n };\n}\n\nmacro_rules! read_value {\n ($iter:expr, ( $($t:tt),* )) => {\n ( $(read_value!($iter, $t)),* )\n };\n ($iter:expr, [ $t:tt ; $len:expr ]) => {\n (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()\n };\n ($iter:expr, chars) => {\n read_value!($iter, String).chars().collect::<Vec<char>>()\n };\n ($iter:expr, usize1) => {\n read_value!($iter, usize) - 1\n };\n ($iter:expr, $t:ty) => {\n $iter.next().unwrap().parse::<$t>().expect(\"Parse error\")\n };\n}\n\n// \u3053\u3053\u307e\u3067\n\nfn run() {\n input! {\n n: usize,\n m: usize,\n a: [u64; n],\n e: [(usize, usize, u64); m],\n }\n let mut k = 0;\n let mut a: Vec<(u64, usize)> = a.into_iter().map(|x| {k += 1; (x, k)}).collect();\n a.sort();\n let mut e: Vec<(u64, usize, usize)> = e.into_iter().map(|(a, b, w)| (w, a, b)).collect();\n let (c, x) = a[0];\n for &(w, v) in a[1..].iter() {\n e.push((c + w, x, v));\n }\n e.sort();\n let mut u = union_find::UF::new(n + 1);\n let mut cost = 0;\n for (c, a, b) in e {\n if !u.same(a, b) {\n u.unite(a, b);\n cost += c;\n }\n }\n println!(\"{}\", cost);\n}\n\nfn main() {\n run();\n}\n", "lang_cluster": "Rust", "compilation_error": false, "code_uid": "f9842aa8632955e94473a732792a682b", "src_uid": "e52ec2fa5bcf5d2027d57b0694b4e15a", "difficulty": 1900}
  11. {"lang": "Rust", "source_code": "#[allow(unused_imports)]\nuse std::cmp::*;\n#[allow(unused_imports)]\nuse std::collections::*;\nuse std::io::{Write, BufWriter};\n// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8\nmacro_rules! input {\n (source = $s:expr, $($r:tt)*) => {\n let mut iter = $s.split_whitespace();\n let mut next = || { iter.next().unwrap() };\n input_inner!{next, $($r)*}\n };\n ($($r:tt)*) => {\n let stdin = std::io::stdin();\n let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));\n let mut next = move || -> String{\n bytes\n .by_ref()\n .map(|r|r.unwrap() as char)\n .skip_while(|c|c.is_whitespace())\n .take_while(|c|!c.is_whitespace())\n .collect()\n };\n input_inner!{next, $($r)*}\n };\n}\n\nmacro_rules! input_inner {\n ($next:expr) => {};\n ($next:expr, ) => {};\n\n ($next:expr, $var:ident : $t:tt $($r:tt)*) => {\n let $var = read_value!($next, $t);\n input_inner!{$next $($r)*}\n };\n}\n\nmacro_rules! read_value {\n ($next:expr, ( $($t:tt),* )) => {\n ( $(read_value!($next, $t)),* )\n };\n\n ($next:expr, [ $t:tt ; $len:expr ]) => {\n (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()\n };\n\n ($next:expr, chars) => {\n read_value!($next, String).chars().collect::<Vec<char>>()\n };\n\n ($next:expr, usize1) => {\n read_value!($next, usize) - 1\n };\n\n ($next:expr, [ $t:tt ]) => {{\n let len = read_value!($next, usize);\n (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()\n }};\n\n ($next:expr, $t:ty) => {\n $next().parse::<$t>().expect(\"Parse error\")\n };\n}\n\nfn solve() {\n let out = std::io::stdout();\n let mut out = BufWriter::new(out.lock());\n macro_rules! puts {\n ($($format:tt)*) => (write!(out,$($format)*).unwrap());\n }\n input! {\n n: usize,\n m: usize,\n a: [i64; n],\n xyw: [(usize1, usize1, i64); m],\n }\n let mut g = vec![Vec::new(); n];\n for (x, y, w) in xyw {\n g[x].push((y, w));\n g[y].push((x, w));\n }\n let mut amin = (1 << 50, n);\n for i in 0 .. n { amin = min(amin, (a[i], i)); }\n // Prim\n let mut tot = 0;\n let (added, init) = amin;\n let mut used = vec![false; n];\n used[init] = true;\n let mut que = BinaryHeap::new();\n for i in 0 .. n {\n if init != i {\n que.push(Reverse((a[i] + added, i)));\n }\n }\n for &(w, cost) in g[init].iter() {\n que.push(Reverse((cost, w)));\n }\n while let Some(Reverse((cost, v))) = que.pop() {\n if used[v] { continue; }\n tot += cost;\n used[v] = true;\n for &(w, cost) in g[v].iter() {\n que.push(Reverse((cost, w)));\n }\n }\n puts!(\"{}\\n\", tot)\n}\n\nfn main() {\n // In order to avoid potential stack overflow, spawn a new thread.\n let stack_size = 104_857_600; // 100 MB\n let thd = std::thread::Builder::new().stack_size(stack_size);\n thd.spawn(|| solve()).unwrap().join().unwrap();\n}\n", "lang_cluster": "Rust", "compilation_error": false, "code_uid": "b16b7d0fe6e78d2642950b033861c461", "src_uid": "e52ec2fa5bcf5d2027d57b0694b4e15a", "difficulty": 1900}
  12. {"lang": "Rust", "source_code": "#[allow(unused_imports)]\nuse std::cmp::{min,max};\n#[allow(unused_imports)]\nuse std::collections::{BTreeMap,BTreeSet};\n#[allow(unused_imports)]\nuse std::ops::*;\n#[allow(unused_imports)]\nuse std::collections::BinaryHeap;\n\n#[allow(unused_macros)]\nmacro_rules! ite {\n ($c:expr, $t:expr, $f:expr) => {{\n if $c { $t } else { $f }\n }};\n}\n\n// ref: tanakh <https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8>\n// diff: using Parser\n#[macro_export]\nmacro_rules! input {\n (source = $s:expr, $($r:tt)*) => {\n let mut parser = Parser::from_str($s);\n input_inner!{parser, $($r)*}\n };\n (parser = $parser:ident, $($r:tt)*) => {\n input_inner!{$parser, $($r)*}\n };\n (new_stdin_parser = $parser:ident, $($r:tt)*) => {\n let stdin = std::io::stdin();\n let reader = std::io::BufReader::new(stdin.lock());\n let mut $parser = Parser::new(reader);\n input_inner!{$parser, $($r)*}\n };\n ($($r:tt)*) => {\n input!{new_stdin_parser = parser, $($r)*}\n };\n}\n\n#[macro_export]\nmacro_rules! input_inner {\n ($parser:ident) => {};\n ($parser:ident, ) => {};\n ($parser:ident, $var:ident : $t:tt $($r:tt)*) => {\n let $var = read_value!($parser, $t);\n input_inner!{$parser $($r)*}\n };\n}\n\n#[macro_export]\nmacro_rules! read_value {\n ($parser:ident, ( $($t:tt),* )) => {\n ( $(read_value!($parser, $t)),* )\n };\n ($parser:ident, [ $t:tt ; $len:expr ]) => {\n (0..$len).map(|_| read_value!($parser, $t)).collect::<Vec<_>>()\n };\n ($parser:ident, chars) => {\n read_value!($parser, String).chars().collect::<Vec<char>>()\n };\n ($parser:ident, usize1) => {\n read_value!($parser, usize) - 1\n };\n ($parser:ident, $t:ty) => {\n $parser.next::<$t>().expect(\"Parse error\")\n };\n}\n\nfn main() {\n input! {\n n: usize,\n m: usize,\n xs: [i64; n],\n es: [(usize1, usize1, i64); m]\n }\n let mut offers = vec![BinaryHeap::new(); n];\n for &(x,y,w) in &es {\n offers[x].push((-w,y));\n offers[y].push((-w,x));\n }\n let mut used = vec![false; n];\n\n let first = 0;\n\n used[first] = true;\n let mut used_count = 1;\n let mut unused_heap = BinaryHeap::new();\n for i in 0..n {\n unused_heap.push((-xs[i], i));\n }\n\n let mut left_offers = BinaryHeap::new();\n let mut left_min = xs[first];\n left_offers.append(&mut offers[first]);\n\n let mut res = 0;\n while used_count < n {\n while let Some((nw, next)) = left_offers.pop() {\n if ! used[next] {\n left_offers.push((nw, next));\n break;\n }\n }\n while let Some((nw, v)) = unused_heap.pop() {\n if ! used[v] {\n unused_heap.push((nw, v));\n break;\n }\n }\n let mut min_next = None;\n let mut min_cost = None;\n if let Some(&(nw, next)) = left_offers.peek() {\n let t = -nw;\n if min_cost.is_none() || min_cost.unwrap() > t {\n min_cost = Some(t);\n min_next = Some(next);\n }\n }\n if let Some(&(nw, next)) = unused_heap.peek() {\n let t = left_min + -nw;\n if min_cost.is_none() || min_cost.unwrap() > t {\n min_cost = Some(t);\n min_next = Some(next);\n }\n }\n\n left_offers.append(&mut offers[min_next.unwrap()]);\n left_min = min(left_min, xs[min_next.unwrap()]);\n res += min_cost.unwrap();\n used[min_next.unwrap()] = true;\n\n used_count += 1;\n }\n println!(\"{}\", res);\n}\n\nuse std::io::BufRead;\nuse std::io;\nuse std::str;\n\n// ref: tatsuya6502 <https://qiita.com/tatsuya6502/items/cd448486f7ef7b5b8c7e>\n// ref: wariuni <https://qiita.com/tatsuya6502/items/cd448486f7ef7b5b8c7e#comment-7040a5ae96305e884eb9>\n// diff: using std::io::BufRead::fill_buf()\npub struct Parser<R> {\n reader: R,\n buf: Vec<u8>,\n pos: usize,\n}\n\nimpl Parser<io::Empty> {\n pub fn from_str(s: &str) -> Parser<io::Empty> {\n Parser {\n reader: io::empty(),\n buf: s.as_bytes().to_vec(),\n pos: 0,\n }\n }\n}\n\nimpl<R:BufRead> Parser<R> {\n pub fn new(reader: R) -> Parser<R> {\n Parser {\n reader: reader,\n buf: vec![],\n pos: 0,\n }\n }\n pub fn update_buf(&mut self) {\n self.buf.clear();\n self.pos = 0;\n loop {\n let (len,complete) = {\n let buf2 = self.reader.fill_buf().unwrap();\n self.buf.extend_from_slice(buf2);\n let len = buf2.len();\n (len, buf2[len-1] <= 0x20)\n };\n self.reader.consume(len);\n if complete {\n break;\n }\n }\n }\n pub fn next<T:str::FromStr>(&mut self) -> Result<T, T::Err> {\n loop {\n let mut begin = self.pos;\n while begin < self.buf.len() && (self.buf[begin] <= 0x20) {\n begin += 1;\n }\n let mut end = begin;\n while end < self.buf.len() && (self.buf[end] > 0x20) {\n end += 1;\n }\n if begin != self.buf.len() {\n self.pos = end;\n return str::from_utf8(&self.buf[begin..end]).unwrap().parse::<T>();\n }\n else {\n self.update_buf();\n }\n }\n }\n}\n\nuse std::fmt::Display;\n#[allow(dead_code)]\nfn write_vec<T: Display>(xs: &Vec<T>) {\n if xs.len() == 0 {\n println!();\n return;\n }\n print!(\"{}\", xs[0]);\n for i in 1..xs.len() {\n print!(\" {}\", xs[i]);\n }\n println!();\n}\n", "lang_cluster": "Rust", "compilation_error": false, "code_uid": "fdbf3a62685242bd099d947dddc8cddf", "src_uid": "e52ec2fa5bcf5d2027d57b0694b4e15a", "difficulty": 1900}
  13.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!