#262975 (Rust) No.619 CardShuffle

• 問題: No.619 CardShuffle
• ユーザー: くれちー
• 提出日時: 2018-06-06 01:56:28
• 言語: Rust (1.83.0 + proconio)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 14,809 bytes
• コンパイル時間: 12,548 ms
• コンパイル使用メモリ: 387,724 KB
• 最終ジャッジ日時: 2024-11-14 20:26:18
• 合計ジャッジ時間: 13,623 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

コンパイルメッセージ

error[E0433]: failed to resolve: use of undeclared crate or module `math`
   --> src/main.rs:229:11
    |
229 |       use math::algebra::Semigroup;
    |           ^^^^ use of undeclared crate or module `math`

error[E0433]: failed to resolve: use of undeclared crate or module `math`
   --> src/main.rs:382:9
    |
382 |     use math::algebra::Monoid;
    |         ^^^^ use of undeclared crate or module `math`

error[E0432]: unresolved import `math`
   --> src/main.rs:238:9
    |
238 |     use math::Modulus;
    |         ^^^^ help: a similar path exists: `crate::math`
    |
    = note: `use` statements changed in Rust 2018; read more at <https://doc.rust-lang.org/edition-guide/rust-2018/module-system/path-clarity.html>

error[E0433]: failed to resolve: could not find `math` in the list of imported crates
  --> src/main.rs:88:19
   |
88 |   type ModU32 = ::math::ModU32<Mod1000000007>;
   |                   ^^^^ could not find `math` in the list of imported crates
   |
help: consider importing this module
   |
203+ use crate::math;
   |
help: if you import `math`, refer to it directly
   |
88 -   type ModU32 = ::math::ModU32<Mod1000000007>;
88 +   type ModU32 = math::ModU32<Mod1000000007>;
   |

warning: the item `FromIterator` is imported redundantly
  --> src/main.rs:86:25
   |
86 |   use std::iter::{once, FromIterator};
   |                         ^^^^^^^^^^^^
  --> /tmp/rust-20240322-9800-yefgu1/rustc-1.77.0-src/library/std/src/prelude/mod.rs:129:13
   |
   = note: the item `FromIterator` is already defined here
   |
   = note: `#[warn(unused_imports)]` on by default

error[E0783]: `...` range patterns are deprecated
   --> src/main.rs:115:9
    |
115 |         b'0'...b'9' => Card::Number(ModU32::from((c - b'0') as u32)),
    |         ^^^^---^^^^
    |             |
    |             help: use `..=` for an inclusive range

error[E0220]: associated type `T` not found for `M`
   --> src/main.rs:387:19
    |
387 |       vec: Vec<M::T>,
    |                   ^ th

ソースコード

macro_rules! semigroup_impl {
  ($marker:ty, $t:ty, | $lhs:ident, $rhs:ident | $append:expr) => {
    impl $crate::math::algebra::Semigroup for $marker {
      type T = $t;

      fn append($lhs: &$t, $rhs: &$t) -> $t {
        $append
      }
    }
  };
}

macro_rules! monoid_impl {
  ($marker:ty, $t:ty, | $lhs:ident, $rhs:ident | $append:expr, $identity:expr) => {
    semigroup_impl! { $marker, $t, |$lhs, $rhs| $append }

    impl $crate::math::algebra::Monoid for $marker {
      fn identity() -> $t {
        $identity
      }
    }
  };
}

