結果

問題 No.3397 Max Weighted Floor of Linear
コンテスト
ユーザー 👑 Mizar
提出日時 2025-12-06 17:37:30
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 209 ms / 2,000 ms
コード長 4,607 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,856 ms
コンパイル使用メモリ 398,424 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-06 17:37:50
合計ジャッジ時間 19,587 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

fn main() -> std::io::Result<()> {
    use std::io::Write;
    let mut bw = std::io::BufWriter::new(std::io::stdout());
    input! { t: usize }
    for _ in 0..t {
        input! { n: i64, m: i64, a: i64, b: i64, c: i64, d: i64 }
        let ans = mwf_i64(n, m, a, b, c, d);
        writeln!(bw, "{}", ans)?;
    }
    bw.flush()?;
    Ok(())
}

pub trait ProdMonoid<T> {
    fn ident() -> Self;
    fn mul(&self, rhs: &Self) -> Self;
    fn pow(&self, exp: T) -> Self;
}

macro_rules! impl_floor_prod {
    ($t:ty, $i:ident) => {
        #[allow(unused_comparisons)]
        pub fn $i<T>(mut m: $t, mut a: $t, mut b: $t, mut n: $t, e: T, mut x: T, mut y: T) -> T
        where
            T: ProdMonoid<$t> + Clone,
        {
            assert!(0 < m && 0 <= a && 0 <= b && 0 <= n);
            let mut c = (a * n + b) / m;
            let (mut pre, mut suf) = (e.clone(), e.clone());
            loop {
                let p = a / m;
                a %= m;
                x = x.mul(&y.pow(p));
                let q = b / m;
                b %= m;
                pre = pre.mul(&y.pow(q));
                c -= p * n + q;
                if c == 0 {
                    return pre.mul(&x.pow(n)).mul(&suf);
                }
                let d = (m * c - b - 1) / a + 1;
                suf = y.mul(&x.pow(n - d)).mul(&suf);
                b = m - b - 1 + a;
                std::mem::swap(&mut m, &mut a);
                n = c - 1;
                c = d;
                std::mem::swap(&mut x, &mut y);
            }
        }
    };
}
impl_floor_prod!(u128, floor_prod_u128);
impl_floor_prod!(i128, floor_prod_i128);
impl_floor_prod!(u64, floor_prod_u64);
impl_floor_prod!(i64, floor_prod_i64);
impl_floor_prod!(usize, floor_prod_usize);
impl_floor_prod!(isize, floor_prod_isize);

macro_rules! impl_mwf {
    ($t:ty, $i:ident, $p:ident) => {
        pub fn $i(n: $t, m: $t, a: $t, b: $t, c: $t, d: $t) -> $t {
            #[derive(Clone)]
            struct Data($t, $t);
            impl ProdMonoid<$t> for Data {
                fn ident() -> Self {
                    Data(0, <$t>::MIN)
                }
                fn mul(&self, rhs: &Self) -> Self {
                    Data(self.0 + rhs.0, self.1.max(self.0.saturating_add(rhs.1)))
                }
                fn pow(&self, exp: $t) -> Self {
                    assert!(exp >= 0);
                    if exp == 0 {
                        Self::ident()
                    } else {
                        Data(
                            exp * self.0,
                            if self.0 > 0 {
                                (exp - 1).saturating_mul(self.0).saturating_add(self.1)
                            } else {
                                self.1
                            },
                        )
                    }
                }
            }
            $p(m, c, d, n, Data(0, <$t>::MIN), Data(a, 0), Data(b, <$t>::MIN)).1
        }
    };
}
impl_mwf!(i128, mwf_i128, floor_prod_i128);
impl_mwf!(i64, mwf_i64, floor_prod_i64);
impl_mwf!(isize, mwf_isize, floor_prod_isize);

use input_lite::*;
#[rustfmt::skip]#[allow(unused)]mod input_lite{#[macro_export]macro_rules!read_value{($b:expr,($($t:tt),*))=>{($(read_value!($b,$t)),*)};($b:expr,[$t:tt;$len:expr])=>{(0..$len).map(|_|read_value!($b,$t)).collect::<Vec<_>>()};($b:expr,byte)=>{token($b,|s|s[0])};($b:expr,Bytes)=>{token($b,|s|s.to_vec())};($b:expr,Chars)=>{token($b,|s|std::str::from_utf8(s).unwrap().chars().collect::<Vec<_>>())};($b:expr,usize1)=>{read_value!($b,usize)-1};($b:expr,$t:ty)=>{token($b,|s|std::str::from_utf8(s).unwrap().parse::<$t>().unwrap())};}#[macro_export]macro_rules!input_inner{($b:expr)=>{};($b:expr,)=>{};($b:expr,$var:ident:$t:tt$($r:tt)*)=>{let$var=read_value!($b,$t);input_inner!{$b$($r)*}};}#[macro_export]macro_rules!input{(source=$s:expr,$($r:tt)*)=>{input_inner!{$s,$($r)*}};($($r:tt)*)=>{let mut i=std::io::stdin().lock();input_inner!{&mut i,$($r)*}std::mem::drop(i);};}pub fn token<R:std::io::BufRead,T>(r:&mut R,f:impl Fn(&[u8])->T)->T{let(b,mut l)=loop{let b=r.fill_buf().unwrap();assert!(!b.is_empty());if let Some(p)=b.iter().position(|&b|!b.is_ascii_whitespace()){break(&b[p..],p);}let l=b.len();r.consume(l);};if let Some(p)=b.iter().position(|&b|b.is_ascii_whitespace()){let t=&b[..p];let x=f(t);r.consume(l+p+1);return x;}l+=b.len();let mut t=b.to_vec();r.consume(l);while let Ok(b)=r.fill_buf(){if b.is_empty(){break;}if let Some(p)=b.iter().position(|&b|b.is_ascii_whitespace()){t.extend_from_slice(&b[..p]);r.consume(p+1);break;}let l=b.len();t.extend_from_slice(b);r.consume(l);}f(&t)}}
0