結果

問題 No.2927 Reverse Polish Equation
コンテスト
ユーザー magurofly
提出日時 2024-10-12 16:02:40
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 2,342 bytes
コンパイル時間 14,411 ms
コンパイル使用メモリ 394,752 KB
実行使用メモリ 16,544 KB
最終ジャッジ日時 2024-10-16 00:24:45
合計ジャッジ時間 16,738 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#![allow(dead_code, unused_imports, unused_macros, non_snake_case)]

fn main() {
    input! {
        Q: usize, Y: i64,
        S: [String; Q],
    }

    #[derive(Clone, Copy, Debug)]
    struct Term {
        mul: i64,
        add: i64,
        min: i64,
        max: i64,
    }
    fn clamp(x: i64) -> i64 {
        x.min(INF).max(-INF)
    }
    let mut stack = vec![];
    for token in S {
        if token == "X" {
            stack.push(Term { mul: 1, add: 0, min: -INF, max: INF })
        } else if token == "+" {
            let Term { mul: mul1, add: add1, min: min1, max: max1 } = stack.pop().unwrap();
            let Term { mul: mul2, add: add2, min: min2, max: max2 } = stack.pop().unwrap();
            stack.push(Term { mul: mul1 + mul2, add: clamp(add1 + add2), min: clamp(min1 + min2), max: clamp(max1 + max2) });
        } else if token == "min" {
            let Term { mul: mul1, add: add1, min: min1, max: max1 } = stack.pop().unwrap();
            let Term { mul: mul2, add: add2, min: min2, max: max2 } = stack.pop().unwrap();
            stack.push(Term { mul: mul1.min(mul2), add: add1.min(add2), min: min1.min(min2), max: max1.min(max2) });
        } else if token == "max" {
            let Term { mul: mul1, add: add1, min: min1, max: max1 } = stack.pop().unwrap();
            let Term { mul: mul2, add: add2, min: min2, max: max2 } = stack.pop().unwrap();
            stack.push(Term { mul: mul1.max(mul2), add: add1.max(add2), min: min1.max(min2), max: max1.max(max2) });
        } else {
            let c = token.parse::<i64>().unwrap();
            stack.push(Term { mul: 0, add: c, min: -INF, max: INF });
        }
    }

    let Term { mul, add, min, max } = stack.pop().unwrap();
    if (min ..= max).contains(&Y) {
        let x = if mul == 0 { 0 } else { (Y - add) / mul };
        if x * mul + add == Y {
            println!("{x}");
        } else {
            println!("-1");
        }
    } else {
        println!("-1");
    }
}

type Int = i64;
const MOD: Int = 998244353;
const INF: Int = 1_000_000_000_000_000_000;
const YESNO: [&'static str; 2] = ["Yes", "No"];

use proconio::{input, source::line::LineSource, marker::{Usize1, Chars}};

fn yes() { println!("{}", YESNO[0]); }
fn no() { println!("{}", YESNO[1]); }
fn yesno(c: bool) { println!("{}", if c { YESNO[0] } else { YESNO[1] }); }
0