結果

問題 No.3557 KCPC or KUPC 2
コンテスト
ユーザー urectanc
提出日時 2026-05-29 20:03:38
言語 Rust
(1.94.0 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 2,292 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,988 ms
コンパイル使用メモリ 186,724 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2026-05-29 20:03:55
合計ジャッジ時間 4,732 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge4_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点1 10 % AC * 30
部分点2 40 % AC * 30
部分点3 50 % AC * 30
合計 100 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::num::Saturating;

use proconio::input;

fn main() {
    input! {
        n: u128,
        a: u128, b: u128, c: u128,
        d: u128, e: u128, f: u128,
    }

    let p = calc(n, a, b, c);
    let q = calc(n, d, e, f);
    if p < q {
        println!("KCPC");
    } else if p > q {
        println!("KUPC");
    } else {
        println!("Same");
    }
}

fn calc(n: u128, x: u128, y: u128, z: u128) -> u128 {
    let mut ng = 0u128;
    let mut ok = n;

    while ok.abs_diff(ng) > 1 {
        let mid = ok.midpoint(ng);
        if calc2(x, y, z, mid) >= n {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    ok
}

fn calc2(x: u128, y: u128, z: u128, m: u128) -> u128 {
    let x = Saturating(x);
    let y = Saturating(y);
    let z = Saturating(z);
    let m = Saturating(m);

    let offset = x * m;
    let (q, r) = (m / y, m % y);
    let add = q * (q - Saturating(1)) / Saturating(2) * z * y;
    let add2 = r * q * z;

    let ans = (offset + add + add2).0;
    // dbg!(m, q, r, offset, add, add2, ans);
    // eprintln!();
    ans
}

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

    use super::*;

    fn testcase(rng: &mut impl rand::Rng) -> (u128, u128, u128, u128) {
        let n: u128 = rng.random_range(1..100000);
        let a: u128 = rng.random_range(1..1000);
        let b: u128 = rng.random_range(1..1000);
        let c: u128 = rng.random_range(1..1000);
        (n, a, b, c)
    }

    fn naive(n: u128, a: u128, b: u128, c: u128) -> u128 {
        let mut ans = 0;
        for i in 0.. {
            ans += a + i / b * c;
            if ans >= n {
                return i + 1;
            }
        }
        unreachable!()
    }

    #[test]
    fn stress() {
        const T: usize = 1000;

        let failed = vec![(7, 1, 1, 1), (6, 1, 2, 1)];
        for (n, a, b, c) in failed {
            let expected = naive(n, a, b, c);
            let actual = calc(n, a, b, c);
            assert_eq!(expected, actual, "{n} {a} {b} {c}");
        }

        let mut rng = rand::rng();
        for _ in 0..T {
            let (n, a, b, c) = testcase(&mut rng);
            let expected = naive(n, a, b, c);
            let actual = calc(n, a, b, c);
            assert_eq!(expected, actual, "{n} {a} {b} {c}");
        }
    }
}
0