結果
| 問題 | No.2417 Div Count |
| ユーザー |
 Sarievo
|
| 提出日時 | 2023-08-12 13:50:41 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 8 ms / 2,000 ms |
| コード長 | 48,213 bytes |
| コンパイル時間 | 13,009 ms |
| コンパイル使用メモリ | 378,200 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-19 16:23:08 |
| 合計ジャッジ時間 | 14,341 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 41 |
ソースコード
// {{{ My social:
// YouTube: https://www.youtube.com/@Sarievo
// SoundCloud: https://soundcloud.com/sarievo
// Twitter: https://www.twitter.com/sarievo
// }}}
fn solve() {
prepare!();
sc!(n, k);
let mut res = 0;
let e = n - k;
let mut i = 1;
while i * i <= e {
// dg!(i * i);
if e % i == 0 {
if i > k {
res += 1;
}
if e / i > k && e / i != i {
res += 1;
}
}
i += 1;
}
out!(res);
}
// <><><><> Lib Codes <><><><>
#[allow(unused)]
use sarievo::{
segtree::{
identity::*,
monoid_actions::{Additive, Max, Min},
Segtree, Segtree2D,
},
*,
};
#[allow(unused_imports)]
use std::{
cmp::{max, min, Ordering, Reverse},
collections::{
btree_map, hash_map, BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque,
},
vec,
};
// {{{ Lib Codes
mod sarievo {
use super::*;
// {{{ Range
pub fn get_range<R: std::ops::RangeBounds<usize>>(range: R, n: usize) -> (usize, usize) {
use std::ops::Bound::*; // https://doc.rust-lang.org/stable/std/ops/enum.Bound.html
let l = match range.start_bound() {
Included(l) => *l,
Excluded(l) => l + 1,
Unbounded => 0,
};
let r = match range.end_bound() {
Included(r) => r + 1,
Excluded(r) => *r,
Unbounded => n,
};
(l, r)
}
// }}}
// {{{ Segment Tree
#[allow(unused)]
pub mod segtree {
use super::*;
// {{{ Identity
use self::identity::*;
pub mod identity {
// Additive Identity
pub trait Zero: Sized {
fn zero() -> Self;
}
// Multiplicative Identity
pub trait One: Sized {
fn one() -> Self;
}
#[macro_export]
macro_rules! zero_one_impls {
($({$Trait:ident $method:ident $($t:ty)*, $e:expr})*)=>{
$($(impl $Trait for $t{fn $method() -> Self { $e } })*)*
};
}
zero_one_impls! (
{Zero zero u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128, 0} {Zero zero f32 f64, 0.}
{One one u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128, 1} {One one f32 f64, 1.}
);
// Associative Identity
pub trait Bounded: Sized {
fn maximum() -> Self;
fn minimum() -> Self;
}
macro_rules! bounded_num_impls {
($($t:ident)*)=>{
$(impl Bounded for$t{
fn maximum() -> Self { std::$t::MAX }
fn minimum() -> Self { std::$t::MIN }
})*
};
}
bounded_num_impls!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize f32 f64);
}
// }}}
// {{{ Magma
use self::magma::*;
pub mod magma {
pub trait Magma {
type T: Clone;
fn operate(x: &Self::T, y: &Self::T) -> Self::T;
}
pub trait Associative {}
pub trait Semigroup: Magma + Associative {}
impl<S: Magma + Associative> Semigroup for S {}
pub trait Unital: Magma {
fn unit() -> Self::T;
}
pub trait Monoid: Semigroup + Unital {
#[doc = " Binary Exponentiation: xⁿ = x × × x"]
fn pow(mut x: Self::T, mut n: usize) -> Self::T {
let mut ret = Self::unit();
while n > 0 {
if n & 1 == 1 {
ret = Self::operate(&ret, &x);
}
x = Self::operate(&x, &x);
n >>= 1;
}
ret
}
}
impl<M: Semigroup + Unital> Monoid for M {}
}
pub mod monoid_actions {
use super::*;
use std::{marker::PhantomData, ops::Add};
pub struct Additive<T: Clone + Zero + Add<Output = T>>(PhantomData<fn() -> T>);
impl<T: Clone + Zero + Add<Output = T>> Magma for Additive<T> {
type T = T;
#[inline]
fn operate(x: &Self::T, y: &Self::T) -> Self::T {
x.clone() + y.clone()
}
}
impl<T: Clone + Zero + Add<Output = T>> Unital for Additive<T> {
#[inline]
fn unit() -> Self::T {
Zero::zero()
}
}
impl<T: Clone + Zero + Add<Output = T>> Associative for Additive<T> {}
pub struct Max<T: Clone + Bounded + Ord>(PhantomData<fn() -> T>);
impl<T: Clone + Bounded + Ord> Magma for Max<T> {
type T = T;
#[inline]
fn operate(x: &Self::T, y: &Self::T) -> Self::T {
x.max(y).clone()
}
}
impl<T: Clone + Bounded + Ord> Unital for Max<T> {
#[inline]
fn unit() -> Self::T {
Bounded::minimum()
}
}
impl<T: Clone + Bounded + Ord> Associative for Max<T> {}
pub struct Min<T: Clone + Bounded + Ord>(PhantomData<fn() -> T>);
impl<T: Clone + Bounded + Ord> Magma for Min<T> {
type T = T;
#[inline]
fn operate(x: &Self::T, y: &Self::T) -> Self::T {
x.min(y).clone()
}
}
impl<T: Clone + Bounded + Ord> Unital for Min<T> {
#[inline]
fn unit() -> Self::T {
Bounded::maximum()
}
}
impl<T: Clone + Bounded + Ord> Associative for Min<T> {}
}
// }}}
// {{{ Segtree
#[derive(Clone, Debug)]
pub struct Segtree<M: Monoid> {
n: usize,
tree: Vec<M::T>,
}
impl<M: Monoid> From<Vec<M::T>> for Segtree<M> {
fn from(v: Vec<M::T>) -> Self {
let n = v.len();
let mut tree = vec![M::unit(); n * 2];
tree[n..].clone_from_slice(&v);
for i in (1..n).rev() {
tree[i] = M::operate(&tree[i << 1], &tree[i << 1 | 1]);
}
Self { n, tree }
}
}
impl<M: Monoid> Segtree<M> {
pub fn new(n: usize) -> Self {
vec![M::unit(); n].into()
}
fn __propagate(&mut self, mut k: usize) {
k >>= 1;
while k > 0 {
self.tree[k] = M::operate(&self.tree[k << 1], &self.tree[k << 1 | 1]);
k >>= 1;
}
}
pub fn assign(&mut self, mut k: usize, x: M::T) {
k += self.n;
self.tree[k] = x;
self.__propagate(k);
}
pub fn update(&mut self, mut k: usize, x: M::T) {
k += self.n;
self.tree[k] = M::operate(&self.tree[k], &x);
self.__propagate(k);
}
pub fn get(&self, k: usize) -> M::T {
self.tree[k + self.n].clone()
}
pub fn fold<R>(&self, range: R) -> M::T
where
R: std::ops::RangeBounds<usize>,
{
let (l, r) = get_range(range, self.n);
let mut l = l + self.n;
let mut r = r + self.n;
let mut lv = M::unit();
let mut rv = M::unit();
while l < r {
if l & 1 != 0 {
lv = M::operate(&lv, &self.tree[l]);
l += 1;
}
if r & 1 != 0 {
r -= 1;
rv = M::operate(&self.tree[r], &rv)
}
l >>= 1;
r >>= 1;
}
M::operate(&lv, &rv)
}
pub fn len(&self) -> usize {
self.n
}
}
// }}}
// {{{ Segtree 2D
#[derive(Clone)]
pub struct Segtree2D<M: Monoid> {
n: usize,
m: usize,
pub trees: Vec<Segtree<M>>,
}
#[allow(unused)]
impl<M: Monoid> Segtree2D<M> {
pub fn new(n: usize, m: usize) -> Self {
let mut trees = Vec::with_capacity(n * 2);
for _ in 0..n * 2 {
trees.push(Segtree::<M>::new(m));
}
Segtree2D { n, m, trees }
}
fn __propagate(&mut self, mut i: usize, j: usize) {
i >>= 1;
while i > 0 {
let left = self.trees[i << 1].get(j);
let right = self.trees[i << 1 | 1].get(j);
self.trees[i].assign(j, M::operate(&left, &right));
i >>= 1;
}
}
pub fn assign(&mut self, mut i: usize, j: usize, x: M::T) {
debug_assert!(i < self.n);
i += self.n;
self.trees[i].assign(j, x);
self.__propagate(i, j);
}
pub fn update(&mut self, mut i: usize, j: usize, x: M::T) {
debug_assert!(i < self.n);
i += self.n;
self.trees[i].update(j, x);
self.__propagate(i, j);
}
pub fn get(&mut self, i: usize, j: usize) -> M::T {
self.trees[i + self.n].get(j)
}
pub fn fold<R>(&self, r_range: R, c_range: R) -> M::T
where
R: std::ops::RangeBounds<usize> + Clone,
{
let (rx, ry) = get_range(r_range, self.n);
let mut rx = rx + self.n;
let mut ry = ry + self.n;
let mut vx = M::unit();
let mut vy = M::unit();
while rx < ry {
if rx & 1 != 0 {
vx = M::operate(&vx, &self.trees[rx].fold(c_range.clone()));
rx += 1;
}
if ry & 1 != 0 {
ry -= 1;
vy = M::operate(&self.trees[ry].fold(c_range.clone()), &vy);
}
rx >>= 1;
ry >>= 1;
}
M::operate(&vx, &vy)
}
}
// }}}
}
// }}}
// {{{ Graph
#[allow(unused)]
pub struct DenseGraph {
pub n: usize,
pub m: usize,
pub visited: Vec<Vec<bool>>,
}
#[allow(unused)]
impl DenseGraph {
pub const DX: [isize; 8] = [-1, 0, 1, 0, 1, 1, -1, -1];
pub const DY: [isize; 8] = [0, -1, 0, 1, 1, -1, -1, 1];
pub const DC: [char; 8] = ['U', 'L', 'D', 'R', '↘', '↙', '↖', '↗'];
pub fn new(n: usize, m: usize) -> Self {
let mut visited = vec![vec![false; n + 2]; m + 2];
// boundary init
for i in 0..n + 2 {
visited[i][0] = true;
visited[i][m + 1] = true;
}
for j in 0..m + 2 {
visited[0][j] = true;
visited[n + 1][j] = true;
}
DenseGraph { n, m, visited }
}
pub fn next(&self, coord: (usize, usize), i: usize) -> (usize, usize) {
(
(coord.0 as isize + DenseGraph::DX[i]) as usize,
(coord.1 as isize + DenseGraph::DY[i]) as usize,
)
}
}
// }}}
// {{{ Disjoint Union Set
#[allow(dead_code)]
pub struct DSU {
n: usize,
size: Vec<usize>,
link: Vec<usize>,
}
#[allow(unused)]
impl DSU {
pub fn new(n: usize) -> Self {
DSU {
n,
size: vec![1usize; n],
link: (0..n).collect::<Vec<usize>>(),
}
}
pub fn find(&self, mut x: usize) -> usize {
while x != self.link[x] {
x = self.link[x];
}
x
}
pub fn same(&self, a: usize, b: usize) -> bool {
self.find(a) == self.find(b)
}
pub fn merge(&mut self, mut a: usize, mut b: usize) -> bool {
a = self.find(a);
b = self.find(b);
if a == b {
return false;
}
let (a, b) = if self.size[a] < self.size[b] {
(b, a)
} else {
(a, b)
};
self.size[a] += self.size[b];
self.size[b] = 0;
self.link[b] = a;
true
}
}
// }}}
// {{{ chmin / chmax
#[allow(unused)]
pub fn chmax<T: Clone + PartialOrd>(x: &mut T, y: &T) -> bool {
if *x < *y {
x.clone_from(y);
true
} else {
false
}
}
#[allow(unused)]
pub fn chmin<T: Clone + PartialOrd>(x: &mut T, y: &T) -> bool {
if *x > *y {
x.clone_from(y);
true
} else {
false
}
}
#[allow(unused)]
#[macro_export]
macro_rules! max {
($x:expr) => ($x);
($x:expr, $($tail:expr),+) => { std::cmp::max($x, max!($($tail),+)) }
}
#[allow(unused)]
#[macro_export]
macro_rules! min {
($x:expr) => ($x);
($x:expr, $($tail:expr),+) => { std::cmp::min($x, min!($($tail),+)) }
}
// }}}
// {{{ Press
#[allow(unused)]
pub fn press<T: PartialEq>(a: Vec<T>) -> Vec<(T, usize)> {
let mut ret: Vec<(T, usize)> = vec![];
for x in a.into_iter() {
if ret.is_empty() || ret.last().unwrap().0 != x {
ret.push((x, 1));
} else {
ret.last_mut().unwrap().1 += 1;
}
}
return ret;
}
// }}}
// {{{ Next Permutation
#[allow(unused)]
pub fn next_permutation<T: Ord + PartialOrd>(nums: &mut Vec<T>) -> bool {
use std::cmp::Ordering;
let last_ascending = match nums.windows(2).rposition(|w| w[0] < w[1]) {
Some(i) => i,
None => {
nums.reverse();
return false;
}
};
let swap_with = nums[last_ascending + 1..]
.binary_search_by(|n| T::cmp(&nums[last_ascending], n).then(Ordering::Less))
.unwrap_err();
nums.swap(last_ascending, last_ascending + swap_with);
nums[last_ascending + 1..].reverse();
true
}
// }}}
// {{{ kth
pub trait Kth {
fn kth(&self, k: usize) -> Option<usize>;
}
impl Kth for Segtree<Additive<usize>> {
fn kth(&self, k: usize) -> Option<usize> {
let mut l = 0;
let mut r = self.len() - 1;
let mut ret = None;
while l <= r {
let m = (l + r) >> 1;
if self.fold(..=m) > k {
ret = Some(m);
if m == 0 {
break;
}
r = m - 1;
} else {
l = m + 1;
}
}
ret
}
}
//}}}
// {{{ Entry API
pub trait CustomEntry<T: Ord> {
fn dec_key(&mut self, key: T) -> bool;
}
impl<T: Ord> CustomEntry<T> for BTreeMap<T, usize> {
fn dec_key(&mut self, key: T) -> bool {
match self.entry(key) {
btree_map::Entry::Occupied(mut entry) => {
if *entry.get() > 1 {
*entry.get_mut() -= 1;
} else {
entry.remove();
}
true
}
_ => false,
}
}
}
// }}}
}
// }}}
// <><><> More Lib Codes <><><>
crate::main!();
pub use iter_print::IterPrint;
pub use scanner::*;
// {{{ 内脏
// {{{ Main Macros
mod main_macros {
#[doc = " - `prepare!();`: default (all input scanner (`sc!`, `sv!`) + buf print (`out!`, `dg!`))"]
#[doc = " - `prepare!(?);`: interactive (line scanner (`scln!`) + buf print (`out!`, `dg!`))"]
#[macro_export]
macro_rules! prepare {
(@output($dol:tt)) => {
#[allow(unused_imports)]
use std::io::Write as _;
let __out=std::io::stdout();
#[allow(unused_mut,unused_variables)]
let mut __out=std::io::BufWriter::new(__out.lock());
#[allow(unused_macros)]
#[doc=" [`iter_print!`] for buffered stdout."]
macro_rules! out {
($dol($dol t:tt)*) => {
$dol crate::iter_print!(__out, $dol($dol t)*)
}
}
// error output
#[cfg(debug_assertions)]
#[allow(unused_macros)]
#[doc=" [`iter_print!`] for buffered stderr. Do nothing in release mode."]
macro_rules! dg {
($dol($dol t:tt)*) => {{
#[allow(unused_imports)]
use std::io::Write as _;
let __err = std::io::stderr();
#[allow(unused_mut, unused_variables)]
let mut __err = std::io::BufWriter::new(__err.lock());
$dol crate::iter_print!(__err, $dol($dol t)*);
let _ = __err.flush();
}}
}
#[cfg(not(debug_assertions))]
#[allow(unused_macros)]
#[doc=" [`iter_print!`] for buffered stderr. Do nothing in release mode."]
macro_rules! dg { ($dol($dol t:tt)*) => {} }
};
(@normal($dol:tt)) => {
let __in_buf = read_stdin_all_unchecked();
#[allow(unused_mut, unused_variables)]
let mut __scanner = Scanner::new(&__in_buf);
// two modes for scanning a value
#[allow(unused_macros)]
macro_rules! sc {
($dol($dol t:tt)*) => {
$dol crate::scan!(__scanner, $dol($dol t)*)
}
}
#[allow(unused_macros)]
macro_rules! sv {
($dol($dol t:tt)*) => {
$dol crate::scan_value!(__scanner, $dol($dol t)*)
}
}
};
(@interactive($dol:tt)) => {
#[allow(unused_macros)]
#[doc=" Scan a line, and previous line will be truncated in the next call."]
macro_rules!scln{
($dol($dol t:tt)*) => {
let __in_buf = read_stdin_line();
#[allow(unused_mut, unused_variables)]
let mut __scanner = Scanner::new(&__in_buf);
$dol crate::scan!(__scanner, $dol($dol t)*)
}
}
};
() => {
$crate::prepare!(@output($));
$crate::prepare!(@normal($))
};
(?) => {
$crate::prepare!(@output($));
$crate::prepare!(@interactive($))
};
}
// 3 modes for initializing the main class
#[macro_export]
macro_rules! main {
() => {
fn main() {
solve();
}
};
(avx2) => {
fn main() {
#[target_feature(enable = "avx2")]
unsafe fn solve_avx2() {
solve();
}
unsafe { solve_avx2() }
}
};
(large_stack) => {
fn main() {
const STACK_SIZE: usize = 512 * 1024 * 1024;
::std::thread::Builder::new()
.stack_size(STACK_SIZE)
.spawn(solve)
.unwrap()
.join()
.unwrap();
}
};
}
}
// }}}
// {{{ IterPrint
mod iter_print {
use std::{
fmt::Display,
io::{Error, Write},
};
pub trait IterPrint {
fn iter_print<W, S>(self, writer: &mut W, sep: S, is_head: bool) -> Result<(), Error>
where
W: Write,
S: Display;
}
macro_rules! iter_print_tuple_impl {
(@impl$($A:ident$a:ident)?,$($B:ident$b:ident)*)=>{
impl<$($A,)?$($B),*>IterPrint for($($A,)?$($B),*)where$($A:Display,)?$($B:Display),*{
#[allow(unused_variables)]
fn iter_print<W,S>(self,writer:&mut W,sep:S,is_head:bool)->Result<(),Error>
where W:Write,S:Display{
let($($a,)?$($b,)*)=self;
$(if is_head { ::std::write!(writer,"{}",$a)?; } else { ::std::write!(writer,"{}{}",sep,$a)?; })?
$(::std::write!(writer,"{}{}",sep,$b)?;)*Ok(())
}
}
};
(@inc,,$C:ident$c:ident$($D:ident$d:ident)*)=>{
iter_print_tuple_impl!(@impl,);
iter_print_tuple_impl!(@inc$C$c,,$($D$d)*);
};
(@inc$A:ident$a:ident,$($B:ident$b:ident)*,$C:ident$c:ident$($D:ident$d:ident)*)=>{
iter_print_tuple_impl!(@impl$A$a,$($B$b)*);
iter_print_tuple_impl!(@inc$A$a,$($B$b)*$C$c,$($D$d)*);
};
(@inc$A:ident$a:ident,$($B:ident$b:ident)*,)=>{
iter_print_tuple_impl!(@impl$A$a,$($B$b)*);
};
($($t:tt)*)=>{
iter_print_tuple_impl!(@inc,,$($t)*);
};
}
iter_print_tuple_impl!(A a B b C c D d E e F f G g H h I i J j K k);
#[doc = " Print expressions with a separator."]
#[doc = " - `iter_print!(writer, args...)`"]
#[doc = " - `@sep $expr`: set separator (default: `' '`)"]
#[doc = " - `@ns`: alias for `@sep \"\"`"]
#[doc = " - `@lf`: alias for `@sep '\\n'`"]
#[doc = " - `@sp`: alias for `@sep ' '`"]
#[doc = " - `@fmt ($lit, $($expr),*)`: print `format!($lit, $($expr),*)`"]
#[doc = " - `@flush`: flush writer (auto insert `!`)"]
#[doc = " - `@it $expr`: print iterator"]
#[doc = " - `@it1 $expr`: print iterator as 1-indexed"]
#[doc = " - `@cw ($char $expr)`: print iterator as `(elem as u8 + $char as u8) as char`"]
#[doc = " - `@bw ($byte $expr)`: print iterator as `(elem as u8 + $byte) as char`"]
#[doc = " - `@it2d $expr`: print 2d-iterator"]
#[doc = " - `@tup $expr`: print tuple (need to import [`IterPrint`])"]
#[doc = " - `@ittup $expr`: print iterative tuple (need to import [`IterPrint`])"]
#[doc = " - `$expr`: print expr"]
#[doc = " - `{ args... }`: scoped"]
#[doc = " - `;`: print `'\\n'`"]
#[doc = " - `!`: not print `'\\n'` at the end"]
#[macro_export]
macro_rules! iter_print {
(@@fmt$writer:expr,$sep:expr,$is_head:expr,($lit:literal$(,$e:expr)*$(,)?))=>{
if!$is_head{::std::write!($writer,"{}",$sep).expect("io error");}
::std::write!($writer,$lit,$($e),*).expect("io error");
};
(@@item$writer:expr,$sep:expr,$is_head:expr,$e:expr)=>{
$crate::iter_print!(@@fmt$writer,$sep,$is_head,("{}",$e));
};
(@@line_feed$writer:expr$(,)?)=>{
::std::writeln!($writer).expect("io error");
};
(@@it$writer:expr,$sep:expr,$is_head:expr,$iter:expr)=>{{
let mut iter=$iter.into_iter();
if let Some(item)=iter.next(){
$crate::iter_print!(@@item$writer,$sep,$is_head,item);
}
for item in iter{
$crate::iter_print!(@@item$writer,$sep,false,item);
}
}};
(@@it1$writer:expr,$sep:expr,$is_head:expr,$iter:expr)=>{{
let mut iter=$iter.into_iter();
if let Some(item)=iter.next(){
$crate::iter_print!(@@item$writer,$sep,$is_head,item+1);
}
for item in iter{
$crate::iter_print!(@@item$writer,$sep,false,item+1);
}
}};
(@@cw$writer:expr,$sep:expr,$is_head:expr,($ch:literal$iter:expr))=>{{
let mut iter=$iter.into_iter();
let b=$ch as u8;
if let Some(item)=iter.next(){
$crate::iter_print!(@@item$writer,$sep,$is_head,(item as u8+b)as char);
}
for item in iter{
$crate::iter_print!(@@item$writer,$sep,false,(item as u8+b)as char);
}
}};
(@@bw$writer:expr,$sep:expr,$is_head:expr,($b:literal$iter:expr))=>{{
let mut iter=$iter.into_iter();
let b:u8=$b;
if let Some(item)=iter.next(){
$crate::iter_print!(@@item$writer,$sep,$is_head,(item as u8+b)as char);
}
for item in iter{
$crate::iter_print!(@@item$writer,$sep,false,(item as u8+b)as char);
}
}};
(@@it2d$writer:expr,$sep:expr,$is_head:expr,$iter:expr)=>{
let mut iter=$iter.into_iter();
if let Some(item)=iter.next(){
$crate::iter_print!(@@it$writer,$sep,$is_head,item);
}
for item in iter{
$crate::iter_print!(@@line_feed$writer);
$crate::iter_print!(@@it$writer,$sep,true,item);
}
};
(@@tup$writer:expr,$sep:expr,$is_head:expr,$tuple:expr)=>{
IterPrint::iter_print($tuple,&mut$writer,$sep,$is_head).expect("io error");
};
(@@ittup$writer:expr,$sep:expr,$is_head:expr,$iter:expr)=>{
let mut iter=$iter.into_iter();
if let Some(item)=iter.next(){
$crate::iter_print!(@@tup$writer,$sep,$is_head,item)
}
for item in iter{
$crate::iter_print!(@@line_feed$writer);
$crate::iter_print!(@@tup$writer,$sep,true,item);
}
};
(@@assert_tag item)=>{};
(@@assert_tag it)=>{};
(@@assert_tag it1)=>{};
(@@assert_tag it2d)=>{};
(@@assert_tag tup)=>{};
(@@assert_tag ittup)=>{};
(@@assert_tag$tag:ident)=>{
::std::compile_error!(::std::concat!("invalid tag in `iter_print!`: `",std::stringify!($tag),"`"));
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,@sep$e:expr,$($t:tt)*)=>{
$crate::iter_print!(@@inner$writer,$e,$is_head,$($t)*);
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,@ns$($t:tt)*)=>{
$crate::iter_print!(@@inner$writer,"",$is_head,$($t)*);
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,@lf$($t:tt)*)=>{
$crate::iter_print!(@@inner$writer,'\n',$is_head,$($t)*);
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,@sp$($t:tt)*)=>{
$crate::iter_print!(@@inner$writer,' ',$is_head,$($t)*);
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,@flush$($t:tt)*)=>{
$writer.flush().expect("io error");
$crate::iter_print!(@@inner$writer,$sep,$is_head,!$($t)*);
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,@fmt$arg:tt$($t:tt)*)=>{
$crate::iter_print!(@@fmt$writer,$sep,$is_head,$arg);
$crate::iter_print!(@@inner$writer,$sep,$is_head,$($t)*);
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,@cw$arg:tt$($t:tt)*)=>{
$crate::iter_print!(@@cw$writer,$sep,$is_head,$arg);
$crate::iter_print!(@@inner$writer,$sep,$is_head,$($t)*);
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,@bw$arg:tt$($t:tt)*)=>{
$crate::iter_print!(@@bw$writer,$sep,$is_head,$arg);
$crate::iter_print!(@@inner$writer,$sep,$is_head,$($t)*);
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,@$tag:ident$e:expr,$($t:tt)*)=>{
$crate::iter_print!(@@assert_tag$tag);
$crate::iter_print!(@@$tag$writer,$sep,$is_head,$e);
$crate::iter_print!(@@inner$writer,$sep,false,$($t)*);
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,@$tag:ident$e:expr;$($t:tt)*)=>{
$crate::iter_print!(@@assert_tag$tag);
$crate::iter_print!(@@$tag$writer,$sep,$is_head,$e);
$crate::iter_print!(@@line_feed$writer);
$crate::iter_print!(@@inner$writer,$sep,true,$($t)*);
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,@$tag:ident$e:expr)=>{
$crate::iter_print!(@@assert_tag$tag);
$crate::iter_print!(@@$tag$writer,$sep,$is_head,$e);
$crate::iter_print!(@@inner$writer,$sep,false,);
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,@$tag:ident$($t:tt)*)=>{
::std::compile_error!(::std::concat!("invalid expr in `iter_print!`: `",std::stringify!($($t)*),"`"));
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,,$($t:tt)*)=>{
$crate::iter_print!(@@inner$writer,$sep,$is_head,$($t)*);
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,;$($t:tt)*)=>{
$crate::iter_print!(@@line_feed$writer);
$crate::iter_print!(@@inner$writer,$sep,$is_head,$($t)*);
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,!$(,)?)=>{};
(@@inner$writer:expr,$sep:expr,$is_head:expr,!$($t:tt)*)=>{
$crate::iter_print!(@@inner$writer,$sep,$is_head,$($t)*);
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,)=>{
$crate::iter_print!(@@line_feed$writer);
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,{$($t:tt)*}$($rest:tt)*)=>{
$crate::iter_print!(@@inner$writer,$sep,$is_head,$($t)*,!);
$crate::iter_print!(@@inner$writer,$sep,$is_head,$($rest)*);
};
(@@inner$writer:expr,$sep:expr,$is_head:expr,$($t:tt)*)=>{
$crate::iter_print!(@@inner$writer,$sep,$is_head,@item$($t)*);
};
($writer:expr,$($t:tt)*)=>{{
$crate::iter_print!(@@inner$writer,' ',true,$($t)*);
}};
}
}
// }}}
// {{{ Scanner
mod scanner {
#[allow(unused_imports)]
use std::io::Read;
use std::{
iter::{from_fn, repeat_with, FromIterator},
marker::PhantomData,
};
// two ways to read stdin all at once
pub fn read_stdin_all() -> String {
use std::io::Read as _;
let mut s = String::new();
std::io::stdin().read_to_string(&mut s).expect("io error");
s
}
pub fn read_stdin_all_unchecked() -> String {
use std::io::Read as _;
let mut buf = Vec::new();
std::io::stdin().read_to_end(&mut buf).expect("io error");
unsafe { String::from_utf8_unchecked(buf) }
}
// two ways to read from a reader instance
pub fn read_all(mut reader: impl std::io::Read) -> String {
let mut s = String::new();
reader.read_to_string(&mut s).expect("io error");
s
}
pub fn read_all_unchecked(mut reader: impl std::io::Read) -> String {
let mut buf = Vec::new();
reader.read_to_end(&mut buf).expect("io error");
unsafe { String::from_utf8_unchecked(buf) }
}
// read one line at a time from stdin
pub fn read_stdin_line() -> String {
let mut s = String::new();
std::io::stdin().read_line(&mut s).expect("io error");
s
}
// scan with the original value, or scan with a modification
pub trait IterScan: Sized {
type Output;
fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output>;
}
pub trait MarkedIterScan: Sized {
type Output;
fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output>;
}
// the `Scanner` class
#[derive(Clone, Debug)]
pub struct Scanner<'a> {
iter: std::str::SplitAsciiWhitespace<'a>,
}
impl<'a> Scanner<'a> {
#[inline]
pub fn new(s: &'a str) -> Self {
let iter = s.split_ascii_whitespace();
Self { iter }
}
#[inline]
pub fn scan<T>(&mut self) -> <T as IterScan>::Output
where
T: IterScan,
{
<T as IterScan>::scan(&mut self.iter).expect("scan error")
}
// scan a type with a modification
#[inline]
pub fn mscan<T>(&mut self, marker: T) -> <T as MarkedIterScan>::Output
where
T: MarkedIterScan,
{
marker.mscan(&mut self.iter).expect("scan error")
}
// scan a vector
#[inline]
pub fn scan_vec<T>(&mut self, size: usize) -> Vec<<T as IterScan>::Output>
where
T: IterScan,
{
(0..size)
.map(|_| <T as IterScan>::scan(&mut self.iter).expect("scan error"))
.collect()
}
// scan a iterator
#[inline]
pub fn iter<'b, T>(&'b mut self) -> ScannerIter<'a, 'b, T>
where
T: IterScan,
{
ScannerIter {
inner: self,
_marker: std::marker::PhantomData,
}
}
}
macro_rules! iter_scan_impls {
($($t:ty)*) => {
$(impl IterScan for$t{
type Output = Self;
#[inline]
fn scan<'a,I:Iterator<Item=&'a str>>(iter:&mut I) -> Option<Self> {
iter.next()?.parse::<$t>().ok()
}
})*
};
}
iter_scan_impls!(char u8 u16 u32 u64 usize i8 i16 i32 i64 isize f32 f64 u128 i128 String);
macro_rules! iter_scan_tuple_impl {
(@impl$($T:ident)*) => {
impl <$($T:IterScan),*>IterScan for($($T,)*){
type Output = ($(<$T as IterScan>::Output,)*);
#[inline]
fn scan<'a,It:Iterator<Item=&'a str>>(_iter:&mut It) -> Option<Self::Output> {
Some(($(<$T as IterScan>::scan(_iter)?,)*))
}
}
};
(@inner$($T:ident)*,) => {
iter_scan_tuple_impl!(@impl$($T)*);
};
(@inner$($T:ident)*, $U:ident$($Rest:ident)*) => {
iter_scan_tuple_impl!(@impl$($T)*);
iter_scan_tuple_impl!(@inner$($T)*$U, $($Rest)*);
};
($($T:ident)*) => {
iter_scan_tuple_impl!(@inner, $($T)*);
};
}
iter_scan_tuple_impl!(A B C D E F G H I J K);
pub struct ScannerIter<'a, 'b, T> {
inner: &'b mut Scanner<'a>,
_marker: std::marker::PhantomData<fn() -> T>,
}
impl<'a, 'b, T> Iterator for ScannerIter<'a, 'b, T>
where
T: IterScan,
{
type Item = <T as IterScan>::Output;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
<T as IterScan>::scan(&mut self.inner.iter)
}
}
#[doc = " scan and return the value"]
#[doc = " - `scan_value!(scanner, ELEMENT)`"]
#[doc = " ELEMENT :="]
#[doc = " - `$ty`: IterScan"]
#[doc = " - `@$expr`: MarkedIterScan"]
#[doc = " - `[ELEMENT; $expr]`: vector"]
#[doc = " - `[ELEMENT; const $expr]`: array"]
#[doc = " - `[ELEMENT]`: iterator"]
#[doc = " - `($(ELEMENT)*,)`: tuple"]
#[macro_export]
macro_rules! scan_value {
(@repeat$scanner:expr, [$($t:tt)*]$($len:expr)?) => {
::std::iter::repeat_with(||$crate::scan_value!(@inner$scanner, []$($t)*))$(.take($len).collect::<Vec<_>>())?
};
(@array$scanner:expr, [$($t:tt)*]$len:expr) => {
$crate::array![||$crate::scan_value!(@inner$scanner, []$($t)*);$len]
};
(@tuple$scanner:expr, [$([$($args:tt)*])*]) => {
($($($args)*,)*)
};
(@$tag:ident$scanner:expr, [[$($args:tt)*]]) => {
$($args)*
};
(@$tag:ident$scanner:expr, [$($args:tt)*]@$e:expr) => {
$crate::scan_value! (@$tag$scanner, [$($args)*[$scanner.mscan($e)]])
};
(@$tag:ident$scanner:expr, [$($args:tt)*]@$e:expr, $($t:tt)*) => {
$crate::scan_value! (@$tag$scanner, [$($args)*[$scanner.mscan($e)]]$($t)*)
};
(@$tag:ident$scanner:expr, [$($args:tt)*]($($tuple:tt)*)$($t:tt)*) => {
$crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value!(@tuple$scanner, []$($tuple)*)]]$($t)*)
};
(@$tag:ident$scanner:expr, [$($args:tt)*][@$e:expr;const$len:expr]$($t:tt)*) => {
$crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value!(@array$scanner, [@$e]$len)]]$($t)*)
};
(@$tag:ident$scanner:expr, [$($args:tt)*][@$e:expr;$len:expr]$($t:tt)*) => {
$crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value!(@repeat$scanner, [@$e]$len)]]$($t)*)
};
(@$tag:ident$scanner:expr, [$($args:tt)*][[$($tt:tt)*]; const$len:expr]$($t:tt)*) => {
$crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value!(@array$scanner, [[$($tt)*]]$len)]]$($t)*)
};
(@$tag:ident$scanner:expr, [$($args:tt)*][[$($tt:tt)*]; $len:expr]$($t:tt)*) => {
$crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value!(@repeat$scanner, [[$($tt)*]]$len)]]$($t)*)
};
(@$tag:ident$scanner:expr, [$($args:tt)*][($($tt:tt)*); const$len:expr]$($t:tt)*) => {
$crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value!(@array$scanner, [($($tt)*)]$len)]]$($t)*)
};
(@$tag:ident$scanner:expr, [$($args:tt)*][($($tt:tt)*); $len:expr]$($t:tt)*) => {
$crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value!(@repeat$scanner, [($($tt)*)]$len)]]$($t)*)
};
(@$tag:ident$scanner:expr, [$($args:tt)*][$ty:ty; const$len:expr]$($t:tt)*) => {
$crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value!(@array$scanner, [$ty]$len)]]$($t)*)
};
(@$tag:ident$scanner:expr, [$($args:tt)*][$ty:ty; $len:expr]$($t:tt)*) => {
$crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value! (@repeat$scanner, [$ty]$len)]]$($t)*)
};
(@$tag:ident$scanner:expr, [$($args:tt)*][$($tt:tt)*]$($t:tt)*) => {
$crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value! (@repeat$scanner, [$($tt)*])]]$($t)*)
};
(@$tag:ident$scanner:expr, [$($args:tt)*]$ty:ty) => {
$crate::scan_value! (@$tag$scanner, [$($args)*[$scanner.scan::<$ty>()]])
};
(@$tag:ident$scanner:expr, [$($args:tt)*]$ty:ty,$($t:tt)*) => {
$crate::scan_value! (@$tag$scanner, [$($args)*[$scanner.scan::<$ty>()]]$($t)*)
};
(@$tag:ident$scanner:expr, [$($args:tt)*],$($t:tt)*) => {
$crate::scan_value! (@$tag$scanner, [$($args)*]$($t)*)
};
(@$tag:ident$scanner:expr, [$($args:tt)*]) => {
::std::compile_error! (::std::stringify!($($args)*))
};
($scanner:expr,$($t:tt)*) => {
$crate::scan_value! (@inner$scanner, []$($t)*)
}
}
#[doc = " scan and bind values"]
#[doc = " - `scan!(scanner, $($pat $(: ELEMENT)?),*)`"]
#[macro_export]
macro_rules! scan {
(@assert$p:pat) => {};
(@assert$($p:tt)*) => {
::std::compile_error!(::std::concat!("expected pattern, found `", ::std::stringify!($($p)*), "`"));
};
// inner: pattern part
(@pat$scanner:expr, [][]) => {};
(@pat$scanner:expr, [][], $($t:tt)*) => {
$crate::scan! (@pat$scanner, [][]$($t)*)
};
(@pat$scanner:expr, [$($p:tt)*][]$x:ident$($t:tt)*) => {
$crate::scan! (@pat$scanner, [$($p)*$x][]$($t)*)
};
(@pat$scanner:expr, [$($p:tt)*][]::$($t:tt)*) => {
$crate::scan! (@pat$scanner, [$($p)*::][]$($t)*)
};
(@pat$scanner:expr, [$($p:tt)*][]&$($t:tt)*) => {
$crate::scan! (@pat$scanner, [$($p)*&][]$($t)*)
};
(@pat$scanner:expr, [$($p:tt)*][]($($x:tt)*)$($t:tt)*) => {
$crate::scan! (@pat$scanner, [$($p)*($($x)*)][]$($t)*)
};
(@pat$scanner:expr, [$($p:tt)*][][$($x:tt)*]$($t:tt)*) => {
$crate::scan! (@pat$scanner, [$($p)*[$($x)*]][]$($t)*)
};
(@pat$scanner:expr, [$($p:tt)*][]{$($x:tt)*}$($t:tt)*) => {
$crate::scan! (@pat$scanner, [$($p)*{$($x)*}][]$($t)*)
};
(@pat$scanner:expr, [$($p:tt)*][]:$($t:tt)*) => {
$crate::scan! (@ty$scanner, [$($p)*][]$($t)*)
};
(@pat$scanner:expr, [$($p:tt)*][]$($t:tt)*) => {
$crate::scan! (@let$scanner, [$($p)*][usize]$($t)*)
};
// inner: ty part
(@ty$scanner:expr, [$($p:tt)*][$($tt:tt)*]@$e:expr) => {
$crate::scan! (@let$scanner, [$($p)*][$($tt)*@$e])
};
(@ty$scanner:expr, [$($p:tt)*][$($tt:tt)*]@$e:expr,$($t:tt)*) => {
$crate::scan! (@let$scanner, [$($p)*][$($tt)*@$e],$($t)*)
};
(@ty$scanner:expr, [$($p:tt)*][$($tt:tt)*]($($x:tt)*)$($t:tt)*) => {
$crate::scan! (@let$scanner, [$($p)*][$($tt)*($($x)*)]$($t)*)
};
(@ty$scanner:expr, [$($p:tt)*][$($tt:tt)*][$($x:tt)*]$($t:tt)*) => {
$crate::scan! (@let$scanner, [$($p)*][$($tt)*[$($x)*]]$($t)*)
};
(@ty$scanner:expr, [$($p:tt)*][$($tt:tt)*]$ty:ty) => {
$crate::scan! (@let$scanner, [$($p)*][$($tt)*$ty])
};
(@ty$scanner:expr, [$($p:tt)*][$($tt:tt)*]$ty:ty,$($t:tt)*) => {
$crate::scan! (@let$scanner, [$($p)*][$($tt)*$ty],$($t)*)
};
// inner: let part
(@let$scanner:expr, [$($p:tt)*][$($tt:tt)*]$($t:tt)*) => {
$crate::scan! { @assert$($p)* }
let$($p)* = $crate::scan_value! ($scanner, $($tt)*);
$crate::scan! (@pat$scanner, [][]$($t)*)
};
($scanner:expr, $($t:tt)*) => {
$crate::scan! (@pat$scanner, [][]$($t)*)
}
}
#[derive(Debug, Copy, Clone)]
pub enum Usize1 {}
impl IterScan for Usize1 {
type Output = usize;
#[inline]
fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
<usize as IterScan>::scan(iter)?.checked_sub(1)
}
}
#[derive(Debug, Copy, Clone)]
pub struct CharWithBase(pub char);
impl MarkedIterScan for CharWithBase {
type Output = usize;
#[inline]
fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
Some((<char as IterScan>::scan(iter)? as u8 - self.0 as u8) as usize)
}
}
#[derive(Debug, Copy, Clone)]
pub enum Chars {}
impl IterScan for Chars {
type Output = Vec<char>;
#[inline]
fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
Some(iter.next()?.chars().collect())
}
}
#[derive(Debug, Copy, Clone)]
pub struct CharsWithBase(pub char);
impl MarkedIterScan for CharsWithBase {
type Output = Vec<usize>;
#[inline]
fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
Some(
iter.next()?
.chars()
.map(|c| (c as u8 - self.0 as u8) as usize)
.collect(),
)
}
}
#[derive(Debug, Copy, Clone)]
pub enum Byte1 {}
impl IterScan for Byte1 {
type Output = u8;
#[inline]
fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
let bytes = iter.next()?.as_bytes();
assert_eq!(bytes.len(), 1);
Some(bytes[0])
}
}
#[derive(Debug, Copy, Clone)]
pub struct ByteWithBase(pub u8);
impl MarkedIterScan for ByteWithBase {
type Output = usize;
#[inline]
fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
Some((<char as IterScan>::scan(iter)? as u8 - self.0) as usize)
}
}
#[derive(Debug, Copy, Clone)]
pub enum Bytes {}
impl IterScan for Bytes {
type Output = Vec<u8>;
#[inline]
fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
Some(iter.next()?.bytes().collect())
}
}
#[derive(Debug, Copy, Clone)]
pub struct BytesWithBase(pub u8);
impl MarkedIterScan for BytesWithBase {
type Output = Vec<usize>;
#[inline]
fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
Some(
iter.next()?
.bytes()
.map(|c| (c - self.0) as usize)
.collect(),
)
}
}
// TODO
#[derive(Debug, Copy, Clone)]
pub struct Collect<T, B = Vec<<T as IterScan>::Output>>
where
T: IterScan,
B: FromIterator<<T as IterScan>::Output>,
{
size: usize,
_marker: PhantomData<fn() -> (T, B)>,
}
impl<T, B> Collect<T, B>
where
T: IterScan,
B: FromIterator<<T as IterScan>::Output>,
{
pub fn new(size: usize) -> Self {
Self {
size,
_marker: PhantomData,
}
}
}
impl<T, B> MarkedIterScan for Collect<T, B>
where
T: IterScan,
B: FromIterator<<T as IterScan>::Output>,
{
type Output = B;
#[inline]
fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
repeat_with(|| <T as IterScan>::scan(iter))
.take(self.size)
.collect()
}
}
// TODO
#[derive(Debug, Copy, Clone)]
pub struct SizedCollect<T, B = Vec<<T as IterScan>::Output>>
where
T: IterScan,
B: FromIterator<<T as IterScan>::Output>,
{
_marker: PhantomData<fn() -> (T, B)>,
}
impl<T, B> IterScan for SizedCollect<T, B>
where
T: IterScan,
B: FromIterator<<T as IterScan>::Output>,
{
type Output = B;
#[inline]
fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
let size = usize::scan(iter)?;
repeat_with(|| <T as IterScan>::scan(iter))
.take(size)
.collect()
}
}
// TODO
#[derive(Debug, Copy, Clone)]
pub struct Splitted<T, P>
where
T: IterScan,
{
pat: P,
_marker: PhantomData<fn() -> T>,
}
impl<T, P> Splitted<T, P>
where
T: IterScan,
{
pub fn new(pat: P) -> Self {
Self {
pat,
_marker: PhantomData,
}
}
}
impl<T> MarkedIterScan for Splitted<T, char>
where
T: IterScan,
{
type Output = Vec<<T as IterScan>::Output>;
fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
let mut iter = iter.next()?.split(self.pat);
Some(from_fn(|| <T as IterScan>::scan(&mut iter)).collect())
}
}
impl<T> MarkedIterScan for Splitted<T, &str>
where
T: IterScan,
{
type Output = Vec<<T as IterScan>::Output>;
fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
let mut iter = iter.next()?.split(self.pat);
Some(from_fn(|| <T as IterScan>::scan(&mut iter)).collect())
}
}
impl<T, F> MarkedIterScan for F
where
F: Fn(&str) -> Option<T>,
{
type Output = T;
fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
self(iter.next()?)
}
}
}
// }}}
// }}}