結果

問題 No.2595 Parsing Challenge
ユーザー akakimidoriakakimidori
提出日時 2023-12-23 01:02:10
言語 Rust
(1.77.0)
結果
WA  
実行時間 -
コード長 12,850 bytes
コンパイル時間 1,412 ms
コンパイル使用メモリ 194,808 KB
実行使用メモリ 136,672 KB
最終ジャッジ日時 2023-12-23 01:02:26
合計ジャッジ時間 14,264 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,676 KB
testcase_01 AC 1 ms
6,676 KB
testcase_02 AC 1 ms
6,676 KB
testcase_03 AC 1 ms
6,676 KB
testcase_04 AC 1 ms
6,676 KB
testcase_05 AC 0 ms
6,676 KB
testcase_06 AC 1 ms
6,676 KB
testcase_07 AC 1 ms
6,676 KB
testcase_08 AC 1 ms
6,676 KB
testcase_09 AC 0 ms
6,676 KB
testcase_10 AC 1 ms
6,676 KB
testcase_11 AC 1 ms
6,676 KB
testcase_12 AC 1 ms
6,676 KB
testcase_13 AC 1 ms
6,676 KB
testcase_14 AC 1 ms
6,676 KB
testcase_15 WA -
testcase_16 AC 1 ms
6,676 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 WA -
testcase_40 WA -
testcase_41 WA -
testcase_42 WA -
testcase_43 AC 119 ms
136,672 KB
testcase_44 WA -
testcase_45 WA -
testcase_46 WA -
testcase_47 WA -
testcase_48 WA -
testcase_49 WA -
testcase_50 WA -
testcase_51 WA -
testcase_52 WA -
testcase_53 WA -
testcase_54 WA -
testcase_55 WA -
testcase_56 WA -
testcase_57 WA -
testcase_58 WA -
testcase_59 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: value assigned to `seed` is never read
  --> Main.rs:23:13
   |
23 |     let mut seed = BigInt::new(0);
   |             ^^^^
   |
   = help: maybe it is overwritten before being read?
   = note: `#[warn(unused_assignments)]` on by default

warning: method `sub` is never used
   --> Main.rs:289:12
    |
