結果
| 問題 | No.2343 (l+r)/2 |
| ユーザー |
 Sarievo
|
| 提出日時 | 2023-06-09 22:00:38 |
| 言語 | Rust (1.77.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 33,071 bytes |
| コンパイル時間 | 2,382 ms |
| コンパイル使用メモリ | 172,276 KB |
| 実行使用メモリ | 4,508 KB |
| 最終ジャッジ日時 | 2023-08-30 13:17:08 |
| 合計ジャッジ時間 | 2,451 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,376 KB |
| testcase_01 | AC | 25 ms
4,376 KB |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | AC | 4 ms
4,376 KB |
| testcase_05 | AC | 2 ms
4,376 KB |
| testcase_06 | AC | 2 ms
4,380 KB |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | AC | 2 ms
4,384 KB |
| testcase_11 | AC | 3 ms
4,376 KB |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | AC | 4 ms
4,388 KB |
コンパイルメッセージ
warning: unused import: `std::marker::PhantomData` --> Main.rs:88:5 | 88 | use std::marker::PhantomData; | ^^^^^^^^^^^^^^^^^^^^^^^^ | = note: `#[warn(unused_imports)]` on by default warning: variable does not need to be mutable --> Main.rs:35:13 | 35 | let mut dat = press(a); | ----^^^ | | | help: remove this `mut` | = note: `#[warn(unused_mut)]` on by default warning: 2 warnings emitted
ソースコード
// macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::<Vec<char>>() };($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().unwrap() }; }
// macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; }
// macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => { let mut $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; ($iter:expr, mut $var:ident $($r:tt)*) => { let mut $var = $iter.next().unwrap().parse::<usize>().unwrap(); input_inner!{$iter $($r)*} }; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; ($iter:expr, $var:ident $($r:tt)*) => { let $var = $iter.next().unwrap().parse::<usize>().unwrap(); input_inner!{$iter $($r)*} }; }
/*
template<class T> auto press(const T &a) {
vector<pair<decay_t<decltype(a[0])>, ll>> ans;
for(auto&&x:a) {
if (ans.empty() || ans.back().first != x)
ans.emplace_back(x, 1);
else ans.back().second++;
}
return ans;
}
*/
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 {
let back = ret.pop().unwrap();
ret.push((back.0, back.1 + 1));
}
}
return ret;
}
fn main() {
prepare!();
sc!(case);
for _ in 0..case {
sc!(n, a: [usize; n]);
let mut dat = press(a);
let mut x_nseg = 0;
let mut y_nseg = 0;
let mut x_nocc = 0;
let mut y_nocc = 0;
for i in 0..dat.len() {
let da = dat[i];
if da.0 == 0 {
x_nseg += 1;
if i > 1 && i + 1 < dat.len() {
x_nocc += da.1.min(2) - 1;
}
}
else {
y_nseg += 1;
if i > 1 && i + 1 < dat.len() {
y_nocc += da.1.min(2) - 1;
}
}
}
pp!{
if x_nseg == y_nseg {
"Yes"
} else {
if x_nseg == 0 || y_nseg == 0 {
"No"
} else {
if x_nseg > y_nseg {
if y_nocc > 0 {
"Yes"
} else {
"No"
}
} else {
if x_nocc > 0 {
"Yes"
} else {
"No"
}
}
}
}
}
}
}
#[allow(unused_imports)]
use std::{cmp::{Ordering, Reverse}, collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}};
// input / output
use std::marker::PhantomData;
mod main_macros {
#[doc = " Prepare useful macros."]
#[doc = " - `prepare!();`: default (all input scanner (`sc!`, `sv!`) + buf print (`pp!`))"]
#[doc = " - `prepare!(?);`: interactive (line scanner (`scln!`) + buf print (`pp!`))"]
#[macro_export]macro_rules! prepare {(@normal($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)]macro_rules!pp{($dol($dol t:tt)*)=>{$dol crate::iter_print!(__out,$dol($dol t)*)}}let __in_buf=read_stdin_all_unchecked();#[allow(unused_mut,unused_variables)]let mut __scanner=Scanner::new(&__in_buf);#[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_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=" - to flush: `pp!(@flush);`"]macro_rules!pp{($dol($dol t:tt)*)=>{$dol crate::iter_print!(__out,$dol($dol t)*)}}#[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!(@normal($))};(?)=>{$crate::prepare!(@interactive($))};}
}
pub use self::iter_print::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 = " - `@fmt $lit => {$($expr),*}`: print `format!($lit, $($expr),*)`"]
#[doc = " - `@flush`: flush writer (auto insert `!`)"]
#[doc = " - `@iter $expr`: print iterator"]
#[doc = " - `@iterns $expr`: print iterator with no separators"]
#[doc = " - `@iterln $expr`: print iterator with separator `'\\n'`"]
#[doc = " - `@iter2d $expr`: print 2d-iterator"]
#[doc = " - `@tuple $expr`: print tuple (need to import [`IterPrint`], each elements impls `Display`)"]
#[doc = " - `$expr`: print expr"]
#[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");};(@@iter$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);}}};(@@iterns$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,true,item);}}};(@@iterln$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,'\n',$is_head,item);}for item in iter{$crate::iter_print!(@@item$writer,'\n',false,item);}}};(@@iter2d$writer:expr,$sep:expr,$is_head:expr,$iter:expr)=>{let mut iter=$iter.into_iter();if let Some(item)=iter.next(){$crate::iter_print!(@@iter$writer,$sep,$is_head,item);}for item in iter{$crate::iter_print!(@@line_feed$writer);$crate::iter_print!(@@iter$writer,$sep,true,item);}};(@@tuple$writer:expr,$sep:expr,$is_head:expr,$tuple:expr)=>{IterPrint::iter_print($tuple,&mut$writer,$sep,$is_head).expect("io error");};(@@assert_tag item)=>{};(@@assert_tag iter)=>{};(@@assert_tag iterns)=>{};(@@assert_tag iterln)=>{};(@@assert_tag iter2d)=>{};(@@assert_tag tuple)=>{};(@@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,@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$lit:literal=>{$($e:expr),*$(,)?}$($t:tt)*)=>{$crate::iter_print!(@@fmt$writer,$sep,$is_head,$lit,$($e),*);$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)*)=>{$crate::iter_print!(@@inner$writer,$sep,$is_head,@item$($t)*);};($writer:expr,$($t:tt)*)=>{{$crate::iter_print!(@@inner$writer,' ',true,$($t)*);}};}
}
pub use self::scanner::*;
mod scanner {
use std::{iter::{from_fn, repeat_with, FromIterator}, marker::PhantomData};
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) }
}
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) }
}
pub fn read_stdin_line() -> String {
let mut s = String::new();
std::io::stdin().read_line(&mut s).expect("io error");
s
}
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>;
}
#[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") }
#[inline]
pub fn mscan<T>(&mut self, marker: T) -> <T as MarkedIterScan>::Output where T: MarkedIterScan { marker.mscan(&mut self.iter).expect("scan error") }
#[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() }
#[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_value!(scanner, ELEMENT)`"]
#[doc = ""]
#[doc = " ELEMENT :="]
#[doc = " - `$ty`: IterScan"]
#[doc = " - `@$expr`: MarkedIterScan"]
#[doc = " - `[ELEMENT; $expr]`: vector"]
#[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<_>>())?};(@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;$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)*];$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)*);$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;$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!(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)*),"`"));};(@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)*)};(@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)*)};(@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 struct 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 struct 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 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 struct 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()) }
}
#[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() }
}
#[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()
}
}
#[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()?) }
}
}
// recursive closures
mod closure {
#[macro_export]macro_rules! rec {
(@macro_def($dol:tt)$name:ident$($cargs:ident)*)=>{#[allow(unused_macros)]macro_rules!$name{($dol($dol args:expr),*)=>{$name($dol($dol args,)*$($cargs,)*)}}};
(@static[$(($cargs:ident,$cargsexpr:expr,$cargsty:ty))*][$(,)?],fn$func:ident($($args:ident:$argsty:ty),*$(,)?)->$ret:ty$body:block)=>{{fn$func($($args:$argsty,)*$($cargs:$cargsty,)*)->$ret{$crate::rec!(@macro_def($)$func$($cargs)*);$body}|$($args:$argsty,)*|->$ret{$func($($args,)*$($cargsexpr,)*)}}};
(@static[$($pcaps:tt)*][$(,)?],fn$func:ident($($argstt:tt)*)$($rest:tt)*)=>{$crate::rec!(@static[$($pcaps)*][],fn$func($($argstt)*)->()$($rest)*)};
(@static[$($pcaps:tt)*][$carg:ident:&mut$cargty:ty,$($caps:tt)*],$($rest:tt)*)=>{$crate::rec!(@static[$($pcaps)*($carg,&mut$carg,&mut$cargty)][$($caps)*],$($rest)*)};(@static[$($pcaps:tt)*][$carg:ident:&$cargty:ty,$($caps:tt)*],$($rest:tt)*)=>{$crate::rec!(@static[$($pcaps)*($carg,&$carg,&$cargty)][$($caps)*],$($rest)*)};
(@static[$($pcaps:tt)*][$carg:ident:$cargty:ty,$($caps:tt)*],$($rest:tt)*)=>{$crate::rec!(@static[$($pcaps)*($carg,$carg,$cargty)][$($caps)*],$($rest)*)};($([$($caps:tt)*],)?static fn$func:ident($($args:ident:$argsty:ty),*$(,)?)$($rest:tt)*)=>{$crate::rec!(@static[][$($($caps)*)?,],fn$func($($args:$argsty),*)$($rest)*)};
(@default[$($cargs:ident:$cargsty:ty),*$(,)?],fn$func:ident($($args:ident:$argsty:ty),*$(,)?)->$ret:ty$body:block)=>{{fn call<F>(f:&F,$($args:$argsty,)*$($cargs:&mut$cargsty,)*)->$ret where F:Fn(&dyn Fn($($argsty,)*$(&mut$cargsty,)*)->$ret,$($argsty,)*$(&mut$cargsty,)*)->$ret,{f(&|$($args:$argsty,)*$($cargs:&mut$cargsty,)*|->$ret{call(f,$($args,)*$($cargs,)*)},$($args,)*$($cargs,)*)}|$($args:$argsty,)*|->$ret{call(&|$func,$($args:$argsty,)*$($cargs:&mut$cargsty,)*|->$ret{$crate::rec!(@macro_def($)$func$($cargs)*);$body},$($args,)*$(&mut$cargs,)*)}}};
(@default[$($caps:tt)*],fn$func:ident($($argstt:tt)*)$($rest:tt)*)=>{$crate::rec!(@default[$($caps)*],fn$func($($argstt)*)->()$($rest)*)};($([$($caps:tt)*],)?fn$func:ident($($args:ident:$argsty:ty),*$(,)?)$($rest:tt)*)=>{$crate::rec!(@default[$($($caps)*)?],fn$func($($args:$argsty),*)$($rest)*)};
(@unsafe[$($cargs:ident:$cargsty:ty),*$(,)?],fn$func:ident($($args:ident:$argsty:ty),*$(,)?)->$ret:ty$body:block)=>{{fn call<F>(f:&mut F,$($args:$argsty,)*$($cargs:&mut$cargsty,)*)->$ret where F:FnMut(&mut dyn FnMut($($argsty,)*$(&mut$cargsty,)*)->$ret,$($argsty,)*$(&mut$cargsty,)*)->$ret,{let fp=f as*mut F;(unsafe{&mut*fp})(&mut|$($args:$argsty,)*$($cargs:&mut$cargsty,)*|->$ret{call(unsafe{&mut*fp},$($args,)*$($cargs,)*)},$($args,)*$($cargs,)*)}|$($args:$argsty,)*|->$ret{call(&mut|$func,$($args:$argsty,)*$($cargs:&mut$cargsty,)*|->$ret{$crate::rec!(@macro_def($)$func$($cargs)*);$body},$($args,)*$(&mut$cargs,)*)}}};
(@unsafe[$($caps:tt)*],fn$func:ident($($argstt:tt)*)$($rest:tt)*)=>{$crate::rec!(@unsafe[$($caps)*],fn$func($($argstt)*)->()$($rest)*)};($([$($caps:tt)*],)?unsafe fn$func:ident($($args:ident:$argsty:ty),*$(,)?)$($rest:tt)*)=>{$crate::rec!(@unsafe[$($($caps)*)?],fn$func($($args:$argsty),*)$($rest)*)};
($($t:tt)*)=>{::std::compile_error!(::std::concat!("invalid input: ",::std::stringify!($($t)*)))};
}
#[macro_export]macro_rules! mem {
(@inner[$map:ident,$Map:ty,$init:expr]fn$name:ident($($args:ident:$argsty:ty),*$(,)?)->$ret:ty$body:block)=>{let mut$map:$Map=$init;#[allow(unused_mut)]let mut$name=$crate::rec!([$map:$Map],fn$name($($args:$argsty),*)->$ret{if let Some(value)=$map.get(&($($args,)*)).cloned(){value}else{let value=(||$body)();$map.insert(($($args,)*),value.clone());value}});};
(fn$name:ident($($args:ident:$argsty:ty),*$(,)?)->$ret:ty$body:block)=>{$crate::mem!(@inner[__memorize_map,::std::collections::HashMap<($($argsty,)*),$ret>,::std::default::Default::default()]fn$name($($args:$argsty),*)->$ret$body);}
}
}
// recall popular data structures from scratch: eg. segtree, dsu, bit
// sugars
// pub use self::sparse_graph::*;
// mod sparse_graph{use super::{IterScan,MarkedIterScan};use std::{marker::PhantomData,ops,slice};type Marker<T>=PhantomData<fn()->T>;#[derive(Clone,Copy,Debug,Default,Eq,PartialEq,Ord,PartialOrd,Hash)]pub struct DirectedEdge;#[derive(Clone,Copy,Debug,Default,Eq,PartialEq,Ord,PartialOrd,Hash)]pub struct UndirectedEdge;#[derive(Clone,Copy,Debug,Default,Eq,PartialEq,Ord,PartialOrd,Hash)]pub struct BidirectionalEdge;#[derive(Clone,Copy,Debug,Default,Eq,PartialEq,Ord,PartialOrd,Hash)]pub struct Adjacency{pub id:usize,pub to:usize}impl Adjacency{pub fn new(id:usize,to:usize)->Adjacency{Adjacency{id,to}}}#[doc=" Static Sparse Graph represented as Compressed Sparse Row."]#[derive(Debug,Clone)]pub struct SparseGraph<D>{vsize:usize,pub start:Vec<usize>,pub elist:Vec<Adjacency>,pub edges:Vec<(usize,usize)>,_marker:Marker<D>}impl<D>SparseGraph<D>{#[doc=" Return the number of vertices."]pub fn vertices_size(&self)->usize{self.vsize}#[doc=" Return the number of edges."]pub fn edges_size(&self)->usize{self.edges.len()}#[doc=" Return an iterator over graph vertices."]pub fn vertices(&self)->ops::Range<usize>{0..self.vertices_size()}#[doc=" Return a slice of adjacency vertices."]pub fn adjacencies(&self,v:usize)->slice::Iter<'_,Adjacency>{self.elist[self.start[v]..self.start[v+1]].iter()}}pub trait SparseGraphConstruction:Sized{fn construct_graph(vsize:usize,edges:Vec<(usize,usize)>)->SparseGraph<Self>;}impl<D:SparseGraphConstruction>SparseGraph<D>{#[doc=" Construct graph from edges."]pub fn from_edges(vsize:usize,edges:Vec<(usize,usize)>)->Self{D::construct_graph(vsize,edges)}}impl SparseGraphConstruction for DirectedEdge{fn construct_graph(vsize:usize,edges:Vec<(usize,usize)>)->SparseGraph<Self>{let mut start:Vec<_>=vec![0usize;vsize+1];for(from,_)in edges.iter().cloned(){start[from]+=1;}for i in 1..=vsize{start[i]+=start[i-1];}let mut elist=Vec::<Adjacency>::with_capacity(edges.len());let ptr=elist.as_mut_ptr();for(id,(from,to))in edges.iter().cloned().enumerate(){start[from]-=1;unsafe{ptr.add(start[from]).write(Adjacency::new(id,to))};}unsafe{elist.set_len(edges.len())};SparseGraph{vsize,start,elist,edges,_marker:PhantomData}}}impl SparseGraphConstruction for UndirectedEdge{fn construct_graph(vsize:usize,edges:Vec<(usize,usize)>)->SparseGraph<Self>{let mut start:Vec<_>=vec![0usize;vsize+1];for(from,to)in edges.iter().cloned(){start[to]+=1;start[from]+=1;}for i in 1..=vsize{start[i]+=start[i-1];}let mut elist=Vec::<Adjacency>::with_capacity(edges.len()*2);let ptr=elist.as_mut_ptr();for(id,(from,to))in edges.iter().cloned().enumerate(){start[from]-=1;unsafe{ptr.add(start[from]).write(Adjacency::new(id,to))};start[to]-=1;unsafe{ptr.add(start[to]).write(Adjacency::new(id,from))};}unsafe{elist.set_len(edges.len()*2)};SparseGraph{vsize,start,elist,edges,_marker:PhantomData}}}impl SparseGraphConstruction for BidirectionalEdge{fn construct_graph(vsize:usize,edges:Vec<(usize,usize)>)->SparseGraph<Self>{let mut start:Vec<_>=vec![0usize;vsize+1];for(from,to)in edges.iter().cloned(){start[to]+=1;start[from]+=1;}for i in 1..=vsize{start[i]+=start[i-1];}let mut elist=Vec::<Adjacency>::with_capacity(edges.len()*2);let ptr=elist.as_mut_ptr();for(id,(from,to))in edges.iter().cloned().enumerate(){start[from]-=1;unsafe{ptr.add(start[from]).write(Adjacency::new(id*2,to))};start[to]-=1;unsafe{ptr.add(start[to]).write(Adjacency::new(id*2+1,from))};}unsafe{elist.set_len(edges.len()*2)};SparseGraph{vsize,start,elist,edges,_marker:PhantomData}}}pub type DirectedSparseGraph=SparseGraph<DirectedEdge>;pub type UndirectedSparseGraph=SparseGraph<UndirectedEdge>;pub type BidirectionalSparseGraph=SparseGraph<BidirectionalEdge>;pub struct SparseGraphScanner<U:IterScan<Output=usize>,T:IterScan,D>{vsize:usize,esize:usize,_marker:Marker<(U,T,D)>}impl<U:IterScan<Output=usize>,T:IterScan,D>SparseGraphScanner<U,T,D>{pub fn new(vsize:usize,esize:usize)->Self{Self{vsize,esize,_marker:PhantomData}}}impl<U:IterScan<Output=usize>,T:IterScan,D:SparseGraphConstruction>MarkedIterScan for SparseGraphScanner<U,T,D>{type Output=(SparseGraph<D>,Vec<<T as IterScan>::Output>);fn mscan<'a,I:Iterator<Item=&'a str>>(self,iter:&mut I)->Option<Self::Output>{let mut edges=Vec::with_capacity(self.esize);let mut rest=Vec::with_capacity(self.esize);for _ in 0..self.esize{edges.push((U::scan(iter)?,U::scan(iter)?));rest.push(T::scan(iter)?);}let graph=SparseGraph::from_edges(self.vsize,edges);Some((graph,rest))}}pub type DirectedGraphScanner<U,T=()>=SparseGraphScanner<U,T,DirectedEdge>;pub type UndirectedGraphScanner<U,T=()>=SparseGraphScanner<U,T,UndirectedEdge>;pub type BidirectionalGraphScanner<U,T=()>=SparseGraphScanner<U,T,BidirectionalEdge>;pub struct TreeGraphScanner<U:IterScan<Output=usize>,T:IterScan=()>{vsize:usize,_marker:Marker<(U,T)>}impl<U:IterScan<Output=usize>,T:IterScan>TreeGraphScanner<U,T>{pub fn new(vsize:usize)->Self{Self{vsize,_marker:PhantomData}}}impl<U:IterScan<Output=usize>,T:IterScan>MarkedIterScan for TreeGraphScanner<U,T>{type Output=(UndirectedSparseGraph,Vec<<T as IterScan>::Output>);fn mscan<'a,I:Iterator<Item=&'a str>>(self,iter:&mut I)->Option<Self::Output>{UndirectedGraphScanner::<U,T>::new(self.vsize,self.vsize-1).mscan(iter)}}}