#974431 (Rust) No.2734 Addition and Multiplication in yukicoder (Hard)

提出ソース

結果

問題	No.2734 Addition and Multiplication in yukicoder (Hard)
ユーザー	CoCo_Japan_pan
提出日時	2024-04-19 22:56:12
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	532 ms / 5,000 ms
コード長	12,046 bytes
コンパイル時間	15,999 ms
コンパイル使用メモリ	377,972 KB
実行使用メモリ	10,112 KB
最終ジャッジ日時	2024-10-11 16:56:36
合計ジャッジ時間	25,823 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	0 ms 5,248 KB
testcase_03	AC	1 ms 5,248 KB
testcase_04	AC	1 ms 5,248 KB
testcase_05	AC	0 ms 5,248 KB
testcase_06	AC	1 ms 5,248 KB
testcase_07	AC	1 ms 5,248 KB
testcase_08	AC	1 ms 5,248 KB
testcase_09	AC	1 ms 5,248 KB
testcase_10	AC	1 ms 5,248 KB
testcase_11	AC	1 ms 5,248 KB
testcase_12	AC	1 ms 5,248 KB
testcase_13	AC	1 ms 5,248 KB
testcase_14	AC	1 ms 5,248 KB
testcase_15	AC	1 ms 5,248 KB
testcase_16	AC	1 ms 5,248 KB
testcase_17	AC	437 ms 7,552 KB
testcase_18	AC	439 ms 7,808 KB
testcase_19	AC	1 ms 5,248 KB
testcase_20	AC	1 ms 5,248 KB
testcase_21	AC	1 ms 5,248 KB
testcase_22	AC	532 ms 9,984 KB
testcase_23	AC	514 ms 10,112 KB
testcase_24	AC	513 ms 9,856 KB
testcase_25	AC	528 ms 9,984 KB
testcase_26	AC	525 ms 9,984 KB
testcase_27	AC	504 ms 9,088 KB
testcase_28	AC	509 ms 9,728 KB
testcase_29	AC	514 ms 9,600 KB
testcase_30	AC	488 ms 8,704 KB
testcase_31	AC	515 ms 9,856 KB
testcase_32	AC	485 ms 9,216 KB
testcase_33	AC	349 ms 7,040 KB
testcase_34	AC	437 ms 8,320 KB
testcase_35	AC	232 ms 5,248 KB
testcase_36	AC	253 ms 5,504 KB
testcase_37	AC	376 ms 7,424 KB
testcase_38	AC	360 ms 7,296 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#![allow(unused_imports)]
#![allow(unused_macros)]
#![allow(non_snake_case)]
pub use __cargo_equip::prelude::*;

use proconio::marker::{Bytes, Chars, Isize1, Usize1};
use proconio::{input, input_interactive};
#[allow(unused_imports)]
use proconio_derive::fastout;
use static_modint::ModInt998244353;
use std::cmp::Reverse;

/*#[fastout]
fn main() {
    input! {
        N: usize,
        mut A: [u128; N],
    }
    A.sort_by(|a, b| {
        let a_len = a.to_string().len();
        let b_len = b.to_string().len();
        if a_len == b_len {
            a.cmp(b)
        } else {
            let a_f = (10_u128).pow(b_len as u32) * a + b;
            let b_f = (10_u128).pow(a_len as u32) * b + a;
            a_f.cmp(&b_f)
        }
    });
    let ans = A.iter().fold(ModInt998244353::new(0), |acc, &a| {
        let digits = a.to_string().len();
        acc * ModInt998244353::raw(10).pow(digits as u64) + ModInt998244353::new(a)
    });
    println!("{}", ans);
}*/
fn main() {
    let __proconio_stdout = ::std::io::stdout();
    let mut __proconio_stdout = ::std::io::BufWriter::new(__proconio_stdout.lock());
    #[allow(unused_macros)]
    macro_rules ! print { ($ ($ tt : tt) *) => { { use std :: io :: Write as _ ; :: std :: write ! (__proconio_stdout , $ ($ tt) *) . unwrap () ; } } ; }
    #[allow(unused_macros)]
    macro_rules ! println { ($ ($ tt : tt) *) => { { use std :: io :: Write as _ ; :: std :: writeln ! (__proconio_stdout , $ ($ tt) *) . unwrap () ; } } ; }
    let __proconio_res = {
        input! { N : usize , mut A : [u128 ; N] , }
        A.sort_by(|a, b| {
            let a_len = a.to_string().len();
            let b_len = b.to_string().len();
            if a_len == b_len {
                a.cmp(b)
            } else {
                let a_f = (10_u128).pow(b_len as u32) * a + b;
                let b_f = (10_u128).pow(a_len as u32) * b + a;
                a_f.cmp(&b_f)
            }
        });
        let ans = A.iter().fold(ModInt998244353::new(0), |acc, &a| {
            let digits = a.to_string().len();
            acc * ModInt998244353::raw(10).pow(digits as u64) + ModInt998244353::new(a)
        });
        println!("{}", ans);
    };
    <::std::io::BufWriter<::std::io::StdoutLock> as ::std::io::Write>::flush(
        &mut __proconio_stdout,
    )
    .unwrap();
    return __proconio_res;
}