182 | impl BigInt {
    | ----------- method in this implementation
...
289 |     pub fn sub(&self, rhs: &Self) -> Self {
    |            ^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: 2 warnings emitted

ソースコード

diff # 

fn main() {
    input! {
        n: usize,
        s: bytes,
    }
    let mut parser = Parse { s: s, pos: 0 };
    let tree = parser.exp();
    assert!(parser.pos == n);
    let ans = calc(tree);
    if ans.sign == 0 {
        println!("0");
        return;
    }
    if ans.sign < 0 {
        print!("-");
    }
    use util::*;
    println!("{}", ans.data.iter().rev().join(""));
}

fn calc(mut node: Ref) -> BigInt {
    let mut op = vec![];
    let mut seed = BigInt::new(0);
    loop {
        match *node {
            Node::Add(l, r, _) => {
                if l.size() >= r.size() {
                    node = l;
                    op.push((BigInt::new(1), calc(r)));
                } else {
                    node = r;
                    op.push((BigInt::new(1), calc(l)));
                }
            },
            Node::Sub(l, r, _) => {
                if l.size() >= r.size() {
                    node = l;
                    op.push((BigInt::new(1), calc(r).neg()));
                } else {
                    node = r;
                    op.push((BigInt::new(1).neg(), calc(l)));
                }
            },
            Node::Mul(l, r, _) => {
                if l.size() >= r.size() {
                    node = l;
                    op.push((calc(r), BigInt::new(0)));
                } else {
                    node = r;
                    op.push((calc(l), BigInt::new(0)));
                }
            },
            Node::Val(v) => {
                seed = v;
                break;
            }
        }
    }
    let (a, b) = dfs(op);
    a.mul(&seed).add(&b)
}

fn dfs(mut a: Vec<(BigInt,BigInt)>) -> (BigInt, BigInt) {
    if a.is_empty() {
        return (BigInt::new(1), BigInt::new(0));
    }
    if a.len() == 1 {
        return a[0].clone();
    }
    let m = a.len() / 2;
    let b = a.split_off(m);
    let (x, y) = dfs(a);
    let (z, w) = dfs(b);
    (x.mul(&z), x.mul(&w).add(&y))
}

struct Parse {
    s: Vec<u8>,
    pos: usize,
}

impl Parse {
    fn exp(&mut self) -> Ref {
        let mut l = self.term();
        while self.peek().map_or(false, |c| c == b'+' || c == b'-') {
            let op = self.eat();
            let r = self.term();
            if op == b'+' {
                l = Box::new(Node::add(l, r));
            } else {
                l = Box::new(Node::sub(l, r));
            }
        }
        l
    }
    fn term(&mut self) -> Ref {
        let mut l = self.factor();
        while self.peek().map_or(false, |c| c == b'*') {
            assert_eq!(self.eat(), b'*');
            let r = self.term();
            l = Box::new(Node::mul(l, r));
        }
        l
    }
    fn factor(&mut self) -> Ref {
        if self.peek().unwrap() == b'(' {
            self.eat();
            let v = self.exp();
            assert_eq!(self.eat(), b')');
            v
        } else {
            self.number()
        }
    }
    fn number(&mut self) -> Ref {
        let mut cnt = 0;
        while self.peek() == Some(b'-') {
            cnt += 1;
            self.eat();
        }
        let mut s = vec![];
        while self.peek().map_or(false, |c| b'0' <= c && c <= b'9') {
            s.push(self.eat());
        }
        let mut val = BigInt::from_str(&s);
        if cnt % 2 == 1 {
            val.sign *= -1;
        }
        Box::new(Node::Val(val))
    }
    fn peek(&self) -> Option<u8> {
        self.s.get(self.pos).cloned()
    }
    fn eat(&mut self) -> u8 {
        let v = self.s[self.pos];
        self.pos += 1;
        v
    }
}

type Ref = Box<Node>;

#[derive(Debug)]
enum Node {
    Add(Ref, Ref, usize),
    Sub(Ref, Ref, usize),
    Mul(Ref, Ref, usize),
    Val(BigInt),
}

impl Node {
    fn size(&self) -> usize {
        match *self {
            Node::Add(_, _, s) => s,
            Node::Sub(_, _, s) => s,
            Node::Mul(_, _, s) => s,
            Node::Val(_) => 1,
        }
    }
    fn add(l: Ref, r: Ref) -> Self {
        let size = l.size() + r.size();
        Node::Add(l, r, size)
    }
    fn sub(l: Ref, r: Ref) -> Self {
        let size = l.size() + r.size();
        Node::Sub(l, r, size)
    }
    fn mul(l: Ref, r: Ref) -> Self {
        let size = l.size() + r.size();
        Node::Mul(l, r, size)
    }
}

const BASE: u64 = 1_000_000;

#[derive(Clone, Debug)]
struct BigInt {
    sign: i64,
    data: Vec<u64>,
}

impl BigInt {
    pub fn new(a: i64) -> Self {
        let sign = a.signum();
        let mut a = (a * sign) as u64;
        let mut val = vec![];
        while a > 0 {
            val.push(a % BASE);
            a /= BASE;
        }
        let mut res = Self { sign, data: val };
        res.fix();
        res
    }
    pub fn from_str(s: &[u8]) -> Self {
        let data = s
            .rchunks(6)
            .map(|s| s.iter().fold(0u64, |s, a| 10 * s + (*a - b'0') as u64))
            .collect::<Vec<_>>();
        let mut res = Self {
            sign: 1,
            data: data,
        };
        res.fix();
        res
    }
    pub fn fix(&mut self) {
        while self.data.last().map_or(false, |p| *p == 0) {
            self.data.pop();
        }
        if self.data.is_empty() {
            self.sign = 0;
        }
    }
    pub fn valid(&self) -> bool {
        if self.data.len() > 0 {
            self.data.last().map_or(false, |p| *p > 0)
        } else {
            self.sign == 0
        }
    }
    pub fn neg(&self) -> Self {
        let mut v = self.clone();
        v.sign *= -1;
        v
    }
    pub fn add(&self, rhs: &Self) -> Self {
        if self.sign == 0 {
            return rhs.clone();
        }
        if rhs.sign == 0 {
            return self.clone();
        }
        assert!(self.valid() && rhs.valid());
        if self.sign == rhs.sign {
            let mut res = vec![0; self.data.len().max(rhs.data.len()) + 1];
            let mut carry = 0;
            for (i, res) in res.iter_mut().enumerate() {
                let a = self.data.get(i).map_or(0, |p| *p);
                let b = rhs.data.get(i).map_or(0, |p| *p);
                let sum = a + b + carry;
                *res = sum % BASE;
                carry = sum / BASE;
            }
            let mut ans = Self {
                sign: self.sign,
                data: res,
            };
            ans.fix();
            ans
        } else {
            let large = if self.data.len() != rhs.data.len() {
                self.data.len() > rhs.data.len()
            } else {
                self.data
                    .iter()
                    .zip(rhs.data.iter())
                    .rev()
                    .find(|p| *p.0 != *p.1)
                    .map_or(true, |p| *p.0 > *p.1)
            };
            let mut l = self;
            let mut r = rhs;
            if !large {
                std::mem::swap(&mut l, &mut r);
            }
            let mut carry = 0;
            let mut res = vec![0; l.data.len().max(r.data.len()) + 1];
            for (i, res) in res.iter_mut().enumerate() {
                let a = l.data.get(i).map_or(0, |p| *p);
                let b = r.data.get(i).map_or(0, |p| *p);
                if a >= b + carry {
                    *res = a - b - carry;
                    carry = 0;
                } else {
                    *res = a - b - carry + BASE;
                    carry = 1;
                }
            }
            assert!(carry == 0);
            let mut ans = Self {
                sign: l.sign,
                data: res,
            };
            ans.fix();
            ans
        }
    }
    pub fn sub(&self, rhs: &Self) -> Self {
        let mut rhs = rhs.clone();
        rhs.sign *= -1;
        self.add(&rhs)
    }
    pub fn mul(&self, rhs: &Self) -> Self {
        if self.sign == 0 || rhs.sign == 0 {
            return Self::new(0);
        }
        let mut data = karatsuba(&self.data, &rhs.data);
        let mut carry = 0;
        for i in 0.. {
            if carry == 0 && i >= data.len() {
                break;
            }
            if i >= data.len() {
                data.push(0);
            }
            let v = data[i] + carry;
            data[i] = v % BASE;
            carry = v / BASE;
        }
        Self {
            sign: self.sign * rhs.sign,
            data: data,
        }
    }
}

impl Zero for u64 {
    fn zero() -> Self {
        0
    }
    fn is_zero(&self) -> bool {
        *self == 0
    }
}

impl One for u64 {
    fn one() -> Self {
        1
    }
    fn is_one(&self) -> bool {
        *self == 1
    }
}

impl Ring for u64 {}

use std::ops::*;

pub trait Zero: Add<Output = Self> + Sized {
    fn zero() -> Self;
    fn is_zero(&self) -> bool;
}

pub trait One: Mul<Output = Self> + Sized {
    fn one() -> Self;
    fn is_one(&self) -> bool;
}

pub trait Ring: Zero + One + Sub<Output = Self> {}

pub trait Field: Ring + Div<Output = Self> {}

pub fn karatsuba<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Ring + Copy,
{
    fn rec<T>(a: &[T], b: &[T], c: &mut [T], buf: &mut [T])
    where
        T: Ring + Copy,
    {
        if a.len() <= 16 {
            for (i, a) in a.iter().enumerate() {
                for (c, b) in c[i..].iter_mut().zip(b.iter()) {
                    *c = *c + *a * *b;
                }
            }
            return;
        }
        let m = (a.len() + 1) / 2;
        let (la, ua) = a.split_at(m);
        let (lb, ub) = b.split_at(m);
        rec(la, lb, &mut c[..(2 * m)], buf);
        rec(ua, ub, &mut c[(2 * m)..], buf);
        let (x, buf) = buf.split_at_mut(m);
        let (y, buf) = buf.split_at_mut(m);
        let (z, buf) = buf.split_at_mut(2 * m);
        x.copy_from_slice(la);
        y.copy_from_slice(lb);
        let xa = x.iter_mut().zip(ua.iter());
        let yb = y.iter_mut().zip(ub.iter());
        for ((x, a), (y, b)) in xa.zip(yb) {
            *x = *x + *a;
            *y = *y + *b;
        }
        z.fill(T::zero());
        rec(x, y, z, buf);
        for &s in [0, 2 * m].iter() {
            for (z, c) in z.iter_mut().zip(c[s..].iter()) {
                *z = *z - *c;
            }
        }
        for (c, z) in c[m..].iter_mut().zip(z.iter()) {
            *c = *c + *z;
        }
    }
    let need = a.len().min(b.len());
    let mut buf = vec![T::zero(); 6 * need.next_power_of_two()];
    let mut s = 0;
    let mut ans = vec![T::zero(); a.len() + b.len()];
    let mut a = a;
    let mut b = b;
    while a.len() > 0 && b.len() > 0 {
        let len = a.len().min(b.len());
        let (c, buf) = buf.split_at_mut(2 * len);
        c.fill(T::zero());
        rec(&a[..len], &b[..len], c, buf);
        for (ans, c) in ans[s..].iter_mut().zip(c.iter()) {
            *ans = *ans + *c;
        }
        if a.len() == len {
            b = &b[len..];
        } else {
            a = &a[len..];
        }
        s += len;
    }
    ans.pop();
    ans
}

// ---------- begin input macro ----------
// reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[macro_export]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[macro_export]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[macro_export]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, bytes) => {
        read_value!($iter, String).bytes().collect::<Vec<u8>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}
// ---------- end input macro ----------
mod util {
    pub trait Join {
        fn join(self, sep: &str) -> String;
    }

    impl<T, I> Join for I
    where
        I: Iterator<Item = T>,
        T: std::fmt::Display,
    {
        fn join(self, sep: &str) -> String {
            let mut s = String::new();
            use std::fmt::*;
            for (i, v) in self.enumerate() {
                if i > 0 {
                    write!(&mut s, "{}", sep).ok();
                }
                write!(&mut s, "{}", v).ok();
            }
            s
        }
    }
}
0