結果
| 問題 | No.2240 WAC |
| ユーザー |
👑  Mizar
|
| 提出日時 | 2023-03-10 22:10:43 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 5 ms / 2,000 ms |
| コード長 | 54,061 bytes |
| コンパイル時間 | 13,534 ms |
| コンパイル使用メモリ | 379,448 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-09-18 04:23:35 |
| 合計ジャッジ時間 | 13,640 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 43 |
ソースコード
// -*- 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! {
_n: usize, _m: usize,
s: BytesToken,
}
#[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "input"));
// Main Process, Output.
let sl = s.as_slice();
let mut result = true;
let mut wa_count = 0i32;
for &c in sl.iter().rev() {
match c {
b'W' => {
wa_count -= 1;
if wa_count < 0 {
result = false;
break;
}
},
b'A' => { wa_count += 1; },
_ => {},
}
}
let mut ac_count = 0i32;
for &c in sl.iter() {
match c {
b'A' => { ac_count += 1; },
b'C' => {
ac_count -= 1;
if ac_count < 0 {
result = false;
break;
}
},
_ => {},
}
}
out.write_all(if result { b"Yes\n" } else { b"No\n" }).ok();
//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<T: PartialOrd> 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: <https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8>
/// proconio-rs: <https://docs.rs/proconio/0.3.8/proconio/>
/// 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::<Vec<_>>() };
($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`
// <https://doc.rust-lang.org/std/primitive.pointer.html#method.offset_from>
dist as usize - origin as usize
}
#[derive(Clone, Debug)]
pub enum Token<'a> {
Slice(&'a [u8]),
Bytes(Vec<u8>),
}
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<u8> {
match self {
Self::Slice(s) => s.to_vec(),
Self::Bytes(v) => v,
}
}
pub fn as_string(self) -> Result<String, std::string::FromUtf8Error> {
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<Item = u8>`
pub struct ProconIBufIter<R: std::io::BufRead> {
inner: R,
raw: *const u8,
ptr: *const u8,
end: *const u8,
len: usize,
balign: *const u8,
wmask: Vec<u64>,
}
impl<R: std::io::BufRead> ProconIBufIter<R> {
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<R: std::io::BufRead> ProconIBufIter<R> {
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<F: FnMut(u8) -> 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<R: std::io::BufRead> Iterator for ProconIBufIter<R> {
type Item = u8;
fn next(&mut self) -> Option<Self::Item> {
if !self.buf_empty() || unsafe { self.inner_read() } {
Some(unsafe { self.next_unchecked() })
} else {
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(usize::max_value(), None)
}
}
pub trait UPrimInt:
Copy
+ Default
+ std::cmp::Ord
+ std::ops::Add<Output = Self>
+ std::ops::Sub<Output = Self>
+ std::ops::Mul<Output = Self>
+ std::ops::Div<Output = Self>
+ std::ops::Rem<Output = Self>
+ std::ops::AddAssign
+ std::ops::SubAssign
+ std::ops::MulAssign
+ std::ops::DivAssign
+ std::ops::RemAssign
+ std::ops::Shl<u32, Output = Self>
+ std::ops::Shr<u32, Output = Self>
+ std::ops::ShlAssign<u32>
+ std::ops::ShrAssign<u32>
+ std::ops::BitAnd<Output = Self>
+ std::ops::BitOr<Output = Self>
+ std::ops::BitXor<Output = Self>
+ std::ops::BitAndAssign
+ std::ops::BitOrAssign
+ std::ops::BitXorAssign
+ std::convert::From<u8>
{
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<Output = Self>
+ std::ops::Sub<Output = Self>
+ std::ops::Neg<Output = Self>
+ std::ops::Mul<Output = Self>
+ std::ops::Div<Output = Self>
+ std::ops::Rem<Output = Self>
+ std::convert::From<i8>
{
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<u128>;
fn parse_u64_rawopt(&self) -> Option<u64>;
fn parse_u32_rawopt(&self) -> Option<u32>;
fn parse_u16_rawopt(&self) -> Option<u16>;
fn parse_u8_rawopt(&self) -> Option<u8>;
}
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::<u128>());
(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::<u64>());
(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::<u128>());
(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::<u64>());
(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::<u64>());
(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<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).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::<u128>());
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::<u64>());
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<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::<u128>());
(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::<u64>());
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<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::<u64>());
(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<u16> {
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<u8> {
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<u8>;
fn parse_uint<U: UPrimInt>(&mut self) -> U {
self.parse_uint_opt().unwrap()
}
fn parse_uint_or_default<U: UPrimInt>(&mut self) -> U {
self.parse_uint_opt().unwrap_or_default()
}
fn parse_uint_opt<U: UPrimInt>(&mut self) -> Option<U>;
fn parse_iint<I: IPrimInt>(&mut self) -> I {
self.parse_iint_opt().unwrap()
}
fn parse_iint_or_default<I: IPrimInt>(&mut self) -> I {
self.parse_iint_opt().unwrap_or_default()
}
fn parse_iint_opt<I: IPrimInt>(&mut self) -> Option<I>;
}
impl<T: Iterator<Item = u8>> ProconParse for T {
fn get_ascii_byte_opt(&mut self) -> Option<u8> {
loop {
match self.next() {
Some(c @ 0x21..=0x7e) => {
return Some(c);
}
Some(_) => continue,
_ => return None,
}
}
}
fn parse_uint_opt<U: UPrimInt>(&mut self) -> Option<U> {
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<I: IPrimInt>(&mut self) -> Option<I> {
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<R: std::io::BufRead> Drop for ProconIBufIter<R> {
/// 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<u8>);
impl ProconWriteBuffer {
pub fn with_capacity(capacity: usize) -> Self {
let mut b = Vec::<u8>::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<U>(&mut self, d: U)
where
U: UPrimInt + std::convert::Into<u128>,
{
proconwritebuf_uint(&mut self.0, d);
}
pub fn uint_sp<U>(&mut self, s: &[U])
where
U: UPrimInt + std::convert::Into<u128>,
{
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<U>(&mut self, s: &[U])
where
U: UPrimInt + std::convert::Into<u128>,
{
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<I>(&mut self, d: I)
where
I: IPrimInt + std::convert::Into<i128>,
{
proconwritebuf_iint(&mut self.0, d);
}
pub fn iint_sp<I>(&mut self, s: &[I])
where
I: IPrimInt + std::convert::Into<i128>,
{
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<I>(&mut self, s: &[I])
where
I: IPrimInt + std::convert::Into<i128> + std::convert::TryInto<u8>,
{
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<W>(&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<U>(p: &mut *mut u8, mut d: U)
where
U: UPrimInt + std::convert::Into<u128>,
{
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<I>(p: &mut *mut u8, mut d: I)
where
I: IPrimInt + std::convert::Into<i128>,
{
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)
};
}
}