// -*- coding:utf-8-unix -*- // rustup doc --std --toolchain 1.42.0 #![allow(unused_imports)] pub fn solve() { // Initialize. use fastproconio::*; #[rustfmt::skip] #[cfg(tcheck)] let tins = std::time::Instant::now(); #[rustfmt::skip] #[cfg(tcheck)] let mut durs = Vec::with_capacity(16); let stdin = std::io::stdin(); let mut source = ProconIBufIter::new(stdin.lock()); #[rustfmt::skip] #[allow(unused_macros)] macro_rules! finput {($($r:tt)*)=>{finput_inner!{source,$($r)*}};} #[rustfmt::skip] #[allow(unused_macros)] macro_rules! fread {($t:tt)=>{{fread_value!(source,$t)}};} let mut obuf = ProconWriteBuffer::with_capacity(1 << 26); let mut out = std::io::stdout(); //let mut out = std::io::BufWriter::with_capacity(out.lock(), 1 << 26); //let err = std::io::stderr(); //let mut err = std::io::BufWriter::with_capacity(err.lock(), 1 << 26); #[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "initialize")); // Input. (Only some or no input if you want to input in parallel with the main process.) finput! { a: u32, b: u32, } #[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "input")); // Main Process, Output. let (ab_max, ab_min) = (a.max(b), a.min(b)); let mut result = a + b; for max_correct in 0..=ab_min { let max_wrong = ab_max - max_correct; let min_correct = max_correct; let min_wrong = ab_min - min_correct; let correct = max_correct + min_correct; let wrong = max_wrong + min_wrong; result.chmin(if correct >= wrong { correct - wrong } else { wrong - correct }); } obuf.uint(result); obuf.lf(); obuf.write_all(&mut out); //std::io::Write::flush(&mut out).ok(); #[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "output")); // Execution Time. #[rustfmt::skip] #[cfg(tcheck)] for (dur, s) in durs.iter() { eprintln!("{:.6} {}", dur.as_secs_f64(), s); }; } pub fn main() { const USE_THREAD: bool = false; if USE_THREAD { // In order to avoid potential stack overflow, spawn a new thread. let stack_size = 134_217_728; // 128 MB let thd = std::thread::Builder::new().stack_size(stack_size); thd.spawn(|| solve()).unwrap().join().unwrap(); } else { solve() } } /* use bitset_fixed::BitSet; use itertools::*; use num::integer::*; use petgraph::algo::*; use petgraph::graph::{DiGraph, Graph, NodeIndex, UnGraph}; use petgraph::unionfind::UnionFind; use petgraph::visit::{ Bfs, Dfs, EdgeRef, IntoEdges, NodeCount, NodeIndexable, VisitMap, Visitable, }; //use proconio::{input, marker::{Bytes, Chars, Isize1, Usize1}, source::{auto::AutoSource, line::LineSource, once::OnceSource}}; use rand::{ distributions::WeightedIndex, prelude::{thread_rng, Distribution}, seq::SliceRandom, Rng, }; use regex::Regex; use rustc_hash::{FxHasher, FxHashMap, FxHashSet}; use superslice::Ext; */ use std::{ collections::*, convert::{TryFrom, TryInto}, hash::BuildHasherDefault, io::{stderr, stdin, stdout, BufRead, BufReader, BufWriter, Read, Write}, iter::FromIterator, }; /// chmax, chmin sugar syntax trait Change { fn chmax(&mut self, x: Self); fn chmin(&mut self, x: Self); } impl Change for T { fn chmax(&mut self, x: T) { if *self < x { *self = x; } } fn chmin(&mut self, x: T) { if *self > x { *self = x; } } } pub mod fastproconio { /// input macros based on tanakh's input macro / proconio-rs. /// tanakh's input macro: /// proconio-rs: /// ProconIBufIter receive `std::io::BufRead` trait. (`std::io::StdinLock`, `std::io::BufReader`, `&[u8]`, etc.) #[macro_export] macro_rules! finput_inner { ($source:expr) => {}; ($source:expr, ) => {}; ($source:expr, mut $var:ident : $t:tt $($r:tt)*) => { let mut $var = fread_value!($source, $t); finput_inner!{$source $($r)*} }; ($source:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = fread_value!($source, $t); finput_inner!{$source $($r)*} }; } #[macro_export] macro_rules! fread_value { ($source:expr, ( $($t:tt),* )) => { ( $(fread_value!($source, $t)),* ) }; ($source:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| fread_value!($source, $t)).collect::>() }; ($source:expr, u128) => { $source.next_wordtoken().as_slice().parse_u128_raw() }; ($source:expr, usize) => { $source.next_wordtoken().as_slice().parse_u64_raw() as usize }; ($source:expr, usize1) => { $source.next_wordtoken().as_slice().parse_u64_raw() as usize - 1 }; ($source:expr, u64) => { $source.next_wordtoken().as_slice().parse_u64_raw() }; ($source:expr, u64_1) => { $source.next_wordtoken().as_slice().parse_u64_raw() - 1 }; ($source:expr, u32) => { $source.next_wordtoken().as_slice().parse_u32_raw() }; ($source:expr, u32_1) => { $source.next_wordtoken().as_slice().parse_u32_raw() - 1 }; ($source:expr, u16) => { $source.next_wordtoken().as_slice().parse_u16_raw() }; ($source:expr, u16_1) => { $source.next_wordtoken().as_slice().parse_u16_raw() - 1 }; ($source:expr, u8) => { $source.next_wordtoken().as_slice().parse_u8_raw() }; ($source:expr, i128) => { $source.next_wordtoken().as_slice().parse_i128_raw() }; ($source:expr, isize) => { $source.next_wordtoken().as_slice().parse_i64_raw() as isize }; ($source:expr, i64) => { $source.next_wordtoken().as_slice().parse_i64_raw() }; ($source:expr, i32) => { $source.next_wordtoken().as_slice().parse_i32_raw() }; ($source:expr, i16) => { $source.next_wordtoken().as_slice().parse_i16_raw() }; ($source:expr, i8) => { $source.next_wordtoken().as_slice().parse_i8_raw() }; ($source:expr, byte) => { $source.get_ascii_byte() }; ($source:expr, Bytes) => {{ $source.next_wordtoken().as_vec() }}; ($source:expr, BytesToken) => {{ $source.next_wordtoken() }}; ($source:expr, String) => {unsafe { $source.next_wordtoken().as_string_unchecked() }}; ($source:expr, LineBytes) => {{ $source.next_linetoken().as_vec() }}; ($source:expr, LineBytesToken) => {{ $source.next_linetoken() }}; ($source:expr, LineString) => {unsafe { $source.next_linetoken().as_string_unchecked() }}; ($source:expr, $t:ty) => {{ let mut v = vec![];$source.get_utf8_bytes(&mut v);unsafe { std::string::String::from_utf8_unchecked(v.as_slice()) }.parse::<$t>().expect("Parse error") }}; } unsafe fn ptr_offset_u8(dist: *const u8, origin: *const u8) -> usize { // Rust 1.47.0 or later, `dist.offset_from(origin) as usize` // dist as usize - origin as usize } #[derive(Clone, Debug)] pub enum Token<'a> { Slice(&'a [u8]), Bytes(Vec), } impl Token<'_> /* ' */ { pub fn as_slice(&self) -> &[u8] { match self { Self::Slice(s) => s, Self::Bytes(v) => v.as_slice(), } } pub fn as_vec(self) -> Vec { match self { Self::Slice(s) => s.to_vec(), Self::Bytes(v) => v, } } pub fn as_string(self) -> Result { String::from_utf8(self.as_vec()) } pub unsafe fn as_string_unchecked(self) -> String { String::from_utf8_unchecked(self.as_vec()) } } /// Interaction with `std::io::BufRead` Trait, Implementation of `Iterator` pub struct ProconIBufIter { inner: R, raw: *const u8, ptr: *const u8, end: *const u8, len: usize, balign: *const u8, wmask: Vec, } impl ProconIBufIter { pub fn new(inner: R) -> Self { const EMPTY_U8_SLICE: &'static /* ' */ [u8] = b""; Self { inner, raw: EMPTY_U8_SLICE.as_ptr(), ptr: EMPTY_U8_SLICE.as_ptr(), end: EMPTY_U8_SLICE.as_ptr(), len: 0, balign: EMPTY_U8_SLICE.as_ptr(), wmask: vec![0u64; 200], } } } impl ProconIBufIter { pub fn buf_empty(&self) -> bool { self.ptr == self.end } #[allow(clippy::missing_safety_doc)] #[cold] unsafe fn inner_read(&mut self) -> bool { debug_assert_eq!(self.ptr, self.end); self.inner.consume(ptr_offset_u8(self.ptr, self.raw)); if let Ok(s) = self.inner.fill_buf() { self.raw = s.as_ptr(); self.ptr = s.as_ptr(); self.end = s.as_ptr().add(s.len()); self.len = s.len(); self.balign = (self.raw as usize & !0x3f) as *const u8; let alignlen = (((self.end as usize) + 0x3f) & (!0x3f)) - self.balign as usize; let wmasklen = (alignlen + 63) / 64; #[cfg(target_arch = "x86_64")] { #[target_feature(enable = "avx2")] unsafe fn genmask_avx2(asl: &[u8], bsl: &mut [u64]) { use std::arch::x86_64::*; let diff = _mm256_set1_epi8(-0x21); for (a, b) in asl.chunks_exact(64).zip(bsl.iter_mut()) { let s0 = _mm256_load_si256(std::mem::transmute(a.as_ptr().add(0))); let s1 = _mm256_load_si256(std::mem::transmute(a.as_ptr().add(32))); let a0 = _mm256_add_epi8(s0, diff); let a1 = _mm256_add_epi8(s1, diff); let m0 = _mm256_movemask_epi8(_mm256_andnot_si256(s0, a0)) as u32; let m1 = _mm256_movemask_epi8(_mm256_andnot_si256(s1, a1)) as u32; *b = ((m1 as u64) << 32) | (m0 as u64); } } unsafe fn genmask_sse2(asl: &[u8], bsl: &mut [u64]) { use std::arch::x86_64::*; let diff = _mm_set1_epi8(-0x21); for (a, b) in asl.chunks_exact(64).zip(bsl.iter_mut()) { let s0 = _mm_load_si128(std::mem::transmute(a.as_ptr().add(0))); let s1 = _mm_load_si128(std::mem::transmute(a.as_ptr().add(16))); let s2 = _mm_load_si128(std::mem::transmute(a.as_ptr().add(32))); let s3 = _mm_load_si128(std::mem::transmute(a.as_ptr().add(48))); let a0 = _mm_add_epi8(s0, diff); let a1 = _mm_add_epi8(s1, diff); let a2 = _mm_add_epi8(s2, diff); let a3 = _mm_add_epi8(s3, diff); let m0 = _mm_movemask_epi8(_mm_andnot_si128(s0, a0)) as u16; let m1 = _mm_movemask_epi8(_mm_andnot_si128(s1, a1)) as u16; let m2 = _mm_movemask_epi8(_mm_andnot_si128(s2, a2)) as u16; let m3 = _mm_movemask_epi8(_mm_andnot_si128(s3, a3)) as u16; *b = ((m3 as u64) << 48) | ((m2 as u64) << 32) | ((m1 as u64) << 16) | (m0 as u64); } } if self.wmask.len() <= wmasklen { self.wmask .extend(std::iter::repeat(0).take(wmasklen + 1 - self.wmask.len())); } let asl = std::slice::from_raw_parts(self.balign, wmasklen * 64); if is_x86_feature_detected!("avx2") { genmask_avx2(asl, &mut self.wmask); } else { genmask_sse2(asl, &mut self.wmask); } }; self.len != 0 } else { self.raw = self.ptr; self.len = self.end as usize - self.ptr as usize; false } } #[allow(clippy::missing_safety_doc)] unsafe fn next_unchecked(&mut self) -> u8 { let p = self.ptr; self.ptr = p.add(1); *p } /// skip unmatch bytes pub fn skipuntil_bytes_fn bool>(&mut self, f: &mut F) -> bool { loop { let mut ptr = self.ptr; while ptr != self.end { if f(unsafe { *ptr }) { self.ptr = ptr; return true; } unsafe { ptr = ptr.add(1); } } self.ptr = ptr; if unsafe { !self.inner_read() } { return false; } } } #[inline] pub fn next_wordtoken(&mut self) -> Token { if !self.skipuntil_bytes_fn(&mut |c: u8| c > b' ') { return Token::Slice(b""); } #[cfg(target_arch = "x86_64")] unsafe { let ptr = self.ptr; let pdiff = (self.ptr as usize) - (self.balign as usize) + 1; let (p64q, p64r) = (pdiff / 64, pdiff % 64); let mut w = self.wmask.as_ptr().add(p64q); let wmask = (*w) & ((!0u64) << p64r); let mut p = self.balign.add(p64q * 64); if wmask != 0 { p = p.add(wmask.trailing_zeros() as usize); if p < self.end { self.ptr = p.add(1); return Token::Slice(std::slice::from_raw_parts( ptr, p as usize - ptr as usize, )); } } p = p.add(64); w = w.add(1); let end64 = self.end.sub(64); while p < end64 { let wmask = *w; if wmask != 0 { let tlz = wmask.trailing_zeros(); let pp = p.add(tlz as usize); self.ptr = pp.add(1); return Token::Slice(std::slice::from_raw_parts( ptr, pp as usize - ptr as usize, )); } p = p.add(64); w = w.add(1); } if p < self.end { let wmask = *w; if wmask != 0 { let tlz = wmask.trailing_zeros(); let pp = p.add(tlz as usize); if pp < self.end { self.ptr = pp.add(1); return Token::Slice(std::slice::from_raw_parts( ptr, pp as usize - ptr as usize, )); } } } let mut v = std::slice::from_raw_parts(ptr, self.end as usize - ptr as usize).to_vec(); loop { self.ptr = self.end; if !self.inner_read() { return Token::Bytes(v); } let ptr = self.ptr; let pdiff = (ptr as usize) - (self.balign as usize); let (p64q, p64r) = (pdiff / 64, pdiff % 64); let mut w = self.wmask.as_ptr().add(p64q); let mut wmask = (*w) & ((!0u64) << p64r); let mut p = self.balign.add(p64q * 64); while p < self.end { if wmask != 0 { p = p.add(wmask.trailing_zeros() as usize); if p < self.end { self.ptr = p.add(1); v.extend_from_slice(std::slice::from_raw_parts( ptr, p as usize - ptr as usize, )); return Token::Bytes(v); } break; } p = p.add(64); w = w.add(1); wmask = *w; } v.extend_from_slice(std::slice::from_raw_parts( ptr, self.end as usize - ptr as usize, )); } } #[cfg(not(target_arch = "x86_64"))] unsafe { let ptr = self.ptr; let mut p = ptr.add(1); while p < self.end { if *p <= b' ' { self.ptr = p.add(1); return Token::Slice(std::slice::from_raw_parts( ptr, p as usize - ptr as usize, )); } p = p.add(1); } let mut v = std::slice::from_raw_parts(ptr, self.end as usize - ptr as usize).to_vec(); loop { self.ptr = self.end; if !self.inner_read() { break; } let ptr = self.ptr; let mut p = ptr; while p < self.end { if *p <= b' ' { self.ptr = p.add(1); v.extend_from_slice(std::slice::from_raw_parts( ptr, p as usize - ptr as usize, )); return Token::Bytes(v); } p = p.add(1); } v.extend_from_slice(std::slice::from_raw_parts( ptr, self.end as usize - ptr as usize, )); } return Token::Bytes(v); } } #[inline] pub fn next_linetoken(&mut self) -> Token { if !self.skipuntil_bytes_fn(&mut |c: u8| c >= b' ') { return Token::Slice(b""); } #[cfg(target_arch = "x86_64")] unsafe { let ptr = self.ptr; let pdiff = (self.ptr as usize) - (self.balign as usize) + 1; let (p64q, p64r) = (pdiff / 64, pdiff % 64); let mut w = self.wmask.as_ptr().add(p64q); let mut wmask = (*w) & ((!0u64) << p64r); let mut p = self.balign.add(p64q * 64); 's: /* ' */ while p < self.end { while wmask != 0 { let tlz = wmask.trailing_zeros(); let pp = p.add(tlz as usize); if pp >= self.end { break 's; /* ' */ } if *pp < b' ' { self.ptr = pp.add(1); return Token::Slice(std::slice::from_raw_parts( ptr, pp as usize - ptr as usize, )); } wmask &= wmask.wrapping_sub(1); // elase least one bit } p = p.add(64); w = w.add(1); wmask = *w; } let mut v = std::slice::from_raw_parts(ptr, self.end as usize - ptr as usize).to_vec(); loop { self.ptr = self.end; if !self.inner_read() { break; } let ptr = self.ptr; let pdiff = (ptr as usize) - (self.balign as usize); let (p64q, p64r) = (pdiff / 64, pdiff % 64); let mut w = self.wmask.as_ptr().add(p64q); let mut wmask = (*self.wmask.get_unchecked(p64q)) & ((!0u64) << p64r); let mut p = self.balign.add(p64q * 64); 'v: /* ' */ while p < self.end { while wmask != 0 { let tlz = wmask.trailing_zeros(); let pp = p.add(tlz as usize); if pp >= self.end { break 'v; /* ' */ } assert!(*pp < b' '); if (*pp) < b' ' { self.ptr = pp.add(1); v.extend_from_slice(std::slice::from_raw_parts( ptr, pp as usize - ptr as usize, )); return Token::Bytes(v); } wmask &= wmask.wrapping_sub(1); // elase least one bit } p = p.add(64); w = w.add(1); wmask = *w; } v.extend_from_slice(std::slice::from_raw_parts( ptr, self.end as usize - ptr as usize, )); } return Token::Bytes(v); } #[cfg(not(target_arch = "x86_64"))] unsafe { let ptr = self.ptr; let mut p = ptr.add(1); while p < self.end { if *p < b' ' { self.ptr = p.add(1); return Token::Slice(std::slice::from_raw_parts( ptr, p as usize - ptr as usize, )); } p = p.add(1); } let mut v = std::slice::from_raw_parts(ptr, self.end as usize - ptr as usize).to_vec(); loop { self.ptr = self.end; if !self.inner_read() { break; } let ptr = self.ptr; let mut p = ptr; while p < self.end { if *p < b' ' { self.ptr = p.add(1); v.extend_from_slice(std::slice::from_raw_parts( ptr, p as usize - ptr as usize, )); return Token::Bytes(v); } p = p.add(1); } v.extend_from_slice(std::slice::from_raw_parts( ptr, self.end as usize - ptr as usize, )); } return Token::Bytes(v); } } } impl Iterator for ProconIBufIter { type Item = u8; fn next(&mut self) -> Option { if !self.buf_empty() || unsafe { self.inner_read() } { Some(unsafe { self.next_unchecked() }) } else { None } } fn size_hint(&self) -> (usize, Option) { (usize::max_value(), None) } } pub trait UPrimInt: Copy + Default + std::cmp::Ord + std::ops::Add + std::ops::Sub + std::ops::Mul + std::ops::Div + std::ops::Rem + std::ops::AddAssign + std::ops::SubAssign + std::ops::MulAssign + std::ops::DivAssign + std::ops::RemAssign + std::ops::Shl + std::ops::Shr + std::ops::ShlAssign + std::ops::ShrAssign + std::ops::BitAnd + std::ops::BitOr + std::ops::BitXor + std::ops::BitAndAssign + std::ops::BitOrAssign + std::ops::BitXorAssign + std::convert::From { const BITS: u32; fn count_zeros(self) -> u32; fn trailing_zeros(self) -> u32; fn leading_zeros(self) -> u32; } macro_rules! impl_uprimint { ($t:ty) => { impl UPrimInt for $t { const BITS: u32 = (0 as $t).count_zeros(); fn count_zeros(self) -> u32 { self.count_zeros() } fn trailing_zeros(self) -> u32 { self.trailing_zeros() } fn leading_zeros(self) -> u32 { self.leading_zeros() } } }; } impl_uprimint!(u8); impl_uprimint!(u16); impl_uprimint!(u32); impl_uprimint!(u64); impl_uprimint!(u128); impl_uprimint!(usize); pub trait IPrimInt: Copy + Default + std::cmp::Ord + std::ops::Add + std::ops::Sub + std::ops::Neg + std::ops::Mul + std::ops::Div + std::ops::Rem + std::convert::From { const BITS: u32; } macro_rules! impl_iprimint { ($t:ty) => { impl IPrimInt for $t { const BITS: u32 = (0 as $t).count_zeros(); } }; } impl_iprimint!(i8); impl_iprimint!(i16); impl_iprimint!(i32); impl_iprimint!(i64); impl_iprimint!(i128); impl_iprimint!(isize); #[inline] fn parseuint_arith8le(mut a: u64) -> u64 { a = (a & 0x0f0f0f0f0f0f0f0f).wrapping_mul((10 << 8) + 1) >> 8; a = (a & 0x00ff00ff00ff00ff).wrapping_mul((100 << 16) + 1) >> 16; (a & 0x0000ffff0000ffff).wrapping_mul((10000 << 32) + 1) >> 32 } #[inline] #[allow(unused)] fn parseuint_arith8be(mut a: u64) -> u64 { a = (a & 0x0f0f0f0f0f0f0f0f).wrapping_mul((1 << 8) + 10) >> 8; a = (a & 0x00ff00ff00ff00ff).wrapping_mul((1 << 16) + 100) >> 16; (a & 0x0000ffff0000ffff).wrapping_mul((1 << 32) + 10000) >> 32 } #[inline] fn parseuint_raw32b(s: [u8; 32]) -> u128 { use std::convert::TryInto; let a = parseuint_arith8le(u64::from_le_bytes((&s[0..8]).try_into().unwrap())); let b = parseuint_arith8le(u64::from_le_bytes((&s[8..16]).try_into().unwrap())); let c = parseuint_arith8le(u64::from_le_bytes((&s[16..24]).try_into().unwrap())); let d = parseuint_arith8le(u64::from_le_bytes((&s[24..32]).try_into().unwrap())); ((a * 100000000 + b) as u128) * 10000000000000000 + ((c * 100000000 + d) as u128) } #[inline] fn parseuint_raw16b(s: [u8; 16]) -> u64 { use std::convert::TryInto; let a = parseuint_arith8le(u64::from_le_bytes((&s[0..8]).try_into().unwrap())); let b = parseuint_arith8le(u64::from_le_bytes((&s[8..16]).try_into().unwrap())); a * 100000000 + b } #[inline] fn parseuint_raw8b(s: [u8; 8]) -> u64 { parseuint_arith8le(u64::from_le_bytes(s)) } #[inline] fn parseuint_raw8bf(s: &[u8]) -> u64 { let l = s.len(); debug_assert!(l <= 8); let l8 = 8 - l; let l88 = l8 * 8; parseuint_arith8le(unsafe { let s_ptr = s.as_ptr(); if l == 0 { 0 } else if (s_ptr as usize) & 0xff8 < 0xff8 { u64::from_le_bytes(*(s_ptr as *const [u8; 8])) << l88 } else { u64::from_le_bytes(*(s_ptr.sub(l8) as *const [u8; 8])) >> l88 << l88 } }) } #[inline] fn parseuint_raw4bf(s: &[u8]) -> u32 { let l = s.len(); debug_assert!(l <= 4); let l4 = 4 - l; let l48 = l4 * 8; let mut a = unsafe { let s_ptr = s.as_ptr(); if l == 0 { 0 } else if (s_ptr as usize) & 0xffc < 0xffc { u32::from_le_bytes(*(s_ptr as *const [u8; 4])) << l48 } else { u32::from_le_bytes(*(s_ptr.sub(l4) as *const [u8; 4])) >> l48 << l48 } }; a = (a & 0x0f0f0f0f).wrapping_mul((10 << 8) + 1) >> 8; a = (a & 0x00ff00ff).wrapping_mul((100 << 16) + 1) >> 16; a } #[inline] fn parseuint_raw2bf(s: &[u8]) -> u16 { let l = s.len(); debug_assert!(l <= 2); let l2 = 2 - l; let l28 = l2 * 8; let mut a = unsafe { let s_ptr = s.as_ptr(); if l == 0 { 0 } else if (s_ptr as usize) & 0xffe < 0xffe { u16::from_le_bytes(*(s_ptr as *const [u8; 2])) << l28 } else { u16::from_le_bytes(*(s_ptr.sub(l2) as *const [u8; 2])) >> l28 << l28 } }; a = (a & 0x0f0f).wrapping_mul((10 << 8) + 1) >> 8; a } pub trait ByteParseIntRaw { fn parse_u128_raw(&self) -> u128; fn parse_u64_raw(&self) -> u64; fn parse_u32_raw(&self) -> u32; fn parse_u16_raw(&self) -> u16; fn parse_u8_raw(&self) -> u8; fn parse_i128_raw(&self) -> i128; fn parse_i64_raw(&self) -> i64; fn parse_i32_raw(&self) -> i32; fn parse_i16_raw(&self) -> i16; fn parse_i8_raw(&self) -> i8; fn parse_u128_rawopt(&self) -> Option; fn parse_u64_rawopt(&self) -> Option; fn parse_u32_rawopt(&self) -> Option; fn parse_u16_rawopt(&self) -> Option; fn parse_u8_rawopt(&self) -> Option; } impl ByteParseIntRaw for &[u8] { // parse_u128_raw: empty or int(self) > u128::MAX or self.len() > 39 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior. fn parse_u128_raw(&self) -> u128 { use std::convert::TryInto; debug_assert!(!self.is_empty()); debug_assert!(self.len() <= 39); debug_assert!(self.iter().all(u8::is_ascii_digit)); let l = self.len(); if l > 32 { let (upper, lower) = self.split_at(l - 32); parseuint_raw8bf(upper) as u128 * 100000000000000000000000000000000 + parseuint_raw32b(lower.try_into().unwrap()) as u128 } else if l > 24 { let (upper, t24) = self.split_at(l - 24); let (middle, lower) = t24.split_at(8); (parseuint_raw8bf(upper) * 100000000 + parseuint_raw8b(middle.try_into().unwrap())) as u128 * 10000000000000000 + parseuint_raw16b(lower.try_into().unwrap()) as u128 } else if l > 16 { let (upper, lower) = self.split_at(l - std::mem::size_of::()); (parseuint_raw8bf(upper) as u128) * 10000000000000000 + parseuint_raw16b(lower.try_into().unwrap()) as u128 } else if l > 8 { let (upper, lower) = self.split_at(l - std::mem::size_of::()); (parseuint_raw8bf(upper) * 100000000 + parseuint_raw8b(lower.try_into().unwrap())) as u128 } else { parseuint_raw8bf(self) as u128 } } // parse_u64_raw: empty or int(self) > u64::MAX or self.len() > 20 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior. fn parse_u64_raw(&self) -> u64 { use std::convert::TryInto; debug_assert!(!self.is_empty()); debug_assert!(self.len() <= 20); debug_assert!(self.iter().all(u8::is_ascii_digit)); let l = self.len(); if l > 16 { let (upper, lower) = self.split_at(l - std::mem::size_of::()); (parseuint_raw4bf(upper) as u64) * 10000000000000000 + parseuint_raw16b(lower.try_into().unwrap()) } else if l > 8 { let (upper, lower) = self.split_at(l - std::mem::size_of::()); (parseuint_raw8bf(upper) * 100000000 + parseuint_raw8b(lower.try_into().unwrap())) as u64 } else { parseuint_raw8bf(self) as u64 } } // parse_u32_raw: empty or int(self) > u32::MAX or self.len() > 10 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior. fn parse_u32_raw(&self) -> u32 { use std::convert::TryInto; debug_assert!(!self.is_empty()); debug_assert!(self.len() <= 10); debug_assert!(self.iter().all(u8::is_ascii_digit)); let l = self.len(); if l > 8 { let (upper, lower) = self.split_at(l - std::mem::size_of::()); (parseuint_raw2bf(upper) as u32) * 100000000 + parseuint_raw8b(lower.try_into().unwrap()) as u32 } else { parseuint_raw8bf(self) as u32 } } // parse_u16_raw: empty or int(self) > u16::MAX or self.len() > 5 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior. fn parse_u16_raw(&self) -> u16 { debug_assert!(!self.is_empty()); debug_assert!(self.len() <= 5); debug_assert!(self.iter().all(u8::is_ascii_digit)); parseuint_raw8bf(self) as u16 } // parse_u8_raw: empty or int(self) > u8::MAX or self.len() > 3 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior. fn parse_u8_raw(&self) -> u8 { debug_assert!(!self.is_empty()); debug_assert!(self.len() <= 3); debug_assert!(self.iter().all(u8::is_ascii_digit)); parseuint_raw4bf(self) as u8 } fn parse_i128_raw(&self) -> i128 { debug_assert!(!self.is_empty()); if self.is_empty() { 0 } else if self[0] == b'-' { (&self[1..]).parse_u128_raw().wrapping_neg() as i128 } else { self.parse_u128_raw() as i128 } } fn parse_i64_raw(&self) -> i64 { debug_assert!(!self.is_empty()); if self.is_empty() { 0 } else if self[0] == b'-' { (&self[1..]).parse_u64_raw().wrapping_neg() as i64 } else { self.parse_u64_raw() as i64 } } fn parse_i32_raw(&self) -> i32 { debug_assert!(!self.is_empty()); if self.is_empty() { 0 } else if self[0] == b'-' { (&self[1..]).parse_u32_raw().wrapping_neg() as i32 } else { self.parse_u32_raw() as i32 } } fn parse_i16_raw(&self) -> i16 { debug_assert!(!self.is_empty()); if self.is_empty() { 0 } else if self[0] == b'-' { (&self[1..]).parse_u16_raw().wrapping_neg() as i16 } else { self.parse_u16_raw() as i16 } } fn parse_i8_raw(&self) -> i8 { debug_assert!(!self.is_empty()); if self.is_empty() { 0 } else if self[0] == b'-' { (&self[1..]).parse_u128_raw().wrapping_neg() as i8 } else { self.parse_u128_raw() as i8 } } // parse_u128_rawopt: empty or int(self) > u128::MAX or self.len() > 39 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior. fn parse_u128_rawopt(&self) -> Option { use std::convert::TryInto; debug_assert!(!self.is_empty()); debug_assert!(self.len() <= 39); debug_assert!(self.iter().all(u8::is_ascii_digit)); let l = self.len(); if l > 32 { let (upper, lower) = self.split_at(l - 32); (parseuint_raw8bf(upper) as u128).checked_mul(100000000000000000000000000000000)?.checked_add( parseuint_raw32b(lower.try_into().unwrap()) as u128) } else if l > 24 { let (upper, t24) = self.split_at(l - 24); let (middle, lower) = t24.split_at(8); Some((parseuint_raw8bf(upper) * 100000000 + parseuint_raw8b(middle.try_into().unwrap())) as u128 * 10000000000000000 + parseuint_raw16b(lower.try_into().unwrap()) as u128) } else if l > 16 { let (upper, lower) = self.split_at(l - std::mem::size_of::()); Some((parseuint_raw8bf(upper) as u128) * 10000000000000000 + parseuint_raw16b(lower.try_into().unwrap()) as u128) } else if l > 8 { let (upper, lower) = self.split_at(l - std::mem::size_of::()); Some((parseuint_raw8bf(upper) * 100000000 + parseuint_raw8b(lower.try_into().unwrap())) as u128) } else { Some(parseuint_raw8bf(self) as u128) } } // parse_u64_rawopt: empty or int(self) > u64::MAX or self.len() > 20 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior. fn parse_u64_rawopt(&self) -> Option { use std::convert::TryInto; debug_assert!(!self.is_empty()); debug_assert!(self.len() <= 20); debug_assert!(self.iter().all(u8::is_ascii_digit)); let l = self.len(); if l > 16 { let (upper, lower) = self.split_at(l - std::mem::size_of::()); (parseuint_raw4bf(upper) as u64).checked_mul(10000000000000000)?.checked_add( parseuint_raw16b(lower.try_into().unwrap())) } else if l > 8 { let (upper, lower) = self.split_at(l - std::mem::size_of::()); Some((parseuint_raw8bf(upper) * 100000000 + parseuint_raw8b(lower.try_into().unwrap())) as u64) } else { Some(parseuint_raw8bf(self) as u64) } } // parse_u32_rawopt: empty or int(self) > u32::MAX or self.len() > 10 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior. fn parse_u32_rawopt(&self) -> Option { use std::convert::TryInto; debug_assert!(!self.is_empty()); debug_assert!(self.len() <= 10); debug_assert!(self.iter().all(u8::is_ascii_digit)); let l = self.len(); if l > 8 { let (upper, lower) = self.split_at(l - std::mem::size_of::()); (parseuint_raw2bf(upper) as u32).checked_mul( 100000000)?.checked_add( parseuint_raw8b(lower.try_into().unwrap()) as u32) } else { Some(parseuint_raw8bf(self) as u32) } } // parse_u16_rawopt: empty or int(self) > u16::MAX or self.len() > 5 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior. fn parse_u16_rawopt(&self) -> Option { use std::convert::TryInto; debug_assert!(!self.is_empty()); debug_assert!(self.len() <= 5); debug_assert!(self.iter().all(u8::is_ascii_digit)); parseuint_raw8bf(self).try_into().ok() } // parse_u8_rawopt: empty or int(self) > u8::MAX or self.len() > 3 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior. fn parse_u8_rawopt(&self) -> Option { use std::convert::TryInto; debug_assert!(!self.is_empty()); debug_assert!(self.len() <= 3); debug_assert!(self.iter().all(u8::is_ascii_digit)); parseuint_raw4bf(self).try_into().ok() } } /// speed frenzy input parser for program compete pub trait ProconParse { fn get_ascii_byte(&mut self) -> u8 { self.get_ascii_byte_opt().unwrap() } fn get_ascii_byte_or_default(&mut self) -> u8 { self.get_ascii_byte_opt().unwrap_or_default() } fn get_ascii_byte_opt(&mut self) -> Option; fn parse_uint(&mut self) -> U { self.parse_uint_opt().unwrap() } fn parse_uint_or_default(&mut self) -> U { self.parse_uint_opt().unwrap_or_default() } fn parse_uint_opt(&mut self) -> Option; fn parse_iint(&mut self) -> I { self.parse_iint_opt().unwrap() } fn parse_iint_or_default(&mut self) -> I { self.parse_iint_opt().unwrap_or_default() } fn parse_iint_opt(&mut self) -> Option; } impl> ProconParse for T { fn get_ascii_byte_opt(&mut self) -> Option { loop { match self.next() { Some(c @ 0x21..=0x7e) => { return Some(c); } Some(_) => continue, _ => return None, } } } fn parse_uint_opt(&mut self) -> Option { loop { match self.next() { Some(c @ b'0'..=b'9') => { let mut v = U::from(c - b'0'); while let Some(c @ b'0'..=b'9') = self.next() { v = v * U::from(10) + U::from(c - b'0'); } return Some(v); } Some(_) => continue, _ => return None, } } } fn parse_iint_opt(&mut self) -> Option { loop { match self.next() { Some(c @ b'0'..=b'9') => { let mut v = I::from((c - b'0') as i8); while let Some(c @ b'0'..=b'9') = self.next() { v = v * I::from(10) + I::from((c - b'0') as i8); } return Some(v); } Some(b'-') => match self.next() { Some(c @ b'0'..=b'9') => { let mut v = I::from(-((c - b'0') as i8)); while let Some(c @ b'0'..=b'9') = self.next() { v = v * I::from(10) - I::from((c - b'0') as i8); } return Some(v); } _ => return None, }, Some(_) => continue, _ => return None, } } } } impl Drop for ProconIBufIter { /// Saving the pointer on interruption fn drop(&mut self) { self.inner .consume(unsafe { ptr_offset_u8(self.ptr, self.raw) }); } } /// Insufficient write buffer size causes undefined operation. pub struct ProconWriteBuffer(*mut u8, Vec); impl ProconWriteBuffer { pub fn with_capacity(capacity: usize) -> Self { let mut b = Vec::::with_capacity(capacity); let ptr = b.as_mut_ptr(); Self(ptr, b) } pub fn get_mut_ptr(&self) -> *mut u8 { self.0 } pub fn set_mut_ptr(&mut self, p: *mut u8) { self.0 = p; } fn decision(&mut self) { let bptr = self.1.as_mut_ptr(); unsafe { self.1.set_len((self.0 as usize) - (bptr as usize)) }; } pub fn clear(&mut self) { self.1.clear(); self.0 = self.1.as_mut_ptr(); } pub fn get_slice(&mut self) -> &[u8] { self.decision(); self.1.as_slice() } pub fn reserve(&mut self, additional: usize) { self.decision(); self.1.reserve(additional); self.0 = self.1.as_mut_ptr(); } pub fn reserve_exact(&mut self, additional: usize) { self.decision(); self.1.reserve_exact(additional); self.0 = self.1.as_mut_ptr(); } pub fn uint(&mut self, d: U) where U: UPrimInt + std::convert::Into, { proconwritebuf_uint(&mut self.0, d); } pub fn uint_sp(&mut self, s: &[U]) where U: UPrimInt + std::convert::Into, { let mut p = self.0; let mut it = s.iter(); if let Some(&d) = it.next() { proconwritebuf_uint(&mut p, d); for &d in it { proconwritebuf_sp(&mut p); proconwritebuf_uint(&mut p, d); } } self.0 = p; } pub fn uint_splf(&mut self, s: &[U]) where U: UPrimInt + std::convert::Into, { let mut p = self.0; let mut it = s.iter(); if let Some(&d) = it.next() { proconwritebuf_uint(&mut p, d); for &d in it { proconwritebuf_sp(&mut p); proconwritebuf_uint(&mut p, d); } } proconwritebuf_lf(&mut p); self.0 = p; } pub fn usize(&mut self, d: usize) { proconwritebuf_uint(&mut self.0, d as u64); } pub fn usize_sp(&mut self, s: &[usize]) { let mut p = self.0; let mut it = s.iter(); if let Some(&d) = it.next() { proconwritebuf_uint(&mut p, d as u64); for &d in it { proconwritebuf_sp(&mut p); proconwritebuf_uint(&mut p, d as u64); } } self.0 = p; } pub fn usize_splf(&mut self, s: &[usize]) { let mut p = self.0; let mut it = s.iter(); if let Some(&d) = it.next() { proconwritebuf_uint(&mut p, d as u64); for &d in it { proconwritebuf_sp(&mut p); proconwritebuf_uint(&mut p, d as u64); } } proconwritebuf_lf(&mut p); self.0 = p; } pub fn iint(&mut self, d: I) where I: IPrimInt + std::convert::Into, { proconwritebuf_iint(&mut self.0, d); } pub fn iint_sp(&mut self, s: &[I]) where I: IPrimInt + std::convert::Into, { let mut p = self.0; let mut it = s.iter(); if let Some(&d) = it.next() { proconwritebuf_iint(&mut p, d); for &d in it { proconwritebuf_sp(&mut p); proconwritebuf_iint(&mut p, d); } } self.0 = p; } pub fn iint_splf(&mut self, s: &[I]) where I: IPrimInt + std::convert::Into + std::convert::TryInto, { let mut p = self.0; let mut it = s.iter(); if let Some(&d) = it.next() { proconwritebuf_iint(&mut p, d); for &d in it { proconwritebuf_sp(&mut p); proconwritebuf_iint(&mut p, d); } } proconwritebuf_lf(&mut p); self.0 = p; } pub fn sp(&mut self) { proconwritebuf_sp(&mut self.0); } pub fn lf(&mut self) { proconwritebuf_lf(&mut self.0); } pub fn bytes(&mut self, s: &[u8]) { proconwritebuf_bytes(&mut self.0, s); } pub fn str(&mut self, s: &str) { proconwritebuf_str(&mut self.0, s); } pub fn string(&mut self, s: &String) { proconwritebuf_string(&mut self.0, s); } pub fn write_all(&mut self, out: &mut W) where W: std::io::Write, { self.decision(); let _ = out.write_all(self.1.as_slice()); self.1.clear(); self.0 = self.1.as_mut_ptr(); } } pub fn proconwritebuf_uint(p: &mut *mut u8, mut d: U) where U: UPrimInt + std::convert::Into, { unsafe { let bptr = *p; let mut cptr = bptr; if d != U::from(0) { while d != U::from(0) { let (q, r) = (d / U::from(10), d % U::from(10)); d = q; *cptr = b'0' + U::into(r) as u8; cptr = cptr.add(1); } *p = cptr; let mut lptr = bptr; let mut rptr = cptr.sub(1); while (lptr as usize) < (rptr as usize) { let (dr, dl) = (*lptr, *rptr); *lptr = dl; *rptr = dr; lptr = lptr.add(1); rptr = rptr.sub(1); } } else { *cptr = b'0'; *p = cptr.add(1); } }; } pub fn proconwritebuf_iint(p: &mut *mut u8, mut d: I) where I: IPrimInt + std::convert::Into, { unsafe { let bptr = *p; let mut cptr = bptr; if d > I::from(0) { while d != I::from(0) { let (q, r) = (d / I::from(10), d % I::from(10)); d = q; *cptr = b'0' + I::into(r) as u8; cptr = cptr.add(1); } *p = cptr; let mut lptr = bptr; let mut rptr = cptr.sub(1); while (lptr as usize) < (rptr as usize) { let (dr, dl) = (*lptr, *rptr); *lptr = dl; *rptr = dr; lptr = lptr.add(1); rptr = rptr.sub(1); } } else if d < I::from(0) { *cptr = b'-'; cptr = cptr.add(1); let mptr = cptr; { let (q, r) = (-(d / I::from(10)), -(d % I::from(10))); d = q; *cptr = b'0' + I::into(r) as u8; cptr = cptr.add(1); } while d != I::from(0) { let (q, r) = (d / I::from(10), d % I::from(10)); d = q; *cptr = b'0' + I::into(r) as u8; cptr = cptr.add(1); } *p = cptr; let mut lptr = mptr; let mut rptr = cptr.sub(1); while (lptr as usize) < (rptr as usize) { let (dr, dl) = (*lptr, *rptr); *lptr = dl; *rptr = dr; lptr = lptr.add(1); rptr = rptr.sub(1); } } else { *cptr = b'0'; *p = cptr.add(1); } }; } pub fn proconwritebuf_sp(p: &mut *mut u8) { *p = unsafe { **p = b' '; (*p).add(1) } } pub fn proconwritebuf_lf(p: &mut *mut u8) { *p = unsafe { **p = b'\n'; (*p).add(1) } } pub fn proconwritebuf_bytes(p: &mut *mut u8, bytes: &[u8]) { *p = unsafe { let len = bytes.len(); std::ptr::copy_nonoverlapping(bytes.as_ptr(), *p, len); (*p).add(len) }; } pub fn proconwritebuf_str(p: &mut *mut u8, s: &str) { *p = unsafe { let len = s.len(); std::ptr::copy_nonoverlapping(s.as_ptr(), *p, len); (*p).add(len) }; } pub fn proconwritebuf_string(p: &mut *mut u8, s: &String) { *p = unsafe { let len = s.len(); std::ptr::copy_nonoverlapping(s.as_ptr(), *p, len); (*p).add(len) }; } }