結果

問題 No.2069 み世界数式
ユーザー akakimidoriakakimidori
提出日時 2022-09-06 22:28:52
言語 Rust
(1.77.0)
結果
RE  
実行時間 -
コード長 3,977 bytes
コンパイル時間 1,470 ms
コンパイル使用メモリ 157,612 KB
実行使用メモリ 4,512 KB
最終ジャッジ日時 2023-08-16 05:55:25
合計ジャッジ時間 8,275 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 AC 1 ms
4,380 KB
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 AC 1 ms
4,380 KB
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 AC 1 ms
4,380 KB
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

// WA?

fn main() {
    let (m, ans, mut expr) = read();
    let res = Solver::solve(m, &expr);
    if res.0[ans].0 {
        let mut x = 0;
        for s in expr.iter_mut() {
            if *s == b'$' || *s == b'&' {
                *s = res.0[ans].1[x];
                x += 1;
            }
        }
        let ans = expr.iter().map(|c| *c as char).collect::<String>();
        println!("{}", ans);
    } else {
        println!("-1");
    }
}

fn read() -> (usize, usize, Vec<u8>) {
    let mut s = String::new();
    use std::io::*;
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let m = it.next().unwrap().parse().unwrap();
    let ans = it.next().unwrap().parse().unwrap();
    let expr = it.next().unwrap().bytes().collect();
    (m, ans, expr)
}

struct Solver<'a> {
    m: usize,
    s: &'a [u8],
    pos: usize,
}

impl<'a> Solver<'a> {
    fn solve(m: usize, s: &'a [u8]) -> DP {
        let mut state = Solver { m: m, s: s, pos: 0 };
        let res = state.expression();
        assert!(state.pos == state.s.len());
        res
    }
    fn next(&self) -> Option<u8> {
        self.s.get(self.pos).cloned()
    }
    fn eat(&mut self) -> Option<u8> {
        self.s.get(self.pos).cloned().map(|c| {
            self.pos += 1;
            c
        })
    }
    fn expression(&mut self) -> DP {
        let mut res = self.term();
        while self.next().map_or(false, |c| c == b'$') {
            self.eat();
            let rhs = self.term();
            res = res.add_sub(&rhs);
        }
        res
    }
    fn term(&mut self) -> DP {
        let mut res = self.factor();
        while self.next().map_or(false, |c| c == b'&') {
            self.eat();
            let rhs = self.factor();
            res = res.mul_div(&rhs);
        }
        res
    }
    fn factor(&mut self) -> DP {
        let c = self.next().unwrap();
        if c == b'(' {
            self.eat();
            let res = self.expression();
            assert_eq!(self.eat(), Some(b')'));
            res
        } else {
            assert!(b'0' <= c && c <= b'9');
            let mut v = 0;
            while self.next().map_or(false, |c| b'0' <= c && c <= b'9') {
                v = 10 * v + (self.eat().unwrap() - b'0') as usize;
                assert!(v <= self.m);
            }
            DP::new(self.m, v)
        }
    }
}

struct DP(Vec<(bool, Vec<u8>)>);

impl DP {
    fn zero(m: usize) -> Self {
        DP(vec![(false, vec![]); m + 2])
    }
    fn new(m: usize, x: usize) -> Self {
        assert!(1 <= m && m <= 300);
        assert!(x <= m);
        let mut dp = vec![(false, vec![]); m + 2];
        dp[x].0 = true;
        DP(dp)
    }
    fn add_sub(&self, rhs: &Self) -> Self {
        assert!(self.0.len() == rhs.0.len());
        let mut res = DP::zero(self.0.len() - 1);
        for (l, a) in self.0.iter().enumerate().filter(|p| p.1 .0) {
            for (r, b) in rhs.0.iter().enumerate().filter(|p| p.1 .0) {
                res.fill(l + r, a, b'+', b);
                res.fill(l - r, a, b'-', b);
            }
        }
        res
    }
    fn mul_div(&self, rhs: &Self) -> Self {
        assert!(self.0.len() == rhs.0.len());
        let mut res = DP::zero(self.0.len() - 1);
        for (l, a) in self.0.iter().enumerate().filter(|p| p.1 .0) {
            for (r, b) in rhs.0.iter().enumerate().filter(|p| p.1 .0) {
                res.fill(l * r, a, b'*', b);
                if r > 0 {
                    res.fill(l / r, a, b'/', b);
                }
            }
        }
        res
    }
    fn fill(&mut self, x: usize, a: &(bool, Vec<u8>), c: u8, b: &(bool, Vec<u8>)) {
        if x < self.0.len() && !self.0[x].0 {
            self.0[x].0 = true;
            self.0[x].1 =
                a.1.iter()
                    .cloned()
                    .chain(std::iter::once(c))
                    .chain(b.1.iter().cloned())
                    .collect();
        }
    }
}
0