#938961 (Rust) No.464 PPAP

提出ソース

結果

問題	No.464 PPAP
ユーザー	37kt
提出日時	2023-12-18 11:00:13
言語	Rust (1.77.0 + proconio)
結果	CE (最新) AC (最初)
実行時間	-
コード長	32,206 bytes
コンパイル時間	13,004 ms
コンパイル使用メモリ	393,840 KB
最終ジャッジ日時	2024-09-27 08:19:46
合計ジャッジ時間	13,644 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

このコードへのチャレンジ
（要ログイン）

コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ

error[E0659]: `proconio` is ambiguous
 --> src/main.rs:4:5
  |
4 | use proconio::{
  |     ^^^^^^^^ ambiguous name
  |
  = note: ambiguous because of a conflict between a name from a glob import and an outer scope during import or macro resolution
  = note: `proconio` could refer to a crate passed with `--extern`
  = help: use `::proconio` to refer to this crate unambiguously
note: `proconio` could also refer to the module imported here
 --> src/main.rs:1:9
  |
1 | pub use __cargo_equip::prelude::*;
  |         ^^^^^^^^^^^^^^^^^^^^^^^^^
  = help: consider adding an explicit import of `proconio` to disambiguate
  = help: or use `crate::proconio` to refer to this module unambiguously

For more information about this error, try `rustc --explain E0659`.
error: could not compile `main` (bin "main") due to 1 previous error

ソースコード

raw source code

pub use __cargo_equip::prelude::*;

#[allow(unused_imports)]
use proconio::{
    input,
    marker::{Bytes, Chars, Usize1},
};
use rolling_hash::RollingHashModInt61;

fn main() {
    input! {
        s: Bytes,
    }
    let rh1 = RollingHashModInt61::new(&s);
    let mut t = s.clone();
    t.reverse();
    let rh2 = RollingHashModInt61::new(&t);
    let n = s.len();
    let mut f = vec![vec![false; n + 1]; n + 1];
    for i in 0..n {
        for j in i..=n {
            f[i][j] = rh1.get(i..j) == rh2.get(n - j..n - i);
        }
    }
    let mut dp = vec![[0usize; 5]; n + 1];
    dp[0][0] += 1;
    for i in 0..n {
        for j in 0..4 {
            for ni in i + 1..=n {
                if f[i][ni] || j == 2 {
                    dp[ni][j + 1] += dp[i][j];
                }
            }
        }
    }
    println!("{}", dp[n][4]);
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)`                                   licensed under `MIT/Apache-2.0`    as `crate::__cargo_equip::crates::__lazy_static_1_4_0`
///  - `modint61 0.1.0 (path+██████████████████████████████████████████████████)`           published in **missing** licensed under `CC0-1.0`           as `crate::__cargo_equip::crates::modint61`
///  - `nimber 0.1.0 (path+████████████████████████████████████████████████)`               published in **missing** licensed under `CC0-1.0`           as `crate::__cargo_equip::crates::nimber`
///  - `proconio 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)`                                      licensed under `MIT OR Apache-2.0` as `crate::__cargo_equip::crates::proconio`
///  - `random 0.1.0 (path+████████████████████████████████████████████████)`               published in **missing** licensed under `CC0-1.0`           as `crate::__cargo_equip::crates::random`
///  - `rolling-hash 0.1.0 (path+████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0`           as `crate::__cargo_equip::crates::rolling_hash`
/// 
///  # Procedural macros
/// 
///  - `proconio-derive 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT OR Apache-2.0`
/// 
///  # License and Copyright Notices
/// 
///  - `lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)`
/// 
///      ```text
///      Copyright (c) 2010 The Rust Project Developers
/// 
///      Permission is hereby granted, free of charge, to any
///      person obtaining a copy of this software and associated
///      documentation files (the "Software"), to deal in the
///      Software without restriction, including without
///      limitation the rights to use, copy, modify, merge,
///      publish, distribute, sublicense, and/or sell copies of
///      the Software, and to permit persons to whom the Software
///      is furnished to do so, subject to the following
///      conditions:
/// 
///      The above copyright notice and this permission notice
///      shall be included in all copies or substantial portions
///      of the Software.
/// 
///      THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
///      ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
///      TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
///      PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
///      SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
///      CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
///      OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
///      IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
///      DEALINGS IN THE SOFTWARE.
///      ```
/// 
///  - `proconio 0.4.3 (registry+https://github.com/rust-lang/crates.io-index)`
/// 
///      ```text
///      The MIT License
///      Copyright 2019 (C) statiolake <statiolake@gmail.com>
/// 
///      Permission is hereby granted, free of charge, to any person obtaining a copy of
///      this software and associated documentation files (the "Software"), to deal in
///      the Software without restriction, including without limitation the rights to
///      use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
///      the Software, and to permit persons to whom the Software is furnished to do so,
///      subject to the following conditions:
/// 
///      The above copyright notice and this permission notice shall be included in all
///      copies or substantial portions of the Software.
/// 
///      THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
///      IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
///      FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
///      COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
///      IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
///      CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
/// 
///      Copyright for original `input!` macro is held by Hideyuki Tanaka, 2019.  The
///      original macro is licensed under BSD 3-clause license.
/// 
///      Redistribution and use in source and binary forms, with or without
///      modification, are permitted provided that the following conditions are met:
/// 
///      1. Redistributions of source code must retain the above copyright notice, this
///         list of conditions and the following disclaimer.
/// 
///      2. Redistributions in binary form must reproduce the above copyright notice,
///         this list of conditions and the following disclaimer in the documentation
///         and/or other materials provided with the distribution.
/// 
///      3. Neither the name of the copyright holder nor the names of its contributors
///         may be used to endorse or promote products derived from this software
///         without specific prior written permission.
/// 
///      THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
///      ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
///      WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
///      DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
///      FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
///      DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
///      SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
///      CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
///      OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
///      OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
///      ```
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod __lazy_static_1_4_0 {#![no_std]use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;pub use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;#[path="inline_lazy.rs"]pub mod lazy{use crate::__cargo_equip::preludes::__lazy_static_1_4_0::*;extern crate core;extern crate std;use self::std::prelude::v1::*;use self::std::cell::Cell;use self::std::hint::unreachable_unchecked;use self::std::sync::Once;#[allow(deprecated)]pub use self::std::sync::ONCE_INIT;pub struct Lazy<T:Sync>(Cell<Option<T>>,Once);impl<T:Sync>Lazy<T>{#[allow(deprecated)]pub const INIT:Self=Lazy(Cell::new(None),ONCE_INIT);#[inline(always)]pub fn get<F>(&'static self,f:F)->&T where F:FnOnce()->T,{self.1.call_once(||{self.0.set(Some(f()));});unsafe{match*self.0.as_ptr(){Some(ref x)=>x,None=>{debug_assert!(false,"attempted to derefence an uninitialized lazy static. This is a bug");unreachable_unchecked()},}}}}unsafe impl<T:Sync>Sync for Lazy<T>{}#[macro_export]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create{($NAME:ident,$T:ty)=>{static$NAME:$crate::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy<$T> =$crate::__cargo_equip::crates::__lazy_static_1_4_0::lazy::Lazy::INIT;};}macro_rules!__lazy_static_create{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create!{$($tt)*})}}pub use core::ops::Deref as __Deref;#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal{($(#[$attr:meta])*($($vis:tt)*)static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!(@MAKE TY,$(#[$attr])*,($($vis)*),$N);__lazy_static_internal!(@TAIL,$N:$T=$e);lazy_static!($($t)*);};(@TAIL,$N:ident:$T:ty=$e:expr)=>{impl$crate::__cargo_equip::crates::__lazy_static_1_4_0::__Deref for$N{type Target=$T;fn deref(&self)->&$T{#[inline(always)]fn __static_ref_initialize()->$T{$e}#[inline(always)]fn __stability()->&'static$T{__lazy_static_create!(LAZY,$T);LAZY.get(__static_ref_initialize)}__stability()}}impl$crate::__cargo_equip::crates::__lazy_static_1_4_0::LazyStatic for$N{fn initialize(lazy:&Self){let _=&**lazy;}}};(@MAKE TY,$(#[$attr:meta])*,($($vis:tt)*),$N:ident)=>{#[allow(missing_copy_implementations)]#[allow(non_camel_case_types)]#[allow(dead_code)]$(#[$attr])*$($vis)*struct$N{__private_field:()}#[doc(hidden)]$($vis)*static$N:$N=$N{__private_field:()};};()=>()}macro_rules!__lazy_static_internal{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal!{$($tt)*})}#[macro_export(local_inner_macros)]macro_rules!__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static{($(#[$attr:meta])*static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*()static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub)static ref$N:$T=$e;$($t)*);};($(#[$attr:meta])*pub($($vis:tt)+)static ref$N:ident:$T:ty=$e:expr;$($t:tt)*)=>{__lazy_static_internal!($(#[$attr])*(pub($($vis)+))static ref$N:$T=$e;$($t)*);};()=>()}macro_rules!lazy_static{($($tt:tt)*)=>(crate::__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static!{$($tt)*})}pub trait LazyStatic{fn initialize(lazy:&Self);}pub fn initialize<T:LazyStatic>(lazy:&T){LazyStatic::initialize(lazy);}}
        pub mod modint61 {use std::{fmt::{Debug,Display},ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign},};const P:u64=(1<<61)-1;#[derive(Clone,Copy,Default,PartialEq,Eq,Hash)]pub struct ModInt61(u64);impl ModInt61{#[inline]pub fn new(x:impl Into<ModInt61>)->Self{x.into()}#[inline]pub fn raw(val:u64)->Self{Self(val)}#[inline]pub fn val(self)->u64{self.0}#[inline]pub fn modulus()->u64{P}pub fn pow(mut self,mut k:usize)->Self{let mut res=Self::raw(1);while k!=0{if k&1!=0{res*=self;}k>>=1;self*=self;}res}pub fn inv(self)->Self{self.pow(P as usize-2)}}impl Display for ModInt61{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.0)}}impl Debug for ModInt61{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.0)}}impl Neg for ModInt61{type Output=Self;fn neg(self)->Self::Output{if self.0==0{self}else{Self(P-self.0)}}}impl Neg for&ModInt61{type Output=ModInt61;fn neg(self)->Self::Output{-*self}}impl AddAssign for ModInt61{fn add_assign(&mut self,rhs:Self){self.0+=rhs.0;if self.0>=P{self.0-=P;}}}impl SubAssign for ModInt61{fn sub_assign(&mut self,rhs:Self){*self+=-rhs;}}impl MulAssign for ModInt61{fn mul_assign(&mut self,rhs:Self){let t=self.0 as u128*rhs.0 as u128;let t=(t>>61)as u64+(t as u64&P);self.0=if t>=P{t-P}else{t}}}impl DivAssign for ModInt61{fn div_assign(&mut self,rhs:Self){*self*=rhs.inv();}}macro_rules!impl_from_integer{($(($t1:ty,$t2:ty)),*)=>{$(impl From<$t1>for ModInt61{fn from(x:$t1)->Self{Self((x as$t2).rem_euclid(P as$t2)as u64)}})*};}impl_from_integer!((i8,i64),(i16,i64),(i32,i64),(i64,i64),(isize,i64),(i128,i128),(u8,u64),(u16,u64),(u32,u64),(u64,u64),(usize,u64),(u128,u128));macro_rules!impl_ops{($($trait:ident,$trait_assign:ident,$fn:ident,$fn_assign:ident,)*)=>{$(impl$trait_assign<&ModInt61>for ModInt61{fn$fn_assign(&mut self,rhs:&ModInt61){self.$fn_assign(*rhs);}}impl$trait<&ModInt61>for ModInt61{type Output=ModInt61;fn$fn(mut self,rhs:&ModInt61)->Self::Output{self.$fn_assign(*rhs);self}}impl$trait<ModInt61>for&ModInt61{type Output=ModInt61;fn$fn(self,rhs:ModInt61)->Self::Output{(*self).$fn(rhs)}}impl$trait<ModInt61>for ModInt61{type Output=ModInt61;fn$fn(mut self,rhs:ModInt61)->Self::Output{self.$fn_assign(rhs);self}}impl$trait<&ModInt61>for&ModInt61{type Output=ModInt61;fn$fn(self,rhs:&ModInt61)->Self::Output{(*self).$fn(&*rhs)}})*};}impl_ops!{Add,AddAssign,add,add_assign,Sub,SubAssign,sub,sub_assign,Mul,MulAssign,mul,mul_assign,Div,DivAssign,div,div_assign,}}
        pub mod nimber {use std::{convert::TryInto,fmt::{Debug,Display},mem::swap,ops::{Add,AddAssign,Mul,MulAssign,Neg,Sub,SubAssign},str::FromStr,};#[derive(Clone,Copy,PartialEq,Eq,Hash,Default)]pub struct Nimber(usize);impl FromStr for Nimber{type Err=<usize as FromStr>::Err;fn from_str(s:&str)->Result<Self,Self::Err>{Ok(Nimber(s.parse::<usize>()?))}}impl<T,E>From<T>for Nimber where T:TryInto<usize,Error=E>,E:Debug,{fn from(x:T)->Self{Nimber(x.try_into().unwrap())}}impl Nimber{pub fn new<T,E>(x:T)->Self where T:TryInto<usize,Error=E>,E:Debug,{Self::from(x)}pub fn val(&self)->usize{self.0}}impl Display for Nimber{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.0)}}impl Debug for Nimber{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.0)}}impl Neg for Nimber{type Output=Self;fn neg(self)->Self::Output{self}}impl Neg for&Nimber{type Output=Nimber;fn neg(self)->Self::Output{*self}}impl AddAssign for Nimber{fn add_assign(&mut self,rhs:Self){self.0^=rhs.0;}}impl SubAssign for Nimber{fn sub_assign(&mut self,rhs:Self){self.0^=rhs.0;}}impl MulAssign for Nimber{fn mul_assign(&mut self,rhs:Self){PRECALC.with(|precalc|{SMALL.with(|small|{let mut res=0;for d in 0..8{for e in 0..8{res^=precalc[d][e][small[self.0>>d*8&255][rhs.0>>e*8&255]];}}self.0=res;})})}}macro_rules!impl_ops{($($trait:ident,$trait_assign:ident,$fn:ident,$fn_assign:ident,)*)=>{$(impl$trait_assign<&Nimber>for Nimber{fn$fn_assign(&mut self,rhs:&Nimber){self.$fn_assign(*rhs);}}impl$trait<&Nimber>for Nimber{type Output=Nimber;fn$fn(mut self,rhs:&Nimber)->Self::Output{self.$fn_assign(*rhs);self}}impl$trait<Nimber>for&Nimber{type Output=Nimber;fn$fn(self,rhs:Nimber)->Self::Output{(*self).$fn(rhs)}}impl$trait<Nimber>for Nimber{type Output=Nimber;fn$fn(mut self,rhs:Nimber)->Self::Output{self.$fn_assign(rhs);self}}impl$trait<&Nimber>for&Nimber{type Output=Nimber;fn$fn(self,rhs:&Nimber)->Self::Output{(*self).$fn(&*rhs)}})*};}impl_ops!{Add,AddAssign,add,add_assign,Sub,SubAssign,sub,sub_assign,Mul,MulAssign,mul,mul_assign,}fn rec(mut x:usize,mut y:usize)->usize{if x==0||y==0{return 0;}if x<y{swap(&mut x,&mut y);}if y==1{return x;}for k in(0..6).rev(){let shift=1<<k;let mask=(1<<shift)-1;if y>>shift!=0{let v00=rec(x&mask,y&mask);let v01=rec(x&mask,y>>shift);let v10=rec(x>>shift,y&mask);let v11=rec(x>>shift,y>>shift);return v00^(v01^v10^v11)<<shift^rec(v11,1<<shift-1);}else if x>>shift!=0{return rec(x>>shift,y)<<shift^rec(x&mask,y);}}unreachable!()}fn small()->Box<[Box<[usize]>]>{let mut t=vec![vec![0;256].into_boxed_slice();256].into_boxed_slice();for i in 0..256{for j in 0..256{t[i][j]=rec(i,j);}}t}fn precalc()->Box<[Box<[Box<[usize]>]>]>{let mut t=vec![vec![vec![0;256].into_boxed_slice();8].into_boxed_slice();8].into_boxed_slice();for d in 0..8{for e in 0..8{let p=rec(1<<d*8,1<<e*8);for i in 0..256{t[d][e][i]=rec(p,i);}}}t}thread_local!{static SMALL:Box<[Box<[usize]>]> =small();static PRECALC:Box<[Box<[Box<[usize]>]>]> =precalc();}}
        pub mod proconio {#![allow(clippy::needless_doctest_main,clippy::print_literal)]use crate::__cargo_equip::preludes::proconio::*;pub use crate::__cargo_equip::macros::proconio::*;pub use proconio_derive::*;pub mod marker{use crate::__cargo_equip::preludes::proconio::*;use crate::__cargo_equip::crates::proconio::source::{Readable,Source};use std::io::BufRead;pub enum Chars{}impl Readable for Chars{type Output=Vec<char>;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Vec<char>{source.next_token_unwrap().chars().collect()}}pub enum Bytes{}impl Readable for Bytes{type Output=Vec<u8>;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Vec<u8>{source.next_token_unwrap().bytes().collect()}}pub enum Usize1{}impl Readable for Usize1{type Output=usize;fn read<R:BufRead,S:Source<R>>(source:&mut S)->usize{usize::read(source).checked_sub(1).expect("attempted to read the value 0 as a Usize1")}}pub enum Isize1{}impl Readable for Isize1{type Output=isize;fn read<R:BufRead,S:Source<R>>(source:&mut S)->isize{isize::read(source).checked_sub(1).unwrap_or_else(||{panic!(concat!("attempted to read the value {} as a Isize1:"," the value is isize::MIN and cannot be decremented"),std::isize::MIN,)})}}}pub mod source{use crate::__cargo_equip::preludes::proconio::*;use std::any::type_name;use std::fmt::Debug;use std::io::BufRead;use std::str::FromStr;pub mod line{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::str::SplitWhitespace;pub struct LineSource<R:BufRead>{tokens:Peekable<SplitWhitespace<'static>>,current_context:Box<str>,reader:R,}impl<R:BufRead>LineSource<R>{pub fn new(reader:R)->LineSource<R>{LineSource{current_context:"".to_string().into_boxed_str(),tokens:"".split_whitespace().peekable(),reader,}}fn prepare(&mut self){while self.tokens.peek().is_none(){let mut line=String::new();let num_bytes=self.reader.read_line(&mut line).expect("failed to get linel maybe an IO error.");if num_bytes==0{return;}self.current_context=line.into_boxed_str();self.tokens=unsafe{std::mem::transmute::<_,&'static str>(&*self.current_context)}.split_whitespace().peekable();}}}impl<R:BufRead>Source<R>for LineSource<R>{fn next_token(&mut self)->Option<&str>{self.prepare();self.tokens.next()}fn is_empty(&mut self)->bool{self.prepare();self.tokens.peek().is_none()}}use std::io::BufReader;impl<'a>From<&'a str>for LineSource<BufReader<&'a[u8]>>{fn from(s:&'a str)->LineSource<BufReader<&'a[u8]>>{LineSource::new(BufReader::new(s.as_bytes()))}}}pub mod once{use crate::__cargo_equip::preludes::proconio::*;use super::Source;use std::io::BufRead;use std::iter::Peekable;use std::marker::PhantomData;use std::str::SplitWhitespace;pub struct OnceSource<R:BufRead>{tokens:Peekable<SplitWhitespace<'static>>,context:Box<str>,_read:PhantomData<R>,}impl<R:BufRead>OnceSource<R>{pub fn new(mut source:R)->OnceSource<R>{let mut context=String::new();source.read_to_string(&mut context).expect("failed to read from source; maybe an IO error.");let context=context.into_boxed_str();let mut res=OnceSource{context,tokens:"".split_whitespace().peekable(),_read:PhantomData,};use std::mem;let context:&'static str=unsafe{mem::transmute(&*res.context)};res.tokens=context.split_whitespace().peekable();res}}impl<R:BufRead>Source<R>for OnceSource<R>{fn next_token(&mut self)->Option<&str>{self.tokens.next()}fn is_empty(&mut self)->bool{self.tokens.peek().is_none()}}use std::io::BufReader;impl<'a>From<&'a str>for OnceSource<BufReader<&'a[u8]>>{fn from(s:&'a str)->OnceSource<BufReader<&'a[u8]>>{OnceSource::new(BufReader::new(s.as_bytes()))}}}pub mod auto{use crate::__cargo_equip::preludes::proconio::*;#[cfg(debug_assertions)]pub use super::line::LineSource as AutoSource;#[cfg(not(debug_assertions))]pub use super::once::OnceSource as AutoSource;}pub trait Source<R:BufRead>{fn next_token(&mut self)->Option<&str>;fn is_empty(&mut self)->bool;fn next_token_unwrap(&mut self)->&str{self.next_token().expect(concat!("failed to get the next token; ","maybe reader reached an end of input. ","ensure that arguments for `input!` macro is correctly ","specified to match the problem input."))}}impl<R:BufRead,S:Source<R>>Source<R>for&'_ mut S{fn next_token(&mut self)->Option<&str>{(*self).next_token()}fn is_empty(&mut self)->bool{(*self).is_empty()}}pub trait Readable{type Output;fn read<R:BufRead,S:Source<R>>(source:&mut S)->Self::Output;}impl<T:FromStr>Readable for T where T::Err:Debug,{type Output=T;fn read<R:BufRead,S:Source<R>>(source:&mut S)->T{let token=source.next_token_unwrap();match token.parse(){Ok(v)=>v,Err(e)=>panic!(concat!("failed to parse the input `{input}` ","to the value of type `{ty}`: {err:?}; ","ensure that the input format is collectly specified ","and that the input value must handle specified type.",),input=token,ty=type_name::<T>(),err=e,),}}}}use crate::__cargo_equip::crates::proconio::source::auto::AutoSource;use lazy_static::lazy_static;use std::io;use std::io::{BufReader,Stdin};use std::sync::Mutex;pub use crate::__cargo_equip::crates::proconio::source::Readable as __Readable;lazy_static!{#[doc(hidden)]pub static ref STDIN_SOURCE:Mutex<AutoSource<BufReader<Stdin>>>=Mutex::new(AutoSource::new(BufReader::new(io::stdin())));}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_input{(@from[$source:expr]@rest)=>{};(@from[$source:expr]@rest mut$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[mut]@rest$($rest)*}};(@from[$source:expr]@rest$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@rest$var:tt:$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!{@from[$source]@mut[$($mut)*]@var$var@kind[]@rest$($rest)*}};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest)=>{let$($mut)*$var=$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*]@rest);$crate::__cargo_equip::crates::proconio::input!(@from[$source]@rest$($rest)*);};(@from[$source:expr]@mut[$($mut:tt)?]@var$var:tt@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::input!(@from[$source]@mut[$($mut)*]@var$var@kind[$($kind)*$tt]@rest$($rest)*);};(from$source:expr,$($rest:tt)*)=>{#[allow(unused_variables,unused_mut)]let mut s=$source;$crate::__cargo_equip::crates::proconio::input!{@from[&mut s]@rest$($rest)*}};($($rest:tt)*)=>{let mut locked_stdin=$crate::__cargo_equip::crates::proconio::STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program.  ","If this issue repeatedly occur, this is a bug in `proconio`.  ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));$crate::__cargo_equip::crates::proconio::input!{@from[&mut*locked_stdin]@rest$($rest)*}drop(locked_stdin);};}macro_rules!input{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_input!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_read_value{(@source[$source:expr]@kind[[$($kind:tt)*]])=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[]@rest$($kind)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest)=>{{let len=<usize as$crate::__cargo_equip::crates::proconio::__Readable>::read($source);$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[[$($kind)*;len]])}};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest;$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*]@len[$($rest)*])};(@array@source[$source:expr]@kind[$($kind:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@array@source[$source]@kind[$($kind)*$tt]@rest$($rest)*)};(@array@source[$source:expr]@kind[$($kind:tt)*]@len[$($len:tt)*])=>{{let len=$($len)*;(0..len).map(|_|$crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*])).collect::<Vec<_>>()}};(@source[$source:expr]@kind[($($kinds:tt)*)])=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[]@current[]@rest$($kinds)*)};(@tuple@source[$source:expr]@kinds[$([$($kind:tt)*])*]@current[]@rest)=>{($($crate::__cargo_equip::crates::proconio::read_value!(@source[$source]@kind[$($kind)*]),)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*[$($curr)*]]@current[]@rest$($rest)*)};(@tuple@source[$source:expr]@kinds[$($kinds:tt)*]@current[$($curr:tt)*]@rest$tt:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::proconio::read_value!(@tuple@source[$source]@kinds[$($kinds)*]@current[$($curr)*$tt]@rest$($rest)*)};(@source[$source:expr]@kind[])=>{compile_error!(concat!("Reached unreachable statement while parsing macro input.  ","This is a bug in `proconio`.  ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));};(@source[$source:expr]@kind[$kind:ty])=>{<$kind as$crate::__cargo_equip::crates::proconio::__Readable>::read($source)}}macro_rules!read_value{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_proconio_read_value!{$($tt)*})}pub fn is_stdin_empty()->bool{use crate::__cargo_equip::crates::proconio::source::Source;let mut lock=STDIN_SOURCE.lock().expect(concat!("failed to lock the stdin; please re-run this program.  ","If this issue repeatedly occur, this is a bug in `proconio`.  ","Please report this issue from ","<https://github.com/statiolake/proconio-rs/issues>."));lock.is_empty()}}
        pub mod __proconio_derive_0_2_1 {pub use crate::__cargo_equip::macros::__proconio_derive_0_2_1::*;#[macro_export]macro_rules!__cargo_equip_macro_def___proconio_derive_0_2_1_derive_readable{($(_:tt)*)=>(::std::compile_error!("`derive_readable` from `proconio-derive 0.2.1` should have been expanded");)}#[macro_export]macro_rules!__cargo_equip_macro_def___proconio_derive_0_2_1_fastout{($(_:tt)*)=>(::std::compile_error!("`fastout` from `proconio-derive 0.2.1` should have been expanded");)}}
        pub mod random {#[derive(Clone)]pub struct Pcg64Fast(u128);const R:f64=1.0/0xffff_ffff_ffff_ffff_u64 as f64;impl Default for Pcg64Fast{fn default()->Self{Self(std::time::SystemTime::now().duration_since(std::time::UNIX_EPOCH).unwrap().as_nanos()|1,)}}impl Pcg64Fast{#[inline]pub fn new(state:u128)->Self{Self(state|1)}#[inline]pub fn u32(&mut self)->u32{self.u64()as u32}#[inline(always)]pub fn u64(&mut self)->u64{self.0=self.0.wrapping_mul(0x2360_ED05_1FC6_5DA4_4385_DF64_9FCC_F645);let rot=(self.0>>122)as u32;let xsl=(self.0>>64)as u64^self.0 as u64;xsl.rotate_right(rot)}#[inline]pub fn f64(&mut self)->f64{self.u64()as f64*R}}}
        pub mod rolling_hash {use crate::__cargo_equip::preludes::rolling_hash::*;use std::{cmp::Ordering,marker::PhantomData,ops::{Add,Bound,Mul,Neg,RangeBounds},};use modint61::ModInt61;use nimber::Nimber;use random::Pcg64Fast;pub type RollingHashModInt61<'a,C> =RollingHash<'a,C,ModInt61>;pub type RollingHashNimber<'a,C> =RollingHash<'a,C,Nimber>;pub struct GenBaseImpl<T>(PhantomData<fn()->T>);pub trait GenBase{type H;fn base()->Self::H;}impl GenBase for GenBaseImpl<Nimber>{type H=Nimber;fn base()->Nimber{fn gen()->Nimber{let mut rng=Pcg64Fast::default();Nimber::new(rng.u64())}thread_local!{static BASE:Nimber=gen();}BASE.with(|base|*base)}}impl GenBase for GenBaseImpl<ModInt61>{type H=ModInt61;fn base()->ModInt61{fn gen()->ModInt61{const FACTORS:[usize;12]=[2,3,5,7,11,13,31,41,61,151,331,1321];let mut rng=Pcg64Fast::default();loop{let x=ModInt61::new(rng.u64());if FACTORS.iter().all(|&f|x.pow((ModInt61::modulus()as usize-1)/f).val()>1){return x;}}}thread_local!{static BASE:ModInt61=gen();}BASE.with(|base|*base)}}#[derive(Hash,PartialEq,Eq,Clone,Copy)]pub struct Hash<H>where H:Copy+Eq+Add<Output=H>+Mul<Output=H>+Neg<Output=H>,{hash:H,pow:H,}impl<H>Hash<H>where H:Copy+Eq+Add<Output=H>+Mul<Output=H>+Neg<Output=H>,{pub fn val(&self)->H{self.hash}pub fn concat(&self,other:Self)->Self{Self{hash:self.hash*other.pow+other.hash,pow:self.pow*other.pow,}}}#[derive(Clone)]pub struct RollingHash<'a,C,H>where C:Copy+Eq+Into<H>,H:Copy+Eq+Add<Output=H>+Mul<Output=H>+Neg<Output=H>,GenBaseImpl<H>:GenBase<H=H>,{s:&'a[C],hs:Box<[H]>,pw:Box<[H]>,}impl<'a,C,H>RollingHash<'a,C,H>where C:Copy+Eq+Into<H>,H:Copy+Eq+From<u64>+Add<Output=H>+Mul<Output=H>+Neg<Output=H>,GenBaseImpl<H>:GenBase<H=H>,{pub fn new(s:&'a[C])->Self{let n=s.len();let base=GenBaseImpl::<H>::base();let mut hs=vec![H::from(0);n+1];let mut pw=vec![H::from(1);n+1];for i in 0..n{hs[i+1]=hs[i]*base+s[i].into();pw[i+1]=pw[i]*base;}Self{s,hs:hs.into_boxed_slice(),pw:pw.into_boxed_slice(),}}pub fn base()->H{GenBaseImpl::<H>::base()}pub fn len(&self)->usize{self.s.len()}pub fn get(&self,index:impl RangeBounds<usize>)->Hash<H>{let(l,r)=range_to_pair(index,self.len());Hash{hash:self.hs[l]*-self.pw[r-l]+self.hs[r],pow:self.pw[r-l],}}pub fn lcp(&self,index1:impl RangeBounds<usize>,other:&Self,index2:impl RangeBounds<usize>,)->usize{let(l1,r1)=range_to_pair(index1,self.len());let(l2,r2)=range_to_pair(index2,other.len());let n=(r1-l1).min(r2-l2);let mut ok=0;let mut ng=n+1;while ok+1<ng{let md=(ok+ng)/2;if self.get(l1..l1+md)==other.get(l2..l2+md){ok=md;}else{ng=md;}}ok}}impl<'a,C,H>RollingHash<'a,C,H>where C:Copy+Eq+Into<H>+Ord,H:Copy+Eq+From<u64>+Add<Output=H>+Mul<Output=H>+Neg<Output=H>,GenBaseImpl<H>:GenBase<H=H>,{pub fn compare(&self,index1:impl RangeBounds<usize>,other:&Self,index2:impl RangeBounds<usize>,)->Ordering{let(l1,r1)=range_to_pair(index1,self.len());let(l2,r2)=range_to_pair(index2,other.len());let n=self.lcp(l1..r1,other,l2..r2);if l1+n==r1{if l2+n==r2{Ordering::Equal}else{Ordering::Less}}else if l2+n==r2{Ordering::Greater}else{self.s[l1+n].cmp(&other.s[l2+n])}}}fn range_to_pair(range:impl RangeBounds<usize>,n:usize)->(usize,usize){let l=match range.start_bound(){Bound::Included(&l)=>l,Bound::Excluded(&l)=>l+1,Bound::Unbounded=>0,};let r=match range.end_bound(){Bound::Included(&r)=>r+1,Bound::Excluded(&r)=>r,Bound::Unbounded=>n,};(l,r)}}
    }

    pub(crate) mod macros {
        pub mod __lazy_static_1_4_0 {pub use crate::{__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_create as __lazy_static_create,__cargo_equip_macro_def___lazy_static_1_4_0___lazy_static_internal as __lazy_static_internal,__cargo_equip_macro_def___lazy_static_1_4_0_lazy_static as lazy_static};}
        pub mod modint61 {}
        pub mod nimber {}
        pub mod proconio {pub use crate::{__cargo_equip_macro_def_proconio_input as input,__cargo_equip_macro_def_proconio_read_value as read_value};}
        pub mod __proconio_derive_0_2_1 {pub use crate::{__cargo_equip_macro_def___proconio_derive_0_2_1_derive_readable as derive_readable,__cargo_equip_macro_def___proconio_derive_0_2_1_fastout as fastout};}
        pub mod random {}
        pub mod rolling_hash {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::{crates::*,macros::__lazy_static_1_4_0::*};}

    mod preludes {
        pub mod __lazy_static_1_4_0 {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;}
        pub mod modint61 {}
        pub mod nimber {}
        pub mod proconio {pub(in crate::__cargo_equip)use crate::__cargo_equip::macros::__lazy_static_1_4_0::*;pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__lazy_static_1_4_0 as lazy_static,__proconio_derive_0_2_1 as proconio_derive};}
        pub mod __proconio_derive_0_2_1 {}
        pub mod random {}
        pub mod rolling_hash {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{modint61,nimber,random};}
    }
}

yukicoder

結果

コンパイルメッセージ

ソースコード