結果

問題 No.2069 み世界数式
ユーザー akakimidoriakakimidori
提出日時 2022-09-01 21:11:26
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 24 ms / 2,000 ms
コード長 3,969 bytes
コンパイル時間 11,744 ms
コンパイル使用メモリ 402,024 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-24 16:08:46
合計ジャッジ時間 13,580 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

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 + 1])
    }
    fn new(m: usize, x: usize) -> Self {
        assert!(1 <= m && m <= 300);
        assert!(x <= m);
        let mut dp = vec![(false, vec![]); m + 1];
        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