#939894 (Rust) No.2595 Parsing Challenge

提出ソース

結果

問題	No.2595 Parsing Challenge
コンテスト
ユーザー	akakimidori
提出日時	2023-12-23 01:31:36
言語	Rust (1.83.0 + proconio)
結果	AC
実行時間	793 ms / 6,000 ms
コード長	13,013 bytes
コンパイル時間	13,913 ms
コンパイル使用メモリ	400,720 KB
実行使用メモリ	128,736 KB
最終ジャッジ日時	2024-09-27 11:57:11
合計ジャッジ時間	26,391 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
sample	AC * 5
other	AC * 55

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: unused import: `util::*`
  --> src/main.rs:15:9
   |
15 |     use util::*;
   |         ^^^^^^^
   |
   = note: `#[warn(unused_imports)]` on by default

warning: unused variable: `n`
   --> src/main.rs:3:9
    |
3   |         n: usize,
    |         ^
    |
help: `n` is captured in macro and introduced a unused variable
   --> src/main.rs:454:13
    |
2   | /     input! {
3   | |         n: usize,
4   | |         s: bytes,
5   | |     }
    | |_____- in this macro invocation
...
454 |           let $var = read_value!($iter, $t);
    |               ^^^^
    = note: `#[warn(unused_variables)]` on by default
    = note: this warning originates in the macro `input_inner` which comes from the expansion of the macro `input` (in Nightly builds, run with -Z macro-backtrace for more info)

warning: value assigned to `seed` is never read
  --> src/main.rs:30:13
   |
30 |     let mut seed = BigInt::new(0);
   |             ^^^^
   |
   = help: maybe it is overwritten before being read?
   = note: `#[warn(unused_assignments)]` on by default

warning: unused variable: `op`
   --> src/main.rs:106:17
    |
106 |             let op = self.eat();
    |                 ^^ help: if this is intentional, prefix it with an underscore: `_op`

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

ソースコード

raw source code

fn main() {
    input! {
        n: usize,
        s: bytes,
    }
    let tree = Parse { s: s, pos: 0 }.exp();
    let ans = calc(tree);
    if ans.sign == 0 {
        println!("0");
        return;
    }
    if ans.sign < 0 {
        print!("-");
    }
    use util::*;
    let mut res = String::new();
    for (i, a) in ans.data.iter().rev().enumerate() {
        use std::fmt::*;
        if i == 0 {
            write!(&mut res, "{}", *a).ok();
        } else {
            write!(&mut res, "{:<06}", *a).ok();
        }
    }
    println!("{}", res);
}

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'*') {
            let op = self.eat();
            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
        }
    }
}

yukicoder

結果

コンパイルメッセージ

ソースコード