fn solve<R: BufRead, W: Write>(_reader: R, _writer: &mut W) {
  let mut _scanner = Scanner::new(_reader);

  #[allow(unused_macros)]
  macro_rules! scan {
    ($t:ty) => {
      _scanner.next::<$t>().unwrap()
    };
    ($($t:ty),+) => {
      ($(scan!($t)),+)
    };
    ($t:ty; $n:expr) => {
      scan_iter!($t; $n).collect::<Vec<_>>()
    };
    ($t_0:ty, $t_1:ty; $n:expr) => {
      scan!($t_0 = 0, $t_1 = 1; $n)
    };
    ($t_0:ty, $t_1:ty, $t_2:ty; $n:expr) => {
      scan!($t_0 = 0, $t_1 = 1, $t_2 = 2; $n)
    };
    ($($t:ty = $i:tt),+; $n:expr) => {{
      let mut vecs = ($(Vec::<$t>::with_capacity($n)),+);
      for _ in 0..$n {$(
        vecs.$i.push(scan!($t));
      )+}
      vecs
    }};
  }

  #[allow(unused_macros)]
  macro_rules! scan_iter {
    ($t:ty; $n:expr) => {
      _scanner.take::<$t>($n).map(|x| x.unwrap())
    };
  }

  #[allow(unused_macros)]
  macro_rules! print {
    ($fmt:expr) => {
      write!(_writer, $fmt).unwrap()
    };
    ($fmt:expr, $($arg:tt)*) => {
      write!(_writer, $fmt, $($arg)*).unwrap()
    };
  }

  #[allow(unused_macros)]
  macro_rules! println {
    () => {
      writeln!(_writer).unwrap()
    };
    ($fmt:expr) => {
      writeln!(_writer, $fmt).unwrap()
    };
    ($fmt:expr, $($arg:tt)*) => {
      writeln!(_writer, $fmt, $($arg)*).unwrap()
    };
  }

  use data_structures::SegmentTree;
  use math::Mod1000000007;
  use std::iter::{once, FromIterator};

  type ModU32 = ::math::ModU32<Mod1000000007>;

  #[derive(Clone, PartialEq, Eq, Copy, Debug)]
  enum Operator {
    Add,
    Mul,
  }

  impl Operator {
    pub fn from_u8(c: u8) -> Self {
      match c {
        b'+' => Operator::Add,
        b'*' => Operator::Mul,
        _ => panic!(),
      }
    }
  }

  #[derive(Clone, PartialEq, Eq, Copy, Debug)]
  enum Card {
    Number(ModU32),
    Operator(Operator),
  }

  impl Card {
    pub fn from_u8(c: u8) -> Self {
      match c {
        b'0'...b'9' => Card::Number(ModU32::from((c - b'0') as u32)),
        b'+' | b'*' => Card::Operator(Operator::from_u8(c)),
        _ => panic!(),
      }
    }

    pub fn into_mod_u32(self) -> ModU32 {
      match self {
        Card::Number(num) => num,
        _ => panic!(),
      }
    }
  }

  let n = scan!(usize);
  let mut cards = once(b'*').chain(scan_iter!(u8; n)).map(Card::from_u8).collect::<Vec<_>>();

  #[derive(Clone, PartialEq, Eq, Copy, Debug)]
  enum Expr {
    Single(ModU32),
    Triple(ModU32, ModU32, ModU32),
  }

  impl Expr {
    pub fn from_cards(ope_card: Card, num_card: Card) -> Self {
      match (ope_card, num_card) {
        (Card::Operator(ope), Card::Number(num)) => match ope {
          Operator::Add => Expr::Triple(ModU32::from(1), ModU32::from(0), num),
          Operator::Mul => Expr::Single(num),
        },
        _ => panic!(),
      }
    }

    pub fn into_mod_u32(self, card: Card) -> ModU32 {
      match self {
        Expr::Single(a) => card.into_mod_u32() * a,
        Expr::Triple(a, b, c) => card.into_mod_u32() * a + b + c,
      }
    }

    pub fn append(&self, rhs: &Self) -> Self {
      match (*self, *rhs) {
        (Expr::Single(a), Expr::Single(d)) => Expr::Single(a * d),
        (Expr::Single(a), Expr::Triple(d, e, f)) => Expr::Triple(a * d, e, f),
        (Expr::Triple(a, b, c), Expr::Single(d)) => Expr::Triple(a, b, c * d),
        (Expr::Triple(a, b, c), Expr::Triple(d, e, f)) => Expr::Triple(a, b + c * d + e, f),
      }
    }
  }

  struct ExprMonoid;
  monoid_impl! { ExprMonoid, Expr, |l, r| l.append(r), Expr::Single(ModU32::from(1)) }

  let mut segtree = SegmentTree::<ExprMonoid>::from_iter(cards.chunks(2).map(|s| Expr::from_cards(s[0], s[1])));

  let q = scan!(usize);
  for _ in 0..q {
    let (t, x, y) = scan!(u8, usize, usize);
    match t {
      b'!' => {
        if cards[x] == cards[y] {
          continue;
        }
        cards.swap(x, y);
        segtree.set(x / 2, &Expr::from_cards(cards[x - x % 2], cards[x - x % 2 + 1]));
        segtree.set(y / 2, &Expr::from_cards(cards[y - x % 2], cards[y - x % 2 + 1]));
      }
      b'?' => {
        let ans = segtree.concat(x / 2 + 1..y / 2 + 1).into_mod_u32(cards[x]);
        println!("{}", ans);
      }
      _ => unreachable!(),
    }
  }
}

fn main() {
  let stdin = stdin();
  let stdout = stdout();
  #[cfg(debug_assertions)]
  let mut writer = stdout.lock();
  #[cfg(not(debug_assertions))]
  let mut writer = ::std::io::BufWriter::new(stdout.lock());
  solve(stdin.lock(), &mut writer);
  writer.flush().unwrap();
}

use io::Scanner;
use std::io::{stdin, stdout, BufRead, Write};

pub mod math {
  pub use self::mod_u32::*;
  pub use self::modulus::*;

  pub mod algebra {
    pub use self::monoid::*;
    pub use self::semigroup::*;

    mod semigroup {
      use std::fmt::Debug;

      pub trait Semigroup {
        type T: Clone + PartialEq + Debug;

        fn append(lhs: &Self::T, rhs: &Self::T) -> Self::T;

        fn append_assign(lhs: &mut Self::T, rhs: &Self::T) {
          *lhs = Self::append(lhs, rhs);
        }
      }
    }

    mod monoid {
      use math::algebra::Semigroup;

      pub trait Monoid: Semigroup {
        fn identity() -> Self::T;
      }
    }
  }

  mod mod_u32 {
    use math::Modulus;
    use std::fmt::{Debug, Display, Error, Formatter};
    use std::marker::PhantomData;
    use std::ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign};

    pub struct ModU32<M>(pub u32, PhantomData<fn() -> M>);

    impl<M> Default for ModU32<M> {
      fn default() -> Self {
        ModU32(u32::default(), PhantomData)
      }
    }

    impl<M> PartialEq for ModU32<M> {
      fn eq(&self, rhs: &Self) -> bool {
        self.0.eq(&rhs.0)
      }
    }

    impl<M> Eq for ModU32<M> {}

    impl<M> Clone for ModU32<M> {
      fn clone(&self) -> Self {
        ModU32(self.0, PhantomData)
      }
    }

    impl<M> Copy for ModU32<M> {}

    impl<M> Debug for ModU32<M> {
      fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
        Debug::fmt(&self.0, f)
      }
    }

    impl<M> Display for ModU32<M> {
      fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
        Display::fmt(&self.0, f)
      }
    }

    macro_rules! from_impl_u {
      ($($t:ty)+) => {$(
        impl<M: Modulus<Output = u32>> From<$t> for ModU32<M> {
          fn from(x: $t) -> Self {
            ModU32((x % M::modulus() as $t) as u32, PhantomData)
          }
        }
      )+};
    }

    from_impl_u! { u32 u64 }

    macro_rules! from_impl_i {
      ($($t:ty)+) => {$(
        impl<M: Modulus<Output = u32>> From<$t> for ModU32<M> {
          fn from(x: $t) -> Self {
            let temp = x % M::modulus() as $t;
            ModU32(if temp < 0 { temp + M::modulus() as $t } else { temp } as u32, PhantomData)
          }
        }
      )+};
    }

    from_impl_i! { i32 i64 }

    impl<M: Modulus<Output = u32>> Neg for ModU32<M> {
      type Output = Self;

      fn neg(self) -> Self {
        if self.0 == 0 {
          self
        } else {
          ModU32(M::modulus() - self.0, PhantomData)
        }
      }
    }

    impl<M: Modulus<Output = u32>> Add for ModU32<M> {
      type Output = Self;

      fn add(self, rhs: Self) -> Self {
        let temp = self.0 + rhs.0;
        ModU32(if temp >= M::modulus() { temp - M::modulus() } else { temp }, PhantomData)
      }
    }

    impl<M: Modulus<Output = u32>> Sub for ModU32<M> {
      type Output = Self;

      fn sub(self, rhs: Self) -> Self {
        self + -rhs
      }
    }

    impl<M: Modulus<Output = u32>> Mul for ModU32<M> {
      type Output = Self;

      fn mul(self, rhs: Self) -> Self {
        ModU32((self.0 as u64 * rhs.0 as u64 % M::modulus() as u64) as u32, PhantomData)
      }
    }

    macro_rules! impl_assign {
      ($($c:ident, $f:ident, $op:tt);+) => {$(
        impl<M: Modulus<Output = u32>> $c for ModU32<M> {
          fn $f(&mut self, rhs: Self) {
            *self = *self $op rhs;
          }
        }
      )+};
    }

    impl_assign! { AddAssign, add_assign, +; SubAssign, sub_assign, -; MulAssign, mul_assign, * }
  }

  mod modulus {
    pub trait Modulus {
      type Output;

      fn modulus() -> Self::Output;
    }

    pub trait PrimeModulus: Modulus {}

    pub struct Mod1000000007;

    impl Modulus for Mod1000000007 {
      type Output = u32;

      #[inline(always)]
      fn modulus() -> u32 {
        1000000007
      }
    }

    impl PrimeModulus for Mod1000000007 {}
  }
}

pub mod data_structures {
  pub use self::segment_tree::*;

  mod segment_tree {
    use math::algebra::Monoid;
    use std::iter::FromIterator;
    use std::ops::{Index, Range};

    pub struct SegmentTree<M: Monoid> {
      vec: Vec<M::T>,
      len: usize,
    }

    impl<M: Monoid> SegmentTree<M> {
      pub fn new(size: usize) -> Self {
        let len = size;
        let size = size.checked_next_power_of_two().unwrap();
        SegmentTree {
          vec: vec![M::identity(); size.checked_mul(2).unwrap()],
          len: len,
        }
      }

      pub fn len(&self) -> usize {
        self.len
      }

      fn size(&self) -> usize {
        self.vec.len() / 2
      }

      pub fn get(&mut self, index: usize) -> M::T {
        debug_assert!(index < self.len());
        self[index].clone()
      }

      pub fn set(&mut self, index: usize, x: &M::T) {
        assert!(index < self.len());
        let mut i = index + self.size();
        self.vec[i] = x.clone();
        i /= 2;
        while i > 0 {
          self.vec[i] = M::append(&self.vec[i * 2], &self.vec[i * 2 + 1]);
          i /= 2;
        }
      }

      pub fn concat(&self, range: Range<usize>) -> M::T {
        assert!(range.start <= range.end);
        assert!(range.end <= self.len());
        let mut lacc = M::identity();
        let mut racc = M::identity();
        let mut l = range.start + self.size();
        let mut r = range.end + self.size();
        while l < r {
          if l % 2 != 0 {
            lacc = M::append(&lacc, &self.vec[l]);
            l += 1;
          }
          if r % 2 != 0 {
            r -= 1;
            racc = M::append(&self.vec[r], &racc);
          }
          l /= 2;
          r /= 2;
        }
        M::append(&lacc, &racc)
      }
    }

    impl<M: Monoid> FromIterator<M::T> for SegmentTree<M> {
      fn from_iter<I: IntoIterator<Item = M::T>>(iter: I) -> Self {
        let iter = iter.into_iter();
        match iter.size_hint() {
          (lower_bound, Some(upper_bound)) if lower_bound == upper_bound => Self::from_exact_size_iter(upper_bound, iter),
          _ => {
            let vec = iter.collect::<Vec<_>>();
            Self::from_exact_size_iter(vec.len(), vec)
          }
        }
      }
    }

    impl<M: Monoid> SegmentTree<M> {
      fn from_exact_size_iter<I: IntoIterator<Item = M::T>>(len: usize, iter: I) -> Self {
        let iter = iter.into_iter();
        let size = len.checked_next_power_of_two().unwrap();
        let mut vec = Vec::with_capacity(size.checked_mul(2).unwrap());
        for _ in 0..size {
          vec.push(M::identity());
        }
        vec.extend(iter);
        for _ in 0..size - len {
          vec.push(M::identity());
        }
        for i in (1..size).rev() {
          vec[i] = M::append(&vec[i * 2], &vec[i * 2 + 1]);
        }
        debug_assert_eq!(vec.len(), size.checked_mul(2).unwrap());
        SegmentTree { vec: vec, len: len }
      }
    }

    impl<M: Monoid> Index<usize> for SegmentTree<M> {
      type Output = M::T;

      fn index(&self, index: usize) -> &M::T {
        assert!(index < self.len());
        &self.vec[index + self.size()]
      }
    }
  }
}

pub mod io {
  pub use self::scanner::*;

  mod scanner {
    use std::io::BufRead;
    use std::marker::PhantomData;
    use std::str::{FromStr, from_utf8};

    pub struct Scanner<R> {
      reader: R,
      buffer: Vec<u8>,
      position: usize,
    }

    impl<R: BufRead> Scanner<R> {
      pub fn new(reader: R) -> Self {
        Scanner { reader: reader, buffer: vec![], position: 0 }
      }

      pub fn next<T: Parse>(&mut self) -> Option<T> {
        Parse::parse(self.next_bytes().unwrap_or(&[]))
      }

      pub fn take<T: Parse>(&mut self, n: usize) -> Take<R, T> {
        Take { scanner: self, n: n, _marker: PhantomData }
      }

      pub fn next_bytes(&mut self) -> Option<&[u8]> {
        if self.buffer.is_empty() {
          self.read_line();
        }
        loop {
          match self.buffer.get(self.position) {
            Some(&b' ') => self.position += 1,
            Some(&b'\n') => self.read_line(),
            Some(_) => break,
            None => return None,
          }
        }
        let start = self.position;
        loop {
          match self.buffer.get(self.position) {
            Some(&b' ') | Some(&b'\n') | None => break,
            Some(_) => self.position += 1,
          }
        }
        Some(&self.buffer[start..self.position])
      }

      fn read_line(&mut self) {
        self.position = 0;
        self.buffer.clear();
        self.reader.read_until(b'\n', &mut self.buffer).unwrap();
      }
    }

    pub struct Take<'a, R: 'a, T> {
      scanner: &'a mut Scanner<R>,
      n: usize,
      _marker: PhantomData<fn() -> T>,
    }

    impl<'a, R: BufRead, T: Parse> Iterator for Take<'a, R, T> {
      type Item = Option<T>;

      fn next(&mut self) -> Option<Self::Item> {
        if self.n > 0 {
          self.n -= 1;
          Some(self.scanner.next())
        } else {
          None
        }
      }

      fn size_hint(&self) -> (usize, Option<usize>) {
        (self.n, Some(self.n))
      }
    }

    impl<'a, R: BufRead, T: Parse> ExactSizeIterator for Take<'a, R, T> {}

    pub trait Parse: Sized {
      fn parse(bytes: &[u8]) -> Option<Self>;
    }

    impl Parse for u8 {
      fn parse(bytes: &[u8]) -> Option<Self> {
        if bytes.len() == 1 {
          Some(*unsafe { bytes.get_unchecked(0) })
        } else {
          None
        }
      }
    }

    macro_rules! parse_impl {
      ($($t:ident)+) => {$(
        impl Parse for $t {
          fn parse(bytes: &[u8]) -> Option<Self> {
            from_utf8(bytes).ok().and_then(|s| $t::from_str(s).ok())
          }
        }
      )+};
    }

    parse_impl! { i32 i64 isize u32 u64 usize String }
  }
}