#[macro_export]
macro_rules! mat {
    ($($e:expr),*) => { vec![$($e),*] };
    ($($e:expr,)*) => { vec![$($e),*] };
    ($e:expr; $d:expr) => { vec![$e; $d] };
    ($e:expr; $d:expr $(; $ds:expr)+) => { vec![mat![$e $(; $ds)*]; $d] };
}

#[macro_export]
macro_rules! chmin {
    ($a:expr, $b:expr) => {
        if $a > $b {
            $a = $b;
            true
        } else {
            false
        }
    };
}

#[macro_export]
macro_rules! chmax {
    ($a:expr, $b:expr) => {
        if $a < $b {
            $a = $b;
            true
        } else {
            false
        }
    };
}

/// https://maguro.dev/debug-macro/
#[macro_export]
macro_rules! debug {
    ($($a:expr),* $(,)*) => {
        #[cfg(debug_assertions)]
        eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*);
    };
}

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

///  # Bundled libraries
/// 
///  - `internal_type_traits 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#1e1107f6f59acf7b7a31e3df7b8b28dff87722a2)` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__internal_type_traits_0_1_0`
///  - `modint_traits 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#1e1107f6f59acf7b7a31e3df7b8b28dff87722a2)`        licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__modint_traits_0_1_0`
///  - `static_modint 0.1.0 (git+ssh://git@github.com/CoCo-Japan-pan/procon_lib_rs.git#1e1107f6f59acf7b7a31e3df7b8b28dff87722a2)`        licensed under `CC0-1.0` as `crate::__cargo_equip::crates::static_modint`
/// 
///  # Procedural macros
/// 
///  - `proconio-derive 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)` licensed under `MIT OR Apache-2.0`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod __internal_type_traits_0_1_0 {use std::ops::{Add,AddAssign,Sub,SubAssign};pub trait Integral:Copy+Add<Output=Self>+AddAssign+Sub<Output=Self>+SubAssign+Ord+Zero+One+BoundedBelow+BoundedAbove{}pub trait Zero{fn zero()->Self;}pub trait One{fn one()->Self;}pub trait BoundedBelow{fn min_value()->Self;}pub trait BoundedAbove{fn max_value()->Self;}macro_rules!impl_integral{($($ty:ty),*)=>{$(impl Zero for$ty{#[inline]fn zero()->Self{0}}impl One for$ty{#[inline]fn one()->Self{1}}impl BoundedBelow for$ty{#[inline]fn min_value()->Self{Self::MIN}}impl BoundedAbove for$ty{#[inline]fn max_value()->Self{Self::MAX}}impl Integral for$ty{})*};}impl_integral!(i8,i16,i32,i64,i128,isize,u8,u16,u32,u64,u128,usize);}
        pub mod __modint_traits_0_1_0 {use std::fmt::{Debug,Display};use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign};use std::str::FromStr;pub trait ModInt:Debug+Default+Clone+PartialEq+Eq+Display+Copy+Add<Output=Self>+Sub<Output=Self>+Mul<Output=Self>+Div<Output=Self>+AddAssign+SubAssign+MulAssign+DivAssign+Neg<Output=Self>+FromStr{fn new<T:RemEuclidU32>(x:T)->Self;fn raw(x:u32)->Self;fn value(&self)->u32;fn modulus()->u32;fn pow(&self,mut n:u64)->Self{let mut ret=Self::new(1);let mut base=*self;while n>0{if n&1==1{ret*=base;}base*=base;n>>=1;}ret}#[inline]fn inv(&self)->Self{let(g,x)=inv_gcd(self.value(),Self::modulus());assert_eq!(g,1);Self::raw(x)}}fn inv_gcd(a:u32,b:u32)->(u32,u32){assert!(a<b);if a==0{return(b,0);}let mut s=b;let mut t=a;let mut m0=0_i32;let mut m1=1_i32;while t!=0{let u=s/t;s-=t*u;m0-=m1*(u as i32);std::mem::swap(&mut s,&mut t);std::mem::swap(&mut m0,&mut m1);}if m0<0{m0+=(b/s)as i32;}(s,m0 as u32)}pub trait RemEuclidU32:Copy{fn rem_euclid_u32(self,modulus:u32)->u32;}impl RemEuclidU32 for u8{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self as u32%modulus}}impl RemEuclidU32 for u16{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self as u32%modulus}}impl RemEuclidU32 for u32{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{self%modulus}}impl RemEuclidU32 for u64{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{(self%modulus as u64)as u32}}impl RemEuclidU32 for usize{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{let casted:u64=self.try_into().unwrap();casted.rem_euclid_u32(modulus)}}impl RemEuclidU32 for u128{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{(self%modulus as u128)as u32}}#[inline]fn neg(val:u32,modulus:u32)->u32{if val==0{0}else{modulus-val}}macro_rules!impl_rem_euclid_u32_for_signed{($($t:ty),*)=>{$(impl RemEuclidU32 for$t{#[inline]fn rem_euclid_u32(self,modulus:u32)->u32{if self<0{neg(self.unsigned_abs().rem_euclid_u32(modulus),modulus)}else{self.unsigned_abs().rem_euclid_u32(modulus)}}})*};}impl_rem_euclid_u32_for_signed!(i8,i16,i32,i64,isize,i128);}
        pub mod proconio_derive {pub use crate::__cargo_equip::macros::proconio_derive::*;#[macro_export]macro_rules!__cargo_equip_macro_def_proconio_derive_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_fastout{($(_:tt)*)=>(::std::compile_error!("`fastout` from `proconio-derive 0.2.1` should have been expanded");)}}
        pub mod static_modint {use crate::__cargo_equip::preludes::static_modint::*;use internal_type_traits::{One,Zero};use modint_traits::{ModInt,RemEuclidU32};use std::fmt::Display;use std::iter::{Product,Sum};use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign};use std::str::FromStr;pub type ModInt998244353=StaticModInt<998244353>;pub type ModInt1000000007=StaticModInt<1000000007>;#[derive(Debug,Clone,Copy,PartialEq,Eq,Hash,Default)]pub struct StaticModInt<const MOD:u32>{value:u32,}impl<const MOD:u32>Zero for StaticModInt<MOD>{fn zero()->Self{Self::raw(0)}}impl<const MOD:u32>One for StaticModInt<MOD>{fn one()->Self{Self::new(1)}}impl<const MOD:u32>Display for StaticModInt<MOD>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.value)}}impl<const MOD:u32,T>Sum<T>for StaticModInt<MOD>where Self:Add<T,Output=Self>,{fn sum<I:Iterator<Item=T>>(iter:I)->Self{iter.fold(Self::raw(0),Add::add)}}impl<const MOD:u32,T>Product<T>for StaticModInt<MOD>where Self:Mul<T,Output=Self>,{fn product<I:Iterator<Item=T>>(iter:I)->Self{iter.fold(Self::new(1),Mul::mul)}}impl<const MOD:u32>FromStr for StaticModInt<MOD>{type Err=<i64 as FromStr>::Err;fn from_str(s:&str)->Result<Self,Self::Err>{i64::from_str(s).map(Self::new)}}impl<const MOD:u32>StaticModInt<MOD>{#[inline]pub fn value(&self)->u32{self.value}#[inline]pub fn modulus()->u32{MOD}#[inline]pub fn new<T:RemEuclidU32>(x:T)->Self{ModInt::new(x)}#[inline]pub fn raw(x:u32)->Self{Self{value:x}}#[inline]pub fn pow(&self,n:u64)->Self{ModInt::pow(self,n)}#[inline]pub fn inv(&self)->Self{ModInt::inv(self)}}impl<const MOD:u32>ModInt for StaticModInt<MOD>{#[inline]fn value(&self)->u32{self.value}#[inline]fn modulus()->u32{MOD}#[inline]fn raw(x:u32)->Self{Self{value:x}}#[inline]fn new<T:RemEuclidU32>(x:T)->Self{Self{value:x.rem_euclid_u32(MOD),}}}impl<const MOD:u32>Neg for StaticModInt<MOD>{type Output=Self;#[inline]fn neg(self)->Self{if self.value==0{Self{value:0}}else{Self{value:MOD-self.value,}}}}impl<const MOD:u32,T>Add<T>for StaticModInt<MOD>where Self:AddAssign<T>,{type Output=Self;fn add(mut self,rhs:T)->Self{self+=rhs;self}}impl<const MOD:u32>AddAssign for StaticModInt<MOD>{fn add_assign(&mut self,rhs:Self){self.value+=rhs.value;if self.value>=MOD{self.value-=MOD;}}}impl<const MOD:u32,T:RemEuclidU32>AddAssign<T>for StaticModInt<MOD>{fn add_assign(&mut self,rhs:T){*self+=Self::new(rhs);}}impl<const MOD:u32,T>Sub<T>for StaticModInt<MOD>where Self:SubAssign<T>,{type Output=Self;fn sub(mut self,rhs:T)->Self{self-=rhs;self}}impl<const MOD:u32>SubAssign for StaticModInt<MOD>{fn sub_assign(&mut self,rhs:Self){if self.value<rhs.value{self.value+=MOD;}self.value-=rhs.value;}}impl<const MOD:u32,T:RemEuclidU32>SubAssign<T>for StaticModInt<MOD>{fn sub_assign(&mut self,rhs:T){*self-=Self::new(rhs);}}impl<const MOD:u32,T>Mul<T>for StaticModInt<MOD>where Self:MulAssign<T>,{type Output=Self;fn mul(mut self,rhs:T)->Self{self*=rhs;self}}impl<const MOD:u32>MulAssign for StaticModInt<MOD>{fn mul_assign(&mut self,rhs:Self){self.value=(self.value as u64*rhs.value as u64).rem_euclid_u32(MOD);}}impl<const MOD:u32,T:RemEuclidU32>MulAssign<T>for StaticModInt<MOD>{fn mul_assign(&mut self,rhs:T){*self*=Self::new(rhs);}}impl<const MOD:u32,T>Div<T>for StaticModInt<MOD>where Self:DivAssign<T>,{type Output=Self;fn div(mut self,rhs:T)->Self{self/=rhs;self}}#[allow(clippy::suspicious_op_assign_impl)]impl<const MOD:u32>DivAssign for StaticModInt<MOD>{fn div_assign(&mut self,rhs:Self){*self*=rhs.inv();}}impl<const MOD:u32,T:RemEuclidU32>DivAssign<T>for StaticModInt<MOD>{fn div_assign(&mut self,rhs:T){*self/=Self::new(rhs);}}macro_rules!impl_from_primitive{($($t:ty),*)=>{$(impl<const MOD:u32>From<$t>for StaticModInt<MOD>{fn from(x:$t)->Self{Self::new(x)}})*};}impl_from_primitive!(u8,u16,u32,u64,usize,u128,i8,i16,i32,i64,isize,i128);}
    }

    pub(crate) mod macros {
        pub mod __internal_type_traits_0_1_0 {}
        pub mod __modint_traits_0_1_0 {}
        pub mod proconio_derive {pub use crate::{__cargo_equip_macro_def_proconio_derive_derive_readable as derive_readable,__cargo_equip_macro_def_proconio_derive_fastout as fastout};}
        pub mod static_modint {}
    }

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

    mod preludes {
        pub mod __internal_type_traits_0_1_0 {}
        pub mod __modint_traits_0_1_0 {}
        pub mod proconio_derive {}
        pub mod static_modint {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{__internal_type_traits_0_1_0 as internal_type_traits,__modint_traits_0_1_0 as modint_traits};}
    }
}