結果
| 問題 | No.2494 Sum within Components |
| ユーザー |
 cotton_fn_
|
| 提出日時 | 2023-10-07 20:57:08 |
| 言語 | Rust (1.77.0) |
| 結果 |
AC
|
| 実行時間 | 22 ms / 2,000 ms |
| コード長 | 35,880 bytes |
| コンパイル時間 | 2,967 ms |
| コンパイル使用メモリ | 180,672 KB |
| 実行使用メモリ | 5,364 KB |
| 最終ジャッジ日時 | 2023-10-07 20:57:13 |
| 合計ジャッジ時間 | 3,262 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge12 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,380 KB |
| testcase_01 | AC | 1 ms
4,380 KB |
| testcase_02 | AC | 1 ms
4,376 KB |
| testcase_03 | AC | 1 ms
4,376 KB |
| testcase_04 | AC | 1 ms
4,380 KB |
| testcase_05 | AC | 1 ms
4,380 KB |
| testcase_06 | AC | 1 ms
4,376 KB |
| testcase_07 | AC | 1 ms
4,380 KB |
| testcase_08 | AC | 1 ms
4,380 KB |
| testcase_09 | AC | 2 ms
4,376 KB |
| testcase_10 | AC | 2 ms
4,380 KB |
| testcase_11 | AC | 2 ms
4,380 KB |
| testcase_12 | AC | 3 ms
4,380 KB |
| testcase_13 | AC | 2 ms
4,376 KB |
| testcase_14 | AC | 18 ms
4,532 KB |
| testcase_15 | AC | 17 ms
4,376 KB |
| testcase_16 | AC | 9 ms
4,380 KB |
| testcase_17 | AC | 9 ms
5,296 KB |
| testcase_18 | AC | 10 ms
5,364 KB |
| testcase_19 | AC | 22 ms
5,304 KB |
コンパイルメッセージ
warning: function `find_ws_naive` is never used
--> Main.rs:781:19
|
781 | pub(crate) fn find_ws_naive(s: &[u8]) -> Option<usize> {
| ^^^^^^^^^^^^^
|
= note: `#[warn(dead_code)]` on by default
warning: 1 warning emitted
ソースコード
#![allow(unused_imports)]
use input2::*;
use std::{
collections::*,
io::{self, BufWriter, Read, Write},
};
fn run<I: Read, O: Write>(mut ss: Input<I>, mut out: O) {
let t: u32 = 1;
for _ in 0..t {
case(&mut ss, &mut out);
}
}
fn case<I: Read, O: Write>(ss: &mut Input<I>, mut out: O) {
use modint2::*;
let (n, m): (usize, usize) = ss.input();
let mut dsu =
dsu::DsuMerge::from_iterator(ss.seq(n).map(|x: u32| mint::<998244353>(x)), |x, y| *x += y);
for (u, v) in ss.seq::<(usize, usize)>(m) {
let (u, v) = (u - 1, v - 1);
dsu.unite(u, v);
}
let mut ans = mint(1);
for i in 0..n {
if dsu.is_root(i) {
ans *= dsu.data(i).pow(dsu.size(i));
}
}
wln!(out, "{ans}")
}
fn main() {
let stdin = io::stdin();
let ss = Input::new(stdin.lock());
let stdout = io::stdout();
let out = BufWriter::new(stdout.lock());
run(ss, out);
}
pub mod dsu {
#[derive(Clone)]
pub struct Dsu(Vec<isize>);
impl Dsu {
pub fn new(n: usize) -> Self {
Self(vec![-1; n])
}
pub fn root(&self, mut u: usize) -> usize {
while self.0[u] >= 0 {
u = self.0[u] as usize;
}
u
}
pub fn is_root(&self, u: usize) -> bool {
self.0[u] < 0
}
pub fn unite(&mut self, u: usize, v: usize) -> UniteResult {
let ru = self.root(u);
let rv = self.root(v);
if ru == rv {
return UniteResult {
root: ru,
united_root: None,
size: -self.0[ru] as _,
};
}
let (r, c) = if -self.0[ru] >= -self.0[rv] {
(ru, rv)
} else {
(rv, ru)
};
self.0[r] += self.0[c];
self.0[c] = r as isize;
UniteResult {
root: r,
united_root: Some(c),
size: -self.0[r] as _,
}
}
pub fn is_same(&self, u: usize, v: usize) -> bool {
self.root(u) == self.root(v)
}
pub fn size(&self, u: usize) -> usize {
-self.0[self.root(u)] as usize
}
pub fn reset(&mut self) {
todo!();
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub struct UniteResult {
pub root: usize,
pub united_root: Option<usize>,
pub size: usize,
}
impl UniteResult {
pub fn is_united(&self) -> bool {
self.united_root.is_some()
}
}
use std::mem::ManuallyDrop;
pub struct DsuMerge<T, F> {
inner: Dsu,
data: Vec<ManuallyDrop<T>>,
merge: F,
}
impl<T, F: FnMut(&mut T, T)> DsuMerge<T, F> {
pub fn new(n: usize, init: T, merge: F) -> Self
where
T: Clone,
{
Self::from_iterator((0..n).map(|_| init.clone()), merge)
}
pub fn from_fn(n: usize, init: impl FnMut(usize) -> T, merge: F) -> Self {
Self::from_iterator((0..n).map(init), merge)
}
pub fn from_iterator(iter: impl IntoIterator<Item = T>, merge: F) -> Self {
let data: Vec<_> = iter.into_iter().map(|x| ManuallyDrop::new(x)).collect();
Self {
inner: Dsu::new(data.len()),
data,
merge,
}
}
pub fn root(&self, u: usize) -> usize {
self.inner.root(u)
}
pub fn is_root(&self, u: usize) -> bool {
self.inner.is_root(u)
}
pub fn unite(&mut self, u: usize, v: usize) -> (UniteResult, &mut T) {
let res = self.inner.unite(u, v);
if let Some(c) = res.united_root {
let taken = unsafe { ManuallyDrop::take(&mut self.data[c]) };
(self.merge)(&mut self.data[res.root], taken);
}
(res, &mut self.data[res.root])
}
pub fn is_same(&self, u: usize, v: usize) -> bool {
self.inner.is_same(u, v)
}
pub fn size(&self, u: usize) -> usize {
self.inner.size(u)
}
pub fn data(&self, u: usize) -> &T {
&self.data[self.root(u)]
}
pub fn data_mut(&mut self, u: usize) -> &mut T {
&mut self.data[self.inner.root(u)]
}
}
impl<T, F> Drop for DsuMerge<T, F> {
fn drop(&mut self) {
if std::mem::needs_drop::<T>() {
for (u, data) in self.data.iter_mut().enumerate() {
if self.inner.is_root(u) {
unsafe {
ManuallyDrop::drop(data);
}
}
}
}
}
}
}
pub mod modint2 {
use std::{
cell::{Cell, UnsafeCell},
cmp, fmt,
hash::Hash,
iter,
marker::PhantomData,
ops,
};
#[inline]
pub fn mint<const M: u32>(value: impl Into<ModInt<ConstMod<M>>>) -> ModInt<ConstMod<M>> {
value.into()
}
#[inline]
pub fn var_mint(value: impl Into<ModInt<VarMod>>) -> ModInt<VarMod> {
value.into()
}
pub type Mint<const N: u32> = ModInt<ConstMod<N>>;
pub type VarMint = ModInt<VarMod>;
pub trait Modulo {
fn modulo() -> u32;
#[inline]
fn rem32(x: u32) -> u32 {
x % Self::modulo()
}
#[inline]
fn rem64(x: u64) -> u32 {
(x % Self::modulo() as u64) as u32
}
}
pub struct ConstMod<const M: u32>;
impl<const M: u32> Modulo for ConstMod<M> {
#[inline]
fn modulo() -> u32 {
M
}
}
#[inline]
pub fn set_var_mod(m: u32) {
BarrettReduction::new(m).store_thread();
}
pub struct VarMod;
impl Modulo for VarMod {
#[inline]
fn modulo() -> u32 {
BarrettReduction::load_thread().m
}
#[inline]
fn rem32(x: u32) -> u32 {
Self::rem64(x as u64) as u32
}
#[inline]
fn rem64(x: u64) -> u32 {
BarrettReduction::load_thread().rem(x)
}
}
#[derive(Clone, Copy, Debug)]
struct BarrettReduction {
m: u32,
e: u32,
s: u64,
}
impl BarrettReduction {
#[inline]
pub fn new(m: u32) -> Self {
assert_ne!(m, 0);
assert_ne!(m, 1);
let e = 31 - (m - 1).leading_zeros();
Self {
s: ((1u128 << (64 + e)) / m as u128) as u64 + (!m.is_power_of_two()) as u64,
m,
e,
}
}
#[inline]
pub fn div(&self, x: u64) -> u64 {
((self.s as u128 * x as u128) >> 64) as u64 >> self.e
}
#[inline]
pub fn rem(&self, x: u64) -> u32 {
(x - self.m as u64 * self.div(x)) as u32
}
#[inline]
pub fn store_thread(self) {
BR.with(|br| br.set(self));
}
#[inline]
pub fn load_thread() -> Self {
BR.with(|br| br.get())
}
}
thread_local! { static BR : Cell < BarrettReduction > = Cell :: new (BarrettReduction { m : 0 , s : 0 , e : 0 }) ; }
#[repr(transparent)]
pub struct ModInt<M> {
value: u32,
marker: PhantomData<M>,
}
impl<M> ModInt<M> {
pub const ZERO: Self = Self::unnormalized(0);
#[inline]
pub const fn unnormalized(value: u32) -> Self {
Self {
value,
marker: PhantomData,
}
}
#[inline]
pub const fn get(self) -> u32 {
self.value
}
}
impl<M: Modulo> ModInt<M> {
#[inline]
pub fn new(value: u32) -> Self {
Self::unnormalized(M::rem32(value))
}
#[inline]
pub fn normalize(self) -> Self {
Self::new(self.value)
}
#[inline]
pub fn modulo() -> u32 {
M::modulo()
}
#[inline]
pub fn set<T: Into<ModInt<M>>>(&mut self, value: T) {
*self = value.into();
}
#[inline]
pub fn inv(self) -> Self {
self.pow(M::modulo() - 2)
}
}
impl<M: Modulo> ops::Neg for ModInt<M> {
type Output = Self;
#[inline]
fn neg(self) -> Self::Output {
Self::unnormalized(if self.value == 0 {
0
} else {
M::modulo() - self.value
})
}
}
impl<M: Modulo> ops::Neg for &ModInt<M> {
type Output = ModInt<M>;
#[inline]
fn neg(self) -> Self::Output {
-(*self)
}
}
impl<M: Modulo> ops::Add for ModInt<M> {
type Output = Self;
#[inline]
fn add(self, other: Self) -> Self {
let sum = self.value + other.value;
Self::unnormalized(if sum < M::modulo() {
sum
} else {
sum - M::modulo()
})
}
}
impl<M: Modulo> ops::Sub for ModInt<M> {
type Output = Self;
#[inline]
fn sub(self, other: Self) -> Self {
let (diff, of) = self.value.overflowing_sub(other.value);
Self::unnormalized(if of {
diff.wrapping_add(M::modulo())
} else {
diff
})
}
}
impl<M: Modulo> ops::Mul for ModInt<M> {
type Output = Self;
#[inline]
fn mul(self, other: Self) -> Self {
Self::unnormalized(M::rem64(self.value as u64 * other.value as u64))
}
}
impl<M: Modulo> ops::Div for ModInt<M> {
type Output = Self;
#[inline]
fn div(self, other: Self) -> Self {
self * other.inv()
}
}
macro_rules! binop {
($ Op : ident , $ op : ident , $ OpAssign : ident , $ op_assign : ident) => {
impl<M: Modulo> ops::$Op<&ModInt<M>> for ModInt<M> {
type Output = Self;
#[inline]
fn $op(self, other: &ModInt<M>) -> Self::Output {
self.$op(*other)
}
}
impl<M: Modulo> ops::$Op<ModInt<M>> for &ModInt<M> {
type Output = ModInt<M>;
#[inline]
fn $op(self, other: ModInt<M>) -> Self::Output {
(*self).$op(other)
}
}
impl<M: Modulo> ops::$Op for &ModInt<M> {
type Output = ModInt<M>;
#[inline]
fn $op(self, other: Self) -> Self::Output {
(*self).$op(*other)
}
}
impl<M: Modulo> ops::$OpAssign for ModInt<M> {
#[inline]
fn $op_assign(&mut self, rhs: Self) {
*self = <Self as ops::$Op>::$op(*self, rhs);
}
}
impl<M: Modulo> ops::$OpAssign<&ModInt<M>> for ModInt<M> {
#[inline]
fn $op_assign(&mut self, rhs: &ModInt<M>) {
*self = <Self as ops::$Op>::$op(*self, *rhs);
}
}
};
}
binop!(Add, add, AddAssign, add_assign);
binop!(Sub, sub, SubAssign, sub_assign);
binop!(Mul, mul, MulAssign, mul_assign);
binop!(Div, div, DivAssign, div_assign);
impl<M: Modulo> iter::Sum for ModInt<M> {
fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
let sum = iter.fold(0u64, |acc, x| acc + x.get() as u64);
Self::from(sum)
}
}
impl<M: Modulo> iter::Product for ModInt<M> {
fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
iter.fold(ModInt::new(1), |x, y| x * y)
}
}
macro_rules! fold {
($ Trait : ident , $ f : ident) => {
impl<'a, M: Modulo + 'a> iter::$Trait<&'a ModInt<M>> for ModInt<M> {
fn $f<I: Iterator<Item = &'a ModInt<M>>>(iter: I) -> Self {
<Self as iter::$Trait>::$f(iter.copied())
}
}
};
}
fold!(Sum, sum);
fold!(Product, product);
pub trait Pow<Exp> {
fn pow(self, exp: Exp) -> Self;
}
macro_rules! pow {
($ Uint : ident , $ Int : ident) => {
impl<M: Modulo> Pow<$Uint> for ModInt<M> {
#[inline]
fn pow(self, mut exp: $Uint) -> Self {
let mut res = Self::unnormalized(1);
if exp == 0 {
return res;
}
let mut base = self;
while exp > 1 {
if exp & 1 == 1 {
res *= base;
}
base *= base;
exp >>= 1;
}
res * base
}
}
impl<M: Modulo> Pow<$Int> for ModInt<M> {
#[inline]
fn pow(self, exp: $Int) -> Self {
let p = self.pow(exp.abs() as $Uint);
if exp >= 0 {
p
} else {
p.inv()
}
}
}
};
}
pow!(usize, isize);
pow!(u8, i8);
pow!(u16, i16);
pow!(u32, i32);
pow!(u64, i64);
pow!(u128, i128);
impl<M> Clone for ModInt<M> {
fn clone(&self) -> Self {
*self
}
}
impl<M> Copy for ModInt<M> {}
impl<M> Default for ModInt<M> {
fn default() -> Self {
Self::ZERO
}
}
impl<M> PartialEq for ModInt<M> {
fn eq(&self, other: &Self) -> bool {
self.value == other.value
}
}
impl<M> Eq for ModInt<M> {}
impl<M> PartialOrd for ModInt<M> {
fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
self.value.partial_cmp(&other.value)
}
}
impl<M> Ord for ModInt<M> {
fn cmp(&self, other: &Self) -> cmp::Ordering {
self.value.cmp(&other.value)
}
}
impl<M> Hash for ModInt<M> {
fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
self.value.hash(state)
}
}
impl<M> fmt::Display for ModInt<M> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
fmt::Display::fmt(&self.value, f)
}
}
impl<M> fmt::Debug for ModInt<M> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
fmt::Debug::fmt(&self.value, f)
}
}
impl<M: Modulo> From<u32> for ModInt<M> {
fn from(value: u32) -> Self {
Self::new(value)
}
}
impl<M: Modulo> From<u64> for ModInt<M> {
fn from(value: u64) -> Self {
Self::unnormalized(M::rem64(value))
}
}
impl<M: Modulo> From<u128> for ModInt<M> {
fn from(value: u128) -> Self {
Self::unnormalized((value % M::modulo() as u128) as u32)
}
}
macro_rules! from_small_uint {
($ ty : ident) => {
impl<M: Modulo> From<$ty> for ModInt<M> {
fn from(value: $ty) -> Self {
Self::new(value as u32)
}
}
};
}
from_small_uint!(u8);
from_small_uint!(u16);
impl<M: Modulo> From<usize> for ModInt<M> {
fn from(value: usize) -> Self {
if cfg!(target_pointer_width = "64") {
ModInt::from(value as u64)
} else {
ModInt::from(value as u32)
}
}
}
macro_rules! from_signed {
($ Uint : ident , $ Int : ident) => {
impl<M: Modulo> From<$Int> for ModInt<M> {
fn from(value: $Int) -> Self {
let abs = ModInt::from(value.abs() as $Uint);
if value >= 0 {
abs
} else {
-abs
}
}
}
};
}
from_signed!(usize, isize);
from_signed!(u8, i8);
from_signed!(u16, i16);
from_signed!(u32, i32);
from_signed!(u64, i64);
from_signed!(u128, i128);
pub struct Fact<M>(UnsafeCell<FactInner<M>>);
impl<M: Modulo> Fact<M> {
#[inline]
pub fn new() -> Self {
Self(UnsafeCell::new(FactInner {
fact: vec![],
fact_inv: vec![],
}))
}
#[inline]
pub fn fact(&self, n: usize) -> ModInt<M> {
unsafe { (*self.0.get()).fact(n) }
}
#[inline]
pub fn fact_inv(&self, n: usize) -> ModInt<M> {
unsafe { (*self.0.get()).fact_inv(n) }
}
#[inline]
pub fn binom(&self, n: usize, k: usize) -> ModInt<M> {
if n >= k {
self.fact(n) * self.fact_inv(n - k) * self.fact_inv(k)
} else {
ModInt::unnormalized(0)
}
}
#[inline]
pub fn perm(&self, n: usize, k: usize) -> ModInt<M> {
if n >= k {
self.fact(n) * self.fact_inv(n - k)
} else {
ModInt::unnormalized(0)
}
}
#[inline]
pub fn catalan(&self, n: usize) -> ModInt<M> {
self.fact(2 * n) * self.fact_inv(n + 1) * self.fact_inv(n)
}
}
struct FactInner<M> {
fact: Vec<ModInt<M>>,
fact_inv: Vec<ModInt<M>>,
}
impl<M: Modulo> FactInner<M> {
#[inline]
fn fact(&mut self, n: usize) -> ModInt<M> {
if let Some(&val) = self.fact.get(n) {
val
} else {
self.grow_fact(n)
}
}
fn grow_fact(&mut self, n: usize) -> ModInt<M> {
self.fact.reserve(n + 1 - self.fact.len());
if self.fact.is_empty() {
self.fact.push(ModInt::new(1));
}
unsafe {
let ptr = self.fact.as_mut_ptr();
let mut val = *ptr.add(self.fact.len() - 1);
for i in self.fact.len()..=n {
val *= ModInt::new(i as u32);
*ptr.add(i) = val;
}
self.fact.set_len(n + 1);
val
}
}
#[inline]
fn fact_inv(&mut self, n: usize) -> ModInt<M> {
if let Some(&val) = self.fact_inv.get(n) {
val
} else {
self.grow_fact_inv(n)
}
}
fn grow_fact_inv(&mut self, n: usize) -> ModInt<M> {
self.fact(n);
self.fact_inv.reserve(n + 1 - self.fact_inv.len());
unsafe {
let res = self.fact[n].inv();
let mut val = res;
let ptr = self.fact_inv.as_mut_ptr();
*ptr.add(n) = val;
for i in (self.fact.len()..n).rev() {
val *= ModInt::new(i as u32 + 1);
*ptr.add(i) = val;
}
self.fact_inv.set_len(n + 1);
res
}
}
}
}
pub mod input2 {
use std::{
convert::TryInto,
io::{self, Read},
marker::PhantomData,
mem::{self, MaybeUninit},
ptr, slice,
};
pub struct Input<R> {
src: R,
buf: Vec<u8>,
pos: usize,
len: usize,
}
macro_rules! def_input {
($ ty : ident) => {
pub fn $ty(&mut self) -> $ty {
self.input()
}
};
}
impl<R: Read> Input<R> {
pub fn new(src: R) -> Self {
Self::with_capacity(src, 1 << 20)
}
pub fn with_capacity(src: R, cap: usize) -> Self {
Self {
src,
buf: vec![0; cap],
pos: 0,
len: 0,
}
}
pub fn input<T: Parse>(&mut self) -> T {
T::parse(self)
}
pub fn seq<T: Parse>(&mut self, n: usize) -> Seq<T, R> {
Seq {
src: self,
n,
marker: PhantomData,
}
}
pub fn vec<T: Parse>(&mut self, n: usize) -> Vec<T> {
self.seq(n).collect()
}
pub fn str(&mut self) -> &str {
std::str::from_utf8(self.bytes()).expect("utf8 error")
}
pub fn bytes(&mut self) -> &[u8] {
let range = self.bytes_inner();
unsafe { self.buf.get_unchecked(range) }
}
pub fn bytes_vec(&mut self) -> Vec<u8> {
let range = self.bytes_inner();
if range.start == 0 && 2 * range.end >= self.buf.len() {
let buf_len = self.buf.len();
let mut new_buf = vec![0; buf_len];
new_buf[..self.len].copy_from_slice(self.remaining());
let mut res = mem::replace(&mut self.buf, new_buf);
self.pos = 0;
res.truncate(range.end);
res
} else {
self.buf[range].to_vec()
}
}
#[inline]
fn bytes_inner(&mut self) -> std::ops::Range<usize> {
let mut i = 0;
loop {
if self.len > 0 {
if let Some(d) = find_ws(unsafe {
self.buf.get_unchecked(self.pos + i..self.pos + self.len)
}) {
let del = i + d;
let range = self.pos..self.pos + del;
self.pos += del + 1;
self.len -= del + 1;
if del == 0 {
continue;
}
return range;
}
i = self.len;
}
if self.read() == 0 {
let range = self.pos..self.pos + self.len;
self.pos = 0;
self.len = 0;
return range;
}
}
}
#[cold]
fn read(&mut self) -> usize {
if self.pos != 0 {
self.buf.copy_within(self.pos..self.pos + self.len, 0);
self.pos = 0;
}
if self.len == self.buf.len() {
self.buf.resize((2 * self.buf.len()).max(1 << 13), 0);
}
loop {
match self
.src
.read(unsafe { self.buf.get_unchecked_mut(self.len..) })
{
Ok(n) => {
self.len += n;
return n;
}
Err(e) if e.kind() == io::ErrorKind::WouldBlock => {}
Err(e) => panic!("io error: {}", e),
}
}
}
#[inline]
fn remaining(&self) -> &[u8] {
unsafe { self.buf.get_unchecked(self.pos..self.pos + self.len) }
}
def_input!(usize);
def_input!(u8);
def_input!(u16);
def_input!(u32);
def_input!(u64);
def_input!(isize);
def_input!(i8);
def_input!(i16);
def_input!(i32);
def_input!(i64);
def_input!(f32);
def_input!(f64);
}
#[inline]
pub(crate) fn find_ws_naive(s: &[u8]) -> Option<usize> {
for (i, c) in s.iter().enumerate() {
if *c <= b' ' {
return Some(i);
}
}
None
}
const CHUNK_SIZE: usize = mem::size_of::<usize>();
#[inline]
pub(crate) fn find_ws(s: &[u8]) -> Option<usize> {
let offset = (32 + s.as_ptr().align_offset(CHUNK_SIZE)).min(s.len());
let mut i = 0;
while i < offset {
if s[i] <= b' ' {
return Some(i);
}
i += 1;
}
if i < s.len() {
find_ws_long(s, i)
} else {
None
}
}
fn find_ws_long(s: &[u8], mut i: usize) -> Option<usize> {
while i + CHUNK_SIZE <= s.len() {
if let Some(j) = find_ws_usize(usize::from_le_bytes(
unsafe { s.get_unchecked(i..i + CHUNK_SIZE) }
.try_into()
.unwrap(),
)) {
return Some(i + j);
}
i += CHUNK_SIZE;
}
while i < s.len() {
if s[i] <= b' ' {
return Some(i);
}
i += 1;
}
None
}
#[inline]
fn find_ws_usize(s: usize) -> Option<usize> {
const SUB: usize = 0x2121212121212121;
const MASK: usize = 0x8080808080808080;
let t = s.wrapping_sub(SUB) & MASK;
(t != 0).then(|| (t.trailing_zeros() / 8) as usize)
}
pub struct Seq<'a, T, R> {
src: &'a mut Input<R>,
n: usize,
marker: PhantomData<*const T>,
}
impl<'a, T: Parse, R: Read> Iterator for Seq<'a, T, R> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
if self.n > 0 {
self.n -= 1;
Some(self.src.input())
} else {
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.n, Some(self.n))
}
}
impl<'a, T: Parse, R: Read> ExactSizeIterator for Seq<'a, T, R> {
fn len(&self) -> usize {
self.size_hint().0
}
}
pub trait Parse {
fn parse<T: Read>(src: &mut Input<T>) -> Self;
}
impl Parse for Vec<u8> {
fn parse<T: Read>(src: &mut Input<T>) -> Self {
src.bytes_vec()
}
}
impl Parse for String {
fn parse<T: Read>(src: &mut Input<T>) -> Self {
String::from_utf8(src.bytes_vec()).unwrap()
}
}
pub trait ParseBytes {
fn parse_bytes(s: &[u8]) -> Self;
}
macro_rules! parse_int {
($ ty : ident , $ ity : ident) => {
impl ParseBytes for $ty {
fn parse_bytes(s: &[u8]) -> Self {
$ty(s, 0)
}
}
impl ParseBytes for $ity {
fn parse_bytes(s: &[u8]) -> Self {
let (minus, s) = if let Some((b'-', s)) = s.split_first() {
(true, s)
} else {
(false, s)
};
let x = $ty(s, 0);
(if minus { (!x).wrapping_add(1) } else { x }) as $ity
}
}
};
}
parse_int!(usize, isize);
parse_int!(u8, i8);
parse_int!(u16, i16);
parse_int!(u32, i32);
parse_int!(u64, i64);
macro_rules! parse {
($ ty : ident) => {
impl Parse for $ty {
fn parse<T: Read>(src: &mut Input<T>) -> Self {
Self::parse_bytes(src.bytes())
}
}
};
}
parse!(usize);
parse!(u8);
parse!(u16);
parse!(u32);
parse!(u64);
parse!(isize);
parse!(i8);
parse!(i16);
parse!(i32);
parse!(i64);
parse!(f32);
parse!(f64);
macro_rules ! tuple { ($ ($ T : ident) ,+) => { impl <$ ($ T : Parse) ,+> Parse for ($ ($ T ,) +) { fn parse < T : Read > (src : & mut Input < T >) -> Self { ($ ($ T :: parse (src) ,) +) } } } ; }
tuple!(A);
tuple!(A, B);
tuple!(A, B, C);
tuple!(A, B, C, D);
tuple!(A, B, C, D, E);
tuple!(A, B, C, D, E, F);
tuple!(A, B, C, D, E, F, G);
tuple!(A, B, C, D, E, F, G, H);
impl<T: Parse, const N: usize> Parse for [T; N] {
fn parse<R: Read>(src: &mut Input<R>) -> Self {
struct Guard<T> {
ptr: *mut T,
i: usize,
}
impl<T> Drop for Guard<T> {
fn drop(&mut self) {
unsafe {
ptr::drop_in_place(slice::from_raw_parts_mut(self.ptr, self.i));
}
}
}
let mut res: MaybeUninit<[T; N]> = MaybeUninit::uninit();
let mut g = Guard {
ptr: res.as_mut_ptr() as *mut T,
i: 0,
};
unsafe {
while g.i < N {
g.ptr.add(g.i).write(src.input());
g.i += 1;
}
mem::forget(g);
res.assume_init()
}
}
}
#[inline]
fn toi8bytes(s: &[u8]) -> (u32, &[u8]) {
let (p, rest) = s.split_at(8);
let x = u64::from_le_bytes(p.try_into().unwrap());
const MASK1: u64 = 0x000f000f000f000f;
let hi = (x >> 8) & MASK1;
let lo = x & MASK1;
let x = 10 * lo + hi;
const MASK2: u64 = 0x0000ffff0000ffff;
let hi = (x >> 16) & MASK2;
let lo = x & MASK2;
let x = 100 * lo + hi;
let hi = (x >> 32) as u32;
let lo = x as u32;
let x = 10000 * lo + hi;
(x, rest)
}
#[inline]
fn toi4bytes(s: &[u8]) -> (u32, &[u8]) {
let (p, rest) = s.split_at(4);
let x = u32::from_le_bytes(p.try_into().unwrap());
const MASK: u32 = 0x000f000f;
let hi = (x >> 8) & MASK;
let lo = x & MASK;
let x = 10 * lo + hi;
let hi = x >> 16;
let lo = x & 0x0000ffff;
let x = 100 * lo + hi;
(x, rest)
}
#[cfg(target_pointer_width = "32")]
fn usize(s: &[u8], pre: usize) -> usize {
u32(s, pre as u32) as usize
}
#[cfg(target_pointer_width = "64")]
fn usize(s: &[u8], pre: usize) -> usize {
u64(s, pre as u64) as usize
}
#[inline]
fn u64(mut s: &[u8], pre: u64) -> u64 {
let mut res = pre;
while s.len() >= 8 {
let (x, rest) = toi8bytes(s);
res = 100000000 * res + x as u64;
s = rest;
}
if s.len() >= 4 {
let (x, rest) = toi4bytes(s);
res = 10000 * res + x as u64;
s = rest;
}
for &c in s {
res = 10 * res + (c & 0xf) as u64;
}
res
}
#[inline]
fn u32(mut s: &[u8], pre: u32) -> u32 {
let mut res = pre;
if s.len() >= 8 {
let (x, rest) = toi8bytes(s);
res = x;
s = rest;
}
if s.len() >= 4 {
let (x, rest) = toi4bytes(s);
res = 10000 * res + x;
s = rest;
}
for &c in s {
res = 10 * res + (c & 0xf) as u32;
}
res
}
#[inline]
fn u16(mut s: &[u8], pre: u16) -> u16 {
let mut res = pre;
if s.len() >= 4 {
let (x, rest) = toi4bytes(s);
res = 10000 * res + x as u16;
s = rest;
}
for &c in s {
res = 10 * res + (c & 0xf) as u16;
}
res
}
#[inline]
fn u8(s: &[u8], pre: u8) -> u8 {
let mut res = pre;
for &c in s {
res = 10 * res + (c & 0xf);
}
res
}
macro_rules! float {
($ ty : ident , $ uty : ident) => {
impl ParseBytes for $ty {
fn parse_bytes(s: &[u8]) -> Self {
const TEN: [$ty; 18] = [
1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13,
1e14, 1e15, 1e16, 1e17,
];
let (minus, s) = if let Some((b'-', s)) = s.split_first() {
(true, s)
} else {
(false, s)
};
let (int, fract) = if let Some(p) = s.iter().position(|c| *c == b'.') {
(&s[..p], &s[p + 1..])
} else {
(s, &s[..0])
};
let x = $uty(int, 0);
let x = if fract.is_empty() {
x as $ty
} else {
let ten = TEN
.get(fract.len())
.copied()
.unwrap_or_else(|| $ty::powi(10.0, fract.len() as _));
$uty(fract, x) as $ty / ten
};
if minus {
-x
} else {
x
}
}
}
};
}
float!(f32, u32);
float!(f64, u64);
impl Parse for char {
fn parse<T: Read>(src: &mut Input<T>) -> Self {
let s = src.str();
let mut cs = s.chars();
match cs.next() {
Some(c) if cs.as_str().is_empty() => c,
_ => panic!("input is not single char"),
}
}
}
pub struct Byte(pub u8);
impl Parse for Byte {
fn parse<T: Read>(src: &mut Input<T>) -> Self {
if let [b] = src.bytes() {
Byte(*b)
} else {
panic!("input is not single byte")
}
}
}
}
pub mod macros {
extern "C" {
pub fn isatty(fd: i32) -> i32;
}
#[macro_export]
macro_rules ! w { ($ dst : expr , $ ($ arg : tt) *) => { if cfg ! (debug_assertions) && unsafe { $ crate :: macros :: isatty (1) } != 0 { write ! ($ dst , "\x1B[1;33m") . unwrap () ; write ! ($ dst , $ ($ arg) *) . unwrap () ; write ! ($ dst , "\x1B[0m") . unwrap () ; } else { write ! ($ dst , $ ($ arg) *) . unwrap () ; } } }
#[macro_export]
macro_rules ! wln { ($ dst : expr $ (, $ ($ arg : tt) *) ?) => { { if cfg ! (debug_assertions) && unsafe { $ crate :: macros :: isatty (1) } != 0 { write ! ($ dst , "\x1B[1;33m") . unwrap () ; writeln ! ($ dst $ (, $ ($ arg) *) ?) . unwrap () ; write ! ($ dst , "\x1B[0m") . unwrap () ; } else { writeln ! ($ dst $ (, $ ($ arg) *) ?) . unwrap () ; } # [cfg (debug_assertions)] $ dst . flush () . unwrap () ; } } }
#[macro_export]
macro_rules! w_iter {
($ dst : expr , $ fmt : expr , $ iter : expr , $ delim : expr) => {{
let mut first = true;
for elem in $iter {
if first {
w!($dst, $fmt, elem);
first = false;
} else {
w!($dst, concat!($delim, $fmt), elem);
}
}
}};
($ dst : expr , $ fmt : expr , $ iter : expr) => {
w_iter!($dst, $fmt, $iter, " ")
};
}
#[macro_export]
macro_rules ! w_iter_ln { ($ dst : expr , $ ($ t : tt) *) => { { w_iter ! ($ dst , $ ($ t) *) ; wln ! ($ dst) ; } } }
#[macro_export]
macro_rules ! e { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprint ! ($ ($ t) *) } }
#[macro_export]
macro_rules ! eln { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprintln ! ($ ($ t) *) } }
#[macro_export]
#[doc(hidden)]
macro_rules ! __tstr { ($ h : expr $ (, $ t : expr) +) => { concat ! (__tstr ! ($ ($ t) ,+) , ", " , __tstr ! (@)) } ; ($ h : expr) => { concat ! (__tstr ! () , " " , __tstr ! (@)) } ; () => { "\x1B[94m[{}:{}]\x1B[0m" } ; (@) => { "\x1B[1;92m{}\x1B[0m = {:?}" } }
#[macro_export]
macro_rules ! d { ($ ($ a : expr) ,*) => { if std :: env :: var ("ND") . map (| v | & v == "0") . unwrap_or (true) { eln ! (__tstr ! ($ ($ a) ,*) , file ! () , line ! () , $ (stringify ! ($ a) , $ a) ,*) ; } } ; }
}