#1176906 (Rust) No.3624 Product

• 問題: No.3624 Product
• ユーザー: urectanc
• 提出日時: 2026-08-14 22:16:48
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: AC
• 実行時間: 20 ms / 2,000 ms
• コード長: 1,652 bytes
• コンパイル時間: 1,032 ms
• コンパイル使用メモリ: 198,680 KB
• 実行使用メモリ: 9,388 KB
• 最終ジャッジ日時: 2026-08-14 22:16:52
• 合計ジャッジ時間: 2,753 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_1

ファイルパターン	結果
sample	AC * 1
other	AC * 12

ソースコード

// msbが同じならng
// 異なるときは？
// rが0ならlは1をとってよい
// (r+2^k)*l < r*(l+2^k)
// 要するに2^k * (2^k - 1)

use proconio::{fastout, input};

#[fastout]
fn main() {
    input! { t: usize }

    for _ in 0..t {
        input! {
            l: usize, r: usize,
        }
        let ans = solve(l, r);
        println!("{}", ans as isize);
    }
}

fn solve(l: usize, r: usize) -> usize {
    if (l, r) == (0, 0) {
        return 0;
    }
    for k in (0..=30).rev() {
        let b = 1 << k;
        let a = b - 1;
        if (l..=r).contains(&a) && (l..=r).contains(&b) {
            return a * b;
        }
    }
    !0
}

#[cfg(test)]
mod tests {
    use rand::RngExt;

    use super::*;

    fn testcase(rng: &mut impl rand::Rng) -> (usize, usize) {
        let l = rng.random_range(0..100);
        let r = rng.random_range(l..100);
        (l, r)
    }

    fn naive(l: usize, r: usize) -> usize {
        let (l, r) = (l as isize, r as isize);
        let mut max = -1;
        for a in l..=r {
            for b in a..=r {
                if a & b == 0 {
                    max = max.max(a * b);
                }
            }
        }
        max as usize
    }

    #[test]
    fn stress() {
        const T: usize = 100000;
        let mut rng = rand::rng();

        let killer = vec![];
        let testcases = killer
            .into_iter()
            .chain(std::iter::repeat_with(|| testcase(&mut rng)).take(T));

        for (l, r) in testcases {
            let expected = naive(l, r);
            let actual = solve(l, r);
            assert_eq!(expected, actual, "{l} {r}");
        }
    }
}