結果

問題 No.5017 Tool-assisted Shooting
ユーザー to-omer
提出日時 2023-07-16 20:01:40
言語 Rust
(1.83.0 + proconio)
結果
TLE  
実行時間 -
コード長 33,635 bytes
コンパイル時間 2,574 ms
コンパイル使用メモリ 188,732 KB
実行使用メモリ 34,392 KB
スコア 0
最終ジャッジ日時 2023-07-16 20:01:51
合計ジャッジ時間 9,969 ms
ジャッジサーバーID
（参考情報） 		judge9 / judge17
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 99
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

pub fn solve() {
    let now = std::time::Instant::now();
    crate::prepare!(?);
    scln!();
    let mut rng = Xorshift::new();
    let mut pos = 12usize;
    let mut grid = [[Cell::default(); W]; H + T];
    let mut score = 0;
    let mut power = 0;
    let mut r = [[0; W]; H];
    for i in 0..H {
        for j in 0..W {
            r[i][j] = rng.rand64();
        }
    }
    for t in 0..T {
        scln!(n: i32);
        if n < 0 {
            return;
        }
        for _ in 0..n {
            scln!(h: u32, p: u32, x);
            grid[t + H - 1][x] = Cell { h, p, d: 0 };
        }
        let mut g = [[Cell::default(); W]; H];
        for (grid, g) in grid[t..t + H].iter().zip(&mut g) {
            *g = *grid;
        }
        let state = State {
            grid: g,
            score,
            power,
            hash: 0,
            t: 0,
            m: 0,
            pos,
            r,
        };
        let res = beam_search(state, (!0, !0), 100, false).unwrap();
        let (out, i) = res.1[0];
        match out {
            b'L' => pos = (pos + W - 1) % W,
            b'R' => pos = (pos + 1) % W,
            b'S' => {}
            _ => panic!(),
        }
        if i != !0 {
            let g = &mut grid[i + t][pos];
            if g.live() {
                g.attack(power);
                if !g.live() {
                    score += g.h;
                    power += g.p;
                }
            }
        }
        pp!(out as char; @flush);
    }
    eprintln!("(score, power) = {:?}", (score, power));
    eprintln!("elapsed = {:?}", now.elapsed());
}
const T: usize = 1000;
const H: usize = 60;
const W: usize = 25;
#[derive(Debug, Clone, Copy, Default)]
pub struct Cell {
    h: u32,
    p: u32,
    d: u32,
}
impl Cell {
    pub fn live(&self) -> bool {
        self.h > self.d
    }
    pub fn attack(&mut self, power: u32) {
        self.d += 1 + power / 100;
    }
    pub fn revert_attack(&mut self, power: u32) {
        self.d -= 1 + power / 100;
    }
}
#[derive(Debug)]
pub struct State {
    grid: [[Cell; W]; H],
    score: u32,
    power: u32,
    hash: u64,
    t: usize,
    pos: usize,
    m: u32,
    r: [[u64; W]; H],
}
impl ModifiableState for State {
    type Operation = (u8, usize);
    type Score = (u32, u32, u32);
    type Hash = u64;
    type Cands = std::vec::IntoIter<Self::Operation>;
    fn score(&self) -> Self::Score {
        (self.power, self.score, self.m)
    }
    fn hash(&self) -> Self::Hash {
        self.hash
    }
    fn accept(&self) -> bool {
        self.t >= 30
    }
    fn candidates(&self) -> Self::Cands {
        let mut cands = vec![];
        for (out, np) in [
            (b'L', (self.pos + W - 1) % W),
            (b'S', self.pos),
            (b'R', (self.pos + 1) % W),
        ] {
            if !self.grid[self.t][np].live() {
                let i = (self.t + 1..H)
                    .find(|&i| self.grid[i][np].live())
                    .unwrap_or(!0);
                if i == self.t + 1 {
                    let g = &self.grid[i][np];
                    if g.d + 1 + self.power / 100 < g.h {
                        continue;
                    }
                }
                cands.push((out, i));
            }
        }
        cands.into_iter()
    }
    fn change(&mut self, (out, i): Self::Operation) {
        match out {
            b'L' => self.pos = (self.pos + W - 1) % W,
            b'R' => self.pos = (self.pos + 1) % W,
            _ => {}
        }
        self.hash ^= self.r[self.t][self.pos];
        if i != !0 {
            let g = &mut self.grid[i][self.pos];
            assert!(g.live());
            self.m +=
                (out == b'S' && (1 + self.power / 100) * (i - self.t) as u32 + g.d >= g.h) as u32;
            g.attack(self.power);
            if !g.live() {
                self.power += g.p;
                self.score += g.h;
            }
        }
        self.t += 1;
    }
    fn revert(&mut self, (out, i): Self::Operation) {
        self.t -= 1;
        if i != !0 {
            let g = &mut self.grid[i][self.pos];
            if !g.live() {
                self.power -= g.p;
                self.score -= g.h;
            }
            g.revert_attack(self.power);
            assert!(g.live());
            self.m -=
                (out == b'S' && (1 + self.power / 100) * (i - self.t) as u32 + g.d >= g.h) as u32;
        }
        self.hash ^= self.r[self.t][self.pos];
        match out {
            b'L' => self.pos = (self.pos + 1) % W,
            b'R' => self.pos = (self.pos + W - 1) % W,
            _ => {}
        }
    }
}
crate::main!();
#[allow(unused_imports)]use std::{cmp::{Ordering,Reverse},collections::{BTreeMap,BTreeSet,BinaryHeap,HashMap,HashSet,VecDeque}};
mod main_macros{#[doc=" Prepare useful macros."]#[doc=" - `prepare!();`: default (all input scanner (`sc!`, `sv!`) + buf print (`pp!`, `dg!`))"]#[doc
    =" - `prepare!(?);`: interactive (line scanner (`scln!`) + buf print (`pp!`, `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!pp{($dol($dol t:tt)*)=>{$dol 
    crate::iter_print!(__out,$dol($dol t)*)}}#[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);#[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($))}
    ;}#[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();}};}}
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=" - `@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)*);}};}}
mod array{#[macro_export]macro_rules!array{[@inner$data:ident=[$init:expr;$len:expr]]=>{{use::std::mem::{ManuallyDrop,MaybeUninit};let mut$data
    :[MaybeUninit<_>;$len]=unsafe{MaybeUninit::uninit().assume_init()};$init;#[repr(C)]union __Transmuter<const N:usize,T:Clone>{src:ManuallyDrop
    <[MaybeUninit<T>;N]>,dst:ManuallyDrop<[T;N]>,}ManuallyDrop::into_inner(unsafe{__Transmuter{src:ManuallyDrop::new($data)}.dst})}};[||$e:expr;$len
    :expr]=>{$crate::array![@inner data=[data.iter_mut().for_each(|item|*item=MaybeUninit::new($e));$len]]};[|$i:pat_param|$e:expr;$len:expr]
    =>{$crate::array![@inner data=[data.iter_mut().enumerate().for_each(|($i,item)|*item=MaybeUninit::new($e));$len]]};[$e:expr;$len:expr]=>{{let e
    =$e;$crate::array![||Clone::clone(&e);$len]}};}}
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 a value with Scanner"]#[doc=""]#[doc=" - `scan_value!(scanner, ELEMENT)`"]#[doc=""]#[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 with 
    Scanner"]#[doc=""]#[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 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())}}#[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()?)}}}<hide>
pub use self::beam_search::{beam_search,ModifiableState};
mod beam_search{use std::{cmp::Reverse,collections::HashSet,fmt::Debug,hash::Hash};pub trait ModifiableState:Debug{type Operation:Clone+Debug;type 
    Score:Clone+Ord+Debug;type Hash:Clone+Eq+Hash+Debug;type Cands:Iterator<Item=Self::Operation>;fn score(&self)->Self::Score;fn hash(&self)->Self
    ::Hash;fn accept(&self)->bool;fn soft_update(&mut self,op:Self::Operation,_score:Self::Score,_hash:Self::Hash)->Option<(Self::Score,Self::Hash
    ,bool)>{self.update(op.clone());let res=(self.score(),self.hash(),self.accept());self.revert(op);Some(res)}fn update(&mut self,op:Self::Operation
    ){self.change(op);}fn revert(&mut self,op:Self::Operation){self.change(op);}fn change(&mut self,_op:Self::Operation){}fn candidates(&self)->Self
    ::Cands;}#[derive(Debug)]pub struct Candidate<S>where S:ModifiableState{parent:usize,op:S::Operation,score:S::Score,hash:S::Hash,accept:bool}impl
    <S>Clone for Candidate<S>where S:ModifiableState{fn clone(&self)->Self{Self{parent:self.parent,op:self.op.clone(),score:self.score.clone(),hash
    :self.hash.clone(),accept:self.accept}}}#[derive(Debug,Clone)]pub struct Node<S>where S:ModifiableState{parent:usize,child:usize,prev:usize,next
    :usize,op:S::Operation,score:S::Score,hash:S::Hash}impl<S>Node<S>where S:ModifiableState{pub fn new(state:&S,init_op:S::Operation
    )->Self{Node{parent:!0,child:!0,prev:!0,next:!0,op:init_op,score:state.score(),hash:state.hash()}}}#[derive(Debug)]pub struct Tree<S>where S
    :ModifiableState{state:S,latest:usize,nodes:Vec<Node<S>>,cur_node:usize}impl<S>Tree<S>where S:ModifiableState{pub fn new(state:S,init_op:S
    ::Operation)->Self{let node=Node::new(&state,init_op);Tree{state,latest:0,nodes:vec![node],cur_node:0}}fn add_node(&mut self,op:S::Operation
    ,parent:usize,score:S::Score,hash:S::Hash){let next=self.nodes[parent].child;if next!=!0{self.nodes[next].prev=self.nodes.len();}self
    .nodes[parent].child=self.nodes.len();self.nodes.push(Node{parent,child:!0,prev:!0,next,op,score,hash});}fn remove_node(&mut self,mut idx:usize
    ){loop{let Node{prev,next,parent,..}=self.nodes[idx];assert_ne!(parent,!0);if prev&next==!0{idx=parent;continue;}if prev!=!0{self.nodes[prev]
    .next=next;}else{self.nodes[parent].child=next;}if next!=!0{self.nodes[next].prev=prev;}break;}}pub fn operations(&self,mut idx:usize)->Vec<S
    ::Operation>{let mut ret=vec![];loop{let Node{op,parent,..}=&self.nodes[idx];if*parent==!0{break;}ret.push(op.clone());idx=*parent;}ret.reverse
    ();ret}fn update(&mut self,cands:&mut Vec<Candidate<S>>,beam_weidth:usize,minimize:bool){if cands.len()>beam_weidth{if minimize{cands
    .select_nth_unstable_by_key(beam_weidth,|s|s.score.clone());}else{cands.select_nth_unstable_by_key(beam_weidth,|s|Reverse(s.score.clone
    ()));}cands.truncate(beam_weidth);}let len=self.nodes.len();for Candidate{parent,op,score,hash,..}in cands.drain(..){self.add_node(op,parent
    ,score,hash);}for i in self.latest..len{if self.nodes[i].child==!0{self.remove_node(i);}}self.latest=len;}pub fn dfs(&mut self,cands:&mut Vec
    <Candidate<S>>,set:&HashSet<S::Hash>,single:bool){let node=&self.nodes[self.cur_node];if node.child==!0{assert!(node.score==self.state.score
    ());assert!(node.hash==self.state.hash());for op in self.state.candidates(){if let Some((score,hash,accept))=self.state.soft_update(op.clone
    (),node.score.clone(),node.hash.clone()){if!set.contains(&hash){cands.push(Candidate{parent:self.cur_node,op,score,hash,accept});}};}}else{let 
    node=self.cur_node;let mut child=self.nodes[node].child;let next_single=single&(self.nodes[child].next==!0);loop{self.cur_node=child;self.state
    .update(self.nodes[child].op.clone());self.dfs(cands,set,next_single);if!next_single{self.state.revert(self.nodes[child].op.clone());}child=self
    .nodes[child].next;if child==!0{break;}}if!next_single{self.cur_node=node;}}}pub fn take_best(&self,cands:&[Candidate<S>],minimize:bool)->Option
    <(S::Score,Vec<S::Operation>)>{let cands=cands.iter().filter(|cand|cand.accept);if let Some(Candidate{op,parent,score,..})=if minimize{cands
    .min_by_key(|cand|cand.score.clone())}else{cands.max_by_key(|cand|cand.score.clone())}{let mut ret=self.operations(*parent);ret.push(op.clone
    ());Some((score.clone(),ret))}else{None}}}pub fn beam_search<S>(state:S,init_op:S::Operation,beam_weidth:usize,minimize:bool)->Option<(S::Score
    ,Vec<S::Operation>)>where S:ModifiableState{let mut tree=Tree::new(state,init_op);let mut cands=vec![];let mut set=HashSet::<S::Hash>::default
    ();loop{tree.dfs(&mut cands,&set,true);if let Some(res)=tree.take_best(&cands,minimize){return Some(res);}if cands.is_empty(){return None;}set
    .extend(cands.iter().map(|cand|cand.hash.clone()));tree.update(&mut cands,beam_weidth,minimize);}}}
