#782950 (Rust) No.5007 Steiner Space Travel

提出ソース
結果

問題	No.5007 Steiner Space Travel
ユーザー	to-omer
提出日時	2022-07-30 15:08:55
言語	Rust (1.77.0)
結果	AC
実行時間	982 ms / 1,000 ms
コード長	34,586 bytes
コンパイル時間	1,753 ms
実行使用メモリ	6,952 KB
スコア	8,424,071
最終ジャッジ日時	2022-07-30 15:09:29
合計ジャッジ時間	34,006 ms
ジャッジサーバーID （参考情報）	judge11 / judge13
	純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	981 ms 4,900 KB
testcase_01	AC	982 ms 6,952 KB
testcase_02	AC	981 ms 6,952 KB
testcase_03	AC	981 ms 6,948 KB
testcase_04	AC	981 ms 4,900 KB
testcase_05	AC	982 ms 4,904 KB
testcase_06	AC	981 ms 4,904 KB
testcase_07	AC	980 ms 4,904 KB
testcase_08	AC	982 ms 6,948 KB
testcase_09	AC	981 ms 4,904 KB
testcase_10	AC	981 ms 4,900 KB
testcase_11	AC	982 ms 4,900 KB
testcase_12	AC	981 ms 4,904 KB
testcase_13	AC	981 ms 6,948 KB
testcase_14	AC	981 ms 6,948 KB
testcase_15	AC	981 ms 4,904 KB
testcase_16	AC	981 ms 6,948 KB
testcase_17	AC	980 ms 4,900 KB
testcase_18	AC	981 ms 6,952 KB
testcase_19	AC	980 ms 4,900 KB
testcase_20	AC	981 ms 4,904 KB
testcase_21	AC	981 ms 4,904 KB
testcase_22	AC	981 ms 4,900 KB
testcase_23	AC	981 ms 6,948 KB
testcase_24	AC	981 ms 4,908 KB
testcase_25	AC	981 ms 4,900 KB
testcase_26	AC	981 ms 4,904 KB
testcase_27	AC	981 ms 2,760 KB
testcase_28	AC	982 ms 4,900 KB
testcase_29	AC	982 ms 4,904 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
pub fn main() {
    let mut sa = SimuratedAnnealing::new().minimize().set_time_limit(0.98);
    crate::prepare!();
    sc!(n, m, mut ab: [(i32, i32); n]);
    const A: i32 = 5;
    let mut rng = Xorshift::default();
    for _ in 0..m {
        ab.push(rng.gen((0..1000, 0..1000)));
    }
    let dist = |p: (i32, i32), q: (i32, i32)| {
        let dx = p.0 - q.0;
        let dy = p.1 - q.1;
        dx * dx + dy * dy
    };
    for _ in 0..10 {
        let mut s = vec![(0i32, 0i32, 0i32); m];
        for i in 0..n {
            let j = (0..m).min_by_key(|j| dist(ab[i], ab[j + n])).unwrap();
            s[j].0 += ab[i].0;
            s[j].1 += ab[i].1;
            s[j].2 += 1;
        }
        for j in 0..m {
            ab[j + n] = if s[j].2 > 0 {
                (s[j].0 / s[j].2, s[j].1 / s[j].2)
            } else {
                rng.gen((0..1000, 0..1000))
            };
        }
    }
    let mut init_state = |k: usize, l: usize| {
        let mut state = Vec::with_capacity(k * n + l + m);
        for _ in 0..k {
            state.extend(0..n);
        }
        for _ in 0..l {
            state.extend(n..n + m);
        }
        rng.shuffle(&mut state[1..]);
        state
    };
    let mut state = init_state(2, m * 2);
    let energy = |i: usize, j: usize| {
        let d = dist(ab[i], ab[j]);
        let c = match (i < n, j < n) {
            (true, true) => A * A,
            (true, false) | (false, true) => A,
            (false, false) => 1,
        };
        d * c
    };
    let mut score: i32 = (0..state.len())
        .map(|i| energy(state[i], state[(i + 1) % state.len()]))
        .sum();
    let mut best = state.clone();
    let mut best_score = score;
    macro_rules! go {
        ($nscore:expr) => {{
            let nscore = $nscore;
            if sa.is_accepted(score as _, nscore as _) {
                score = nscore;
                if score < best_score {
                    best = state.clone();
                    best_score = score;
                }
                false
            } else {
                true
            }
        }};
    }
    while !sa.is_end() {
        match rng.gen(0..2) {
            0 => {
                let i = rng.gen(1..state.len());
                let j = rng.gen(1..state.len());
                let (i, j) = if i < j { (i, j) } else { (j, i) };
                if j - i < 2 {
                    continue;
                }
                let mut nscore = score;
                nscore -= energy(state[i - 1], state[i]);
                nscore -= energy(state[j], state[(j + 1) % state.len()]);
                state[i..=j].reverse();
                nscore += energy(state[i - 1], state[i]);
                nscore += energy(state[j], state[(j + 1) % state.len()]);
                if go!(nscore) {
                    state[i..=j].reverse();
                }
            }
            _ => {
                let i = rng.gen(1..state.len());
                let j = rng.gen(1..state.len());
                if j == i {
                    continue;
                }
                let mut nscore = score;
                nscore -= energy(state[i - 1], state[i]);
                nscore -= energy(state[i], state[(i + 1) % state.len()]);
                nscore -= energy(state[j - 1], state[j]);
                nscore -= energy(state[j], state[(j + 1) % state.len()]);
                state.swap(i, j);
                nscore += energy(state[i - 1], state[i]);
                nscore += energy(state[i], state[(i + 1) % state.len()]);
                nscore += energy(state[j - 1], state[j]);
                nscore += energy(state[j], state[(j + 1) % state.len()]);
                if go!(nscore) {
                    state.swap(i, j);
                }
            }
        }
    }
    eprintln!(
        "score = {:?}",
        (1e9 / ((best_score as f64).sqrt() + 1e3)).round() as i32
    );
    pp!(@ittup ab[n..].iter().cloned());
    let out = (0..=best.len()).map(|i| best[i % best.len()]).map(|x| {
        if x < n {
            (1, x + 1)
        } else {
            (2, x - n + 1)
        }
    });
    pp!(best.len() + 1; @ittup out);
}
#[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($))};}}
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=" - `@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);}}};(@@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 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$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)*}$($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)*);}};}}
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 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 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()?)}}}
pub use self::heuristics::SimuratedAnnealing;
mod heuristics{use super::Xorshift;#[derive(Debug)]pub struct SimuratedAnnealing{pub iter_count:usize,pub now:std::time::Instant,pub time:f64,pub temperture:f64,pub log_table:Vec<f64>,pub rand:Xorshift,pub is_maximize:bool,pub start_temp:f64,pub end_temp:f64,pub time_limit:f64,pub update_interval:usize}impl Default for SimuratedAnnealing{fn default()->Self{let now=std::time::Instant::now();let log_table=(0..Self::LOG_TABLE_SIZE).map(|i|((i*2+1)as f64/(Self::LOG_TABLE_SIZE*2)as f64).ln()).collect();Self{iter_count:0,now,time:0.,temperture:3e3,log_table,rand:Xorshift::new(Self::SEED),is_maximize:true,start_temp:3e3,end_temp:1e-8,time_limit:1.99,update_interval:0xff}}}impl SimuratedAnnealing{pub const LOG_TABLE_SIZE:usize=0x10000;pub const SEED:u64=0xbeef_cafe;pub fn new()->Self{Default::default()}pub fn minimize(mut self)->Self{self.is_maximize=false;self}pub fn set_start_temp(mut self,start_temp:f64)->Self{assert_eq!(self.iter_count,0);self.start_temp=start_temp;self.temperture=start_temp;self}pub fn set_end_temp(mut self,end_temp:f64)->Self{self.end_temp=end_temp;self}pub fn set_time_limit(mut self,time_limit:f64)->Self{self.time_limit=time_limit;self}pub fn set_update_interval(mut self,update_interval:usize)->Self{assert!(update_interval>0);self.update_interval=update_interval;self}pub fn is_accepted(&mut self,current_score:f64,next_score:f64)->bool{let diff=if self.is_maximize{next_score-current_score}else{current_score-next_score};diff>=0.||diff>self.log_table[self.rand.rand(Self::LOG_TABLE_SIZE as u64)as usize]*self.temperture}pub fn is_end(&mut self)->bool{self.iter_count+=1;if self.iter_count%self.update_interval==0{self.time=self.now.elapsed().as_secs_f64();let temp_ratio=(self.end_temp-self.start_temp)/self.time_limit;self.temperture=self.start_temp+temp_ratio*self.time;self.time>=self.time_limit}else{false}}}}
#[derive(Clone,Debug)]pub struct Xorshift{y:u64}
impl Xorshift{pub fn new(seed:u64)->Self{Xorshift{y:seed}}pub fn time()->Self{let seed=std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).ok().unwrap_or_default().as_secs()as u64;Xorshift::new(seed)}#[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(0x2b99_2ddf_a232_49d6)}}
mod random_generator{use super::*;use std::{marker::PhantomData,ops::{Range,RangeFrom,RangeInclusive,RangeTo,RangeToInclusive}};#[doc=" Trait for spec of generating random value."]pub trait RandomSpec<T>:Sized{#[doc=" Return a random value."]fn rand(&self,rng:&mut Xorshift)->T;#[doc=" Return an iterator that generates random values."]fn rand_iter(self,rng:&mut Xorshift)->RandIter<'_,T,Self>{RandIter{spec:self,rng,_marker:PhantomData}}}impl Xorshift{pub fn gen<T,R:RandomSpec<T>>(&mut self,spec:R)->T{spec.rand(self)}pub fn gen_iter<T,R:RandomSpec<T>>(&mut self,spec:R)->RandIter<'_,T,R>{spec.rand_iter(self)}}#[derive(Debug)]pub struct RandIter<'r,T,R:RandomSpec<T>>{spec:R,rng:&'r mut Xorshift,_marker:PhantomData<fn()->T>}impl<T,R:RandomSpec<T>>Iterator for RandIter<'_,T,R>{type Item=T;fn next(&mut self)->Option<Self::Item>{Some(self.spec.rand(self.rng))}}impl<T:NotEmptyStep64>RandomSpec<T>for Range<T>{fn rand(&self,rng:&mut Xorshift)->T{let count=<T as NotEmptyStep64>::steps_between(&self.start,&self.end);assert_ne!(count,0,"empty range in `RandomSpec<T> for Range<T>`");let count=randint_uniform(rng,count);<T as NotEmptyStep64>::forward_unchecked(&self.start,count)}}impl<T:NotEmptyStep64+Bounded>RandomSpec<T>for RangeFrom<T>{fn rand(&self,rng:&mut Xorshift)->T{let count=<T as NotEmptyStep64>::steps_between(&self.start,&<T as Bounded>::maximum()).wrapping_add(1);let count=randint_uniform(rng,count);<T as NotEmptyStep64>::forward_unchecked(&self.start,count)}}impl<T:NotEmptyStep64>RandomSpec<T>for RangeInclusive<T>{fn rand(&self,rng:&mut Xorshift)->T{let count=<T as NotEmptyStep64>::steps_between(self.start(),self.end()).wrapping_add(1);let count=randint_uniform(rng,count);<T as NotEmptyStep64>::forward_unchecked(self.start(),count)}}impl<T:NotEmptyStep64+Bounded>RandomSpec<T>for RangeTo<T>{fn rand(&self,rng:&mut Xorshift)->T{let count=<T as NotEmptyStep64>::steps_between(&<T as Bounded>::minimum(),&self.end);assert_ne!(count,0,"empty range in `RandomSpec<T> for RangeTo<T>`");let count=randint_uniform(rng,count);<T as NotEmptyStep64>::forward_unchecked(&<T as Bounded>::minimum(),count)}}impl<T:NotEmptyStep64+Bounded>RandomSpec<T>for RangeToInclusive<T>{fn rand(&self,rng:&mut Xorshift)->T{let count=<T as NotEmptyStep64>::steps_between(&<T as Bounded>::minimum(),&self.end).wrapping_add(1);let count=randint_uniform(rng,count);<T as NotEmptyStep64>::forward_unchecked(&<T as Bounded>::minimum(),count)}}macro_rules!random_spec_tuple_impls{($($T:ident)*,$($R:ident)*,$($v:ident)*)=>{impl<$($T),*,$($R),*>RandomSpec<($($T,)*)>for($($R,)*)where$($R:RandomSpec<$T>),*{fn rand(&self,rng:&mut Xorshift)->($($T,)*){let($($v,)*)=self;($(($v).rand(rng),)*)}}};}random_spec_tuple_impls!(A,RA,a);random_spec_tuple_impls!(A B,RA RB,a b);random_spec_tuple_impls!(A B C,RA RB RC,a b c);random_spec_tuple_impls!(A B C D,RA RB RC RD,a b c d);random_spec_tuple_impls!(A B C D E,RA RB RC RD RE,a b c d e);random_spec_tuple_impls!(A B C D E F,RA RB RC RD RE RF,a b c d e f);random_spec_tuple_impls!(A B C D E F G,RA RB RC RD RE RF RG,a b c d e f g);random_spec_tuple_impls!(A B C D E F G H,RA RB RC RD RE RF RG RH,a b c d e f g h);random_spec_tuple_impls!(A B C D E F G H I,RA RB RC RD RE RF RG RH RI,a b c d e f g h i);random_spec_tuple_impls!(A B C D E F G H I J,RA RB RC RD RE RF RG RH RI RJ,a b c d e f g h i j);macro_rules!random_spec_primitive_impls{($($t:ty)*)=>{$(impl RandomSpec<$t>for$t{fn rand(&self,_rng:&mut Xorshift)->$t{*self}})*};}random_spec_primitive_impls!(()u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize bool char);impl<T,R:RandomSpec<T>>RandomSpec<T>for&R{fn rand(&self,rng:&mut Xorshift)->T{<R as RandomSpec<T>>::rand(self,rng)}}impl<T,R:RandomSpec<T>>RandomSpec<T>for&mut R{fn rand(&self,rng:&mut Xorshift)->T{<R as RandomSpec<T>>::rand(self,rng)}}pub trait NotEmptyStep64:Clone+PartialOrd{fn steps_between(start:&Self,end:&Self)->u64;fn forward_unchecked(start:&Self,count:u64)->Self;}macro_rules!step64_impls{([$($u:ty),*],[$($i:ty),*])=>{$(impl NotEmptyStep64 for$u{fn steps_between(start:&Self,end:&Self)->u64{if*start<=*end{(*end-*start)as u64}else{panic!("empty range in `NotEmptyStep64`");}}fn forward_unchecked(start:&Self,count:u64)->Self{start+count as Self}})*$(impl NotEmptyStep64 for$i{fn steps_between(start:&Self,end:&Self)->u64{if*start<=*end{((*end as i64).wrapping_sub(*start as i64))as u64}else{panic!("empty range in `NotEmptyStep64`");}}fn forward_unchecked(start:&Self,count:u64)->Self{start+count as Self}})*};}step64_impls!([u8,u16,u32,u64,usize],[i8,i16,i32,i64,isize]);impl NotEmptyStep64 for char{fn steps_between(start:&Self,end:&Self)->u64{let start=*start as u8;let end=*end as u8;if start<=end{(end-start)as u64}else{panic!("empty range in `NotEmptyStep64`");}}fn forward_unchecked(start:&Self,count:u64)->Self{NotEmptyStep64::forward_unchecked(&(*start as u8),count)as char}}#[derive(Debug,Clone,Copy,PartialEq,Eq,PartialOrd,Ord,Hash)]#[doc=" Left-close Right-open No Empty Segment"]pub struct NotEmptySegment<T>(pub T);impl<T:RandomSpec<usize>>RandomSpec<(usize,usize)>for NotEmptySegment<T>{fn rand(&self,rng:&mut Xorshift)->(usize,usize){let n=rng.gen(&self.0)as u64;let k=randint_uniform(rng,n);let l=randint_uniform(rng,n-k)as usize;(l,l+k as usize+1)}}fn randint_uniform(rng:&mut Xorshift,k:u64)->u64{let mut v=rng.rand64();if k>0{v%=k;}v}#[macro_export]#[doc=" Return a random value using [`RandomSpec`]."]macro_rules!rand_value{($rng:expr,($($e:expr),*))=>{($($crate::rand_value!($rng,$e)),*)};($rng:expr,($($t:tt),*))=>{($($crate::rand_value!($rng,$t)),*)};($rng:expr,[$t:tt;$len:expr])=>{::std::iter::repeat_with(||$crate::rand_value!($rng,$t)).take($len).collect::<Vec<_>>()};($rng:expr,[$s:expr;$len:expr])=>{($rng).gen_iter($s).take($len).collect::<Vec<_>>()};($rng:expr,[$($t:tt)*])=>{::std::iter::repeat_with(||$crate::rand_value!($rng,$($t)*))};($rng:expr,{$s:expr})=>{($rng).gen($s)};($rng:expr,$s:expr)=>{($rng).gen($s)};}#[macro_export]#[doc=" Declare random values using [`RandomSpec`]."]macro_rules!rand{($rng:expr)=>{};($rng:expr,)=>{};($rng:expr,$var:tt:$t:tt)=>{let$var=$crate::rand_value!($rng,$t);};($rng:expr,mut$var:tt:$t:tt)=>{let mut$var=$crate::rand_value!($rng,$t);};($rng:expr,$var:tt:$t:tt,$($rest:tt)*)=>{let$var=$crate::rand_value!($rng,$t);rand!($rng,$($rest)*)};($rng:expr,mut$var:tt:$t:tt,$($rest:tt)*)=>{let mut$var=$crate::rand_value!($rng,$t);rand!($rng,$($rest)*)};}}
pub use random_generator::{NotEmptySegment,RandIter,RandomSpec};
pub use self::bounded::Bounded;
mod bounded{#[doc=" Trait for max/min bounds"]pub trait Bounded:Sized+PartialOrd{fn maximum()->Self;fn minimum()->Self;fn is_maximum(&self)->bool{self==&Self::maximum()}fn is_minimum(&self)->bool{self==&Self::minimum()}fn set_maximum(&mut self){*self=Self::maximum()}fn set_minimum(&mut self){*self=Self::minimum()}}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);macro_rules!bounded_tuple_impls{(@impl$($T:ident)*)=>{impl<$($T:Bounded),*>Bounded for($($T,)*){fn maximum()->Self{($(<$T as Bounded>::maximum(),)*)}fn minimum()->Self{($(<$T as Bounded>::minimum(),)*)}}};(@inner$($T:ident)*,)=>{bounded_tuple_impls!(@impl$($T)*);};(@inner$($T:ident)*,$U:ident$($Rest:ident)*)=>{bounded_tuple_impls!(@impl$($T)*);bounded_tuple_impls!(@inner$($T)*$U,$($Rest)*);};($T:ident$($Rest:ident)*)=>{bounded_tuple_impls!(@inner$T,$($Rest)*);};}bounded_tuple_impls!(A B C D E F G H I J);impl Bounded for(){fn maximum()->Self{}fn minimum()->Self{}}impl Bounded for bool{fn maximum()->Self{true}fn minimum()->Self{false}}impl<T>Bounded for Option<T>where T:Bounded{fn maximum()->Self{Some(<T as Bounded>::maximum())}fn minimum()->Self{None}}impl<T>Bounded for std::cmp::Reverse<T>where T:Bounded{fn maximum()->Self{std::cmp::Reverse(<T as Bounded>::minimum())}fn minimum()->Self{std::cmp::Reverse(<T as Bounded>::maximum())}}}
yukicoder

結果

テストケース

ソースコード
