#263137 (Rust) No.647 明太子

• 問題: No.647 明太子
• ユーザー: くれちー
• 提出日時: 2018-06-06 21:57:50
• 言語: Rust (1.77.0 + proconio)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 15,457 bytes
• コンパイル時間: 12,154 ms
• コンパイル使用メモリ: 389,872 KB
• 最終ジャッジ日時: 2024-11-14 20:26:34
• 合計ジャッジ時間: 13,534 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

コンパイルメッセージ

error: expected one of `!`, `(`, `...`, `..=`, `..`, `::`, `:`, `{`, or `|`, found `)`
   --> src/main.rs:218:27
    |
218 |         fn invert(&Self::T) -> Self::T;
    |                           ^ expected one of 9 possible tokens
    |
    = note: anonymous parameters are removed in the 2018 edition (see RFC 1685)
help: explicitly ignore the parameter name
    |
218 |         fn invert(_: &Self::T) -> Self::T;
    |                   ~~~~~~~~~~~

error[E0433]: failed to resolve: use of undeclared crate or module `math`
   --> src/main.rs:207:11
    |
207 |       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:215:11
    |
215 |       use math::algebra::Monoid;
    |           ^^^^ use of undeclared crate or module `math`

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

error[E0433]: failed to resolve: use of undeclared crate or module `math`
   --> src/main.rs:237:11
    |
237 |       use math::algebra::{CommutativeMonoid, Group};
    |           ^^^^ use of undeclared crate or module `math`

error[E0433]: failed to resolve: use of undeclared crate or module `math`
   --> src/main.rs:305:9
    |
305 |     use math::algebra::{CommutativeGroup, CommutativeMonoid};
    |         ^^^^ use of undeclared crate or module `math`

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

warning: unused macro definition: `commutative_monoid_impl`
  --> src/main.rs:37:14
   |
37 | macro_rules! commutative_monoid_im

ソースコード

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
      }
    }
  };
}

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

    impl $crate::math::algebra::Group for $marker {
      fn invert($x: &$t) -> $t {
        $invert
      }
    }
  };
}

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

    impl $crate::math::algebra::CommutativeMonoid for $marker {}
  };
}