#[derive(Clone,Debug)]pub struct Xorshift{y:u64}
impl Xorshift{pub fn new_with_seed(seed:u64)->Self{Xorshift{y:seed}}pub fn new()->Self{use std::{collections::hash_map::RandomState,hash
    ::{BuildHasher,Hasher}};Xorshift::new_with_seed(RandomState::new().build_hasher().finish())}#[inline]pub fn rand64(&mut self)->u64{self.y^=self.y
    <<5;self.y^=self.y>>17;self.y^=self.y<<11;self.y}#[inline]pub fn rand(&mut self,k:u64)->u64{self.rand64()%k}#[inline]pub fn rands(&mut self,k:u64
    ,n:usize)->Vec<u64>{(0..n).map(|_|self.rand(k)).collect::<Vec<_>>()}#[inline]pub fn randf(&mut self)->f64{const UPPER_MASK:u64
    =0x3FF0_0000_0000_0000;const LOWER_MASK:u64=0x000F_FFFF_FFFF_FFFF;let tmp=UPPER_MASK|(self.rand64()&LOWER_MASK);let result:f64=f64::from_bits(tmp
    );result-1.0}#[inline]pub fn gen_bool(&mut self,p:f64)->bool{self.randf()<p}pub fn shuffle<T>(&mut self,slice:&mut[T]){let mut n=slice.len
    ();while n>1{let i=self.rand(n as _)as usize;n-=1;slice.swap(i,n);}}}
impl Default for Xorshift{fn default()->Self{Xorshift::new_with_seed(0x2b99_2ddf_a232_49d6)}}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0