macro_rules! commutative_group_impl {
  ($marker:ty, $t:ty, | $lhs:ident, $rhs:ident | $append:expr, | $x:ident | $invert:expr, $identity:expr) => {
    group_impl! { $marker, $t, |$lhs, $rhs| $append, |$x| $invert, $identity }

    impl $crate::math::algebra::CommutativeMonoid for $marker {}

    impl $crate::math::algebra::CommutativeGroup for $marker {}
  };
}

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::{CoordinateCompressor, FenwickTree};
  use math::algebra::AdditiveGroup;
  use std::iter::FromIterator;

  let n = scan!(usize);
  let (a, b) = scan!(i64, i64; n);
  let m = scan!(usize);
  let (x, y) = scan!(i64, i64; m);

  let compressor = CoordinateCompressor::from_iter(b.iter().chain(y.iter()).cloned());
  let mut fenwick_tree = FenwickTree::<AdditiveGroup<i64>>::new(compressor.len());

  enum Type {
    People,
    Mentaiko,
  }

  let mut stream = Vec::with_capacity(n + m);
  for (i, (a, b)) in a.into_iter().zip(b).enumerate() {
    stream.push((i, Type::People, a, b));
  }
  for (i, (x, y)) in x.into_iter().zip(y).enumerate() {
    stream.push((i, Type::Mentaiko, x, y));
  }
  stream.sort_by_key(|&(_, _, p, _)| -p);

  let mut max = 0;
  let mut ans = Vec::with_capacity(m);
  for (i, t, _, q) in stream {
    let q = compressor.compress(q).unwrap();
    match t {
      Type::People => fenwick_tree.append(q, &1),
      Type::Mentaiko => {
        let crt = fenwick_tree.prefix_concat(..q + 1);
        if crt > max {
          ans.clear();
          max = crt;
          ans.push(i + 1);
        } else if crt == max {
          ans.push(i + 1);
        }
      }
    }
  }

  if max == 0 {
    println!("0");
    return;
  }
  ans.sort();
  for i in ans.into_iter() {
    println!("{}", i);
  }
}

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 mod algebra {
    pub use self::additive_group::*;
    pub use self::commutative_group::*;
    pub use self::commutative_monoid::*;
    pub use self::group::*;
    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 group {
      use math::algebra::Monoid;

      pub trait Group: Monoid {
        fn invert(&Self::T) -> Self::T;

        fn append_inverse(lhs: &Self::T, rhs: &Self::T) -> Self::T {
          Self::append(lhs, &Self::invert(rhs))
        }

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

    mod commutative_monoid {
      use math::algebra::Monoid;

      pub trait CommutativeMonoid: Monoid {}
    }

    mod commutative_group {
      use math::algebra::{CommutativeMonoid, Group};

      pub trait CommutativeGroup: Group + CommutativeMonoid {}
    }

    mod additive_group {
      use std::marker::PhantomData;

      pub struct AdditiveGroup<T> {
        _marker: PhantomData<fn() -> T>,
      }

      macro_rules! additive_group_impl {
        ($($t:ty)+) => {$(
          commutative_group_impl! { AdditiveGroup<$t>, $t, |lhs, rhs| lhs + rhs, |x| -x, 0 }
        )+};
      }

      additive_group_impl! { i32 i64 isize }
    }
  }
}

pub mod data_structures {
  pub use self::coordinate_compressor::*;
  pub use self::fenwick_tree::*;

  mod coordinate_compressor {
    use std::collections::HashMap;
    use std::hash::Hash;
    use std::iter::FromIterator;

    pub struct CoordinateCompressor<T> {
      map: HashMap<T, usize>,
      vec: Vec<T>,
    }

    impl<T: Eq + Hash> CoordinateCompressor<T> {
      pub fn len(&self) -> usize {
        debug_assert_eq!(self.map.len(), self.vec.len());
        self.map.len()
      }

      pub fn compress(&self, x: T) -> Option<usize> {
        self.map.get(&x).cloned()
      }

      pub fn decompress(&self, index: usize) -> Option<&T> {
        self.vec.get(index)
      }
    }

    impl<T: Clone + Ord + Hash> FromIterator<T> for CoordinateCompressor<T> {
      fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut vec = iter.into_iter().collect::<Vec<_>>();
        vec.sort();
        vec.dedup();
        vec.shrink_to_fit();
        let mut map = HashMap::with_capacity(vec.len());
        for (i, x) in vec.iter_mut().enumerate() {
          map.insert(x.clone(), i);
        }
        CoordinateCompressor { map: map, vec: vec }
      }
    }
  }

  mod fenwick_tree {
    use math::algebra::{CommutativeGroup, CommutativeMonoid};
    use search::BinarySearch;
    use std::iter::FromIterator;
    use std::ops::{Range, RangeTo};

    pub struct FenwickTree<M: CommutativeMonoid> {
      vec: Vec<M::T>,
    }

    impl<M: CommutativeMonoid> FenwickTree<M> {
      pub fn new(size: usize) -> Self {
        FenwickTree { vec: vec![M::identity(); size + 1] }
      }

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

      pub fn append(&mut self, index: usize, x: &M::T) {
        assert!(index < self.len());
        let mut i = index as isize + 1;
        while i <= self.len() as isize {
          M::append_assign(&mut self.vec[i as usize], x);
          i += i & -i;
        }
      }

      pub fn prefix_concat(&self, range: RangeTo<usize>) -> M::T {
        assert!(range.end <= self.len());
        let mut acc = M::identity();
        let mut r = range.end as isize;
        while r > 0 {
          M::append_assign(&mut acc, &self.vec[r as usize]);
          r -= r & -r;
        }
        acc
      }
    }

    impl<G: CommutativeGroup> FenwickTree<G> {
      pub fn get(&self, index: usize) -> G::T {
        debug_assert!(index < self.len());
        self.cocnat(index..index + 1)
      }

      pub fn set(&mut self, index: usize, x: &G::T) {
        debug_assert!(index < self.len());
        let diff = G::append_inverse(x, &self.get(index));
        self.append(index, &diff);
      }

      pub fn cocnat(&self, range: Range<usize>) -> G::T {
        assert!(range.start <= range.end);
        assert!(range.end <= self.len());
        let mut acc = G::identity();
        let mut l = range.start as isize;
        let mut r = range.end as isize;
        while l < r {
          G::append_assign(&mut acc, &self.vec[r as usize]);
          r -= r & -r;
        }
        while r < l {
          G::append_inverse_assign(&mut acc, &self.vec[l as usize]);
          l -= l & -l;
        }
        acc
      }
    }

    impl<G: CommutativeGroup> BinarySearch<G::T> for FenwickTree<G> {
      type Output = RangeTo<usize>;

      fn binary_search<F: FnMut(&G::T) -> bool>(&self, mut f: F) -> Option<RangeTo<usize>> {
        let mut i = 0usize;
        let mut sum = G::identity();
        let mut k = if self.len().is_power_of_two() { self.len() } else { self.len().next_power_of_two() / 2 };
        while k > 0 {
          if let Some(current_segment_sum) = self.vec.get(i + k) {
            if !f(&G::append(current_segment_sum, &sum)) {
              G::append_assign(&mut sum, current_segment_sum);
              i += k;
            }
          }
          k /= 2;
        }
        if i < self.len() {
          Some(..i + 1)
        } else {
          None
        }
      }
    }

    impl<M: CommutativeMonoid> FromIterator<M::T> for FenwickTree<M> {
      fn from_iter<I: IntoIterator<Item = M::T>>(iter: I) -> Self {
        let iter = iter.into_iter();
        let mut vec = Vec::with_capacity(1 + iter.size_hint().0);
        vec.push(M::identity());
        vec.extend(iter);
        for i in 1..(vec.len() - 1) as isize {
          let j = (i + (i & -i)) as usize;
          if j < vec.len() {
            vec[j] = M::append(&vec[j], &vec[i as usize]);
          }
        }
        vec.shrink_to_fit();
        FenwickTree { vec: vec }
      }
    }
  }
}

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

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

    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 }
  }
}

pub mod search {
  pub use self::binary_search::*;

  mod binary_search {
    use std::ops::Range;

    pub trait BinarySearch<T> {
      type Output;

      fn binary_search<F: FnMut(&T) -> bool>(&self, f: F) -> Option<Self::Output>;

      fn lower_bound(&self, x: &T) -> Option<Self::Output>
      where
        T: Ord,
      {
        self.binary_search(|t| t >= x)
      }

      fn upper_bound(&self, x: &T) -> Option<Self::Output>
      where
        T: Ord,
      {
        self.binary_search(|t| t > x)
      }
    }

    macro_rules! binary_search_impl {
      ($ok:expr, $ng:expr, $cond1:expr, $cond2:expr) => {{
        let mut ok_end = $ok;
        let mut ng_start = $ng;
        while ok_end - ng_start > 1 {
          let mid = ng_start + (ok_end - ng_start) / 2;
          if $cond1(mid) {
            ok_end = mid;
          } else {
            ng_start = mid;
          }
        }
        if $cond2(ok_end) {
          None
        } else {
          Some(ok_end as Self::Output)
        }
      }};
    }

    impl<T> BinarySearch<T> for [T] {
      type Output = usize;

      fn binary_search<F: FnMut(&T) -> bool>(&self, mut f: F) -> Option<Self::Output> {
        binary_search_impl!(self.len() as isize, -1isize, |mid| f(&self[mid as usize]), |ok_end| ok_end as usize == self.len())
      }
    }

    macro_rules! binary_search_impl_range {
      ($t:ty, $it:ty) => {
        impl BinarySearch<$t> for Range<$t> {
          type Output = $t;

          fn binary_search<F: FnMut(&$t) -> bool>(&self, mut f: F) -> Option<$t> {
            assert!(self.start <= self.end);
            binary_search_impl!(self.end as $it, self.start as $it - 1, |mid| f(&(mid as $t)), |ok_end| ok_end == self.end as $it)
          }
        }
      };
      ($($ut:ty, $it:ty);+) => {$(
        binary_search_impl_range! { $ut, $it }
        binary_search_impl_range! { $it, $it }
      )+};
    }

    binary_search_impl_range! { usize, isize; u32, i32; u64, i64 }
  }
}