#268340 (Rust) No.9 モンスターのレベル上げ

• 問題: No.9 モンスターのレベル上げ
• ユーザー: くれちー
• 提出日時: 2018-06-24 02:31:22
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 2,232 ms / 5,000 ms
• コード長: 10,221 bytes
• コンパイル時間: 4,004 ms
• コンパイル使用メモリ: 156,520 KB
• 実行使用メモリ: 4,380 KB
• 最終ジャッジ日時: 2023-09-13 08:40:57
• 合計ジャッジ時間: 20,352 ms
• ジャッジサーバーID （参考情報）: judge15 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 4,376 KB
testcase_01	AC	1 ms; 4,380 KB
testcase_02	AC	2,232 ms; 4,380 KB
testcase_03	AC	1,723 ms; 4,380 KB
testcase_04	AC	899 ms; 4,376 KB
testcase_05	AC	581 ms; 4,376 KB
testcase_06	AC	194 ms; 4,376 KB
testcase_07	AC	3 ms; 4,380 KB
testcase_08	AC	264 ms; 4,380 KB
testcase_09	AC	2,138 ms; 4,380 KB
testcase_10	AC	0 ms; 4,380 KB
testcase_11	AC	740 ms; 4,376 KB
testcase_12	AC	285 ms; 4,380 KB
testcase_13	AC	612 ms; 4,380 KB
testcase_14	AC	2,141 ms; 4,380 KB
testcase_15	AC	1,967 ms; 4,380 KB
testcase_16	AC	29 ms; 4,376 KB
testcase_17	AC	1,235 ms; 4,376 KB
testcase_18	AC	1,036 ms; 4,376 KB
testcase_19	AC	17 ms; 4,380 KB

ソースコード

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 $(; $m:expr)*) => {{
      let mut vec = Vec::with_capacity($n);
      for _ in 0..$n {
        vec.push(scan!($t $(; $m)*));
      }
      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()
    };
  }

  #[allow(unused_macros)]
  macro_rules! eprint {
    ($fmt:expr) => {
      #[cfg(debug_assertions)]
      write!(::std::io::stderr(), $fmt).unwrap()
    };
    ($fmt:expr, $($arg:tt)*) => {
      #[cfg(debug_assertions)]
      write!(::std::io::stderr(), $fmt, $($arg)*).unwrap()
    };
  }

  #[allow(unused_macros)]
  macro_rules! eprintln {
    () => {
      #[cfg(debug_assertions)]
      writeln!(::std::io::stderr()).unwrap()
    };
    ($fmt:expr) => {
      #[cfg(debug_assertions)]
      writeln!(::std::io::stderr(), $fmt).unwrap()
    };
    ($fmt:expr, $($arg:tt)*) => {
      #[cfg(debug_assertions)]
      writeln!(::std::io::stderr(), $fmt, $($arg)*).unwrap()
    };
  }

  #[allow(unused_macros)]
  macro_rules! dump {
    ($($x:expr),+) => {
      eprint!("[{}:{}] ", file!(), line!());
      eprintln!(concat!($(stringify!($x), "={:?}; "),+), $($x),+);
    };
  }

  use cmp::{OrdAssign, Reverse};
  use data_structures::PairingHeap;

  let n = scan!(usize);
  let a = scan!(i32; n);
  let b = scan!(i32; n);

  let mut pq = PairingHeap::new();
  let mut ans = i32::max_value();

  for i in 0..n {
    let mut cnt_max = 0;
    pq.extend(a.iter().map(|&a_i| Reverse((a_i, 0))));
    for j in 0..n {
      let k = if i + j >= n { i + j - n } else { i + j };
      let Reverse((x, cnt)) = pq.pop().unwrap();
      cnt_max.max_assign(cnt + 1);
      pq.push(Reverse((x + b[k] / 2, cnt + 1)));
    }
    ans.min_assign(cnt_max);
    pq.clear();
  }

  println!("{}", ans);
}

const STACK_SIZE_MEBIBYTES: Option<usize> = None;

fn main() {
  fn run_solver() {
    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();
  }
  if let Some(size) = STACK_SIZE_MEBIBYTES {
    let builder = ::std::thread::Builder::new().stack_size(size * 1024 * 1024);
    builder.spawn(run_solver).unwrap().join().unwrap();
  } else {
    run_solver();
  }
}

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

pub mod cmp {
  pub use self::ord_assign::*;
  pub use self::reverse::*;

  mod ord_assign {
    use std::cmp::{max, min};

    pub trait OrdAssign: Ord
    where
      Self: Copy,
    {
      fn min_assign(&mut self, other: Self) {
        *self = min(*self, other);
      }

      fn max_assign(&mut self, other: Self) {
        *self = max(*self, other);
      }
    }

    impl<T: Ord + Copy> OrdAssign for T {}
  }

  mod reverse {
    use std::cmp::Ordering;

    #[derive(Clone, Copy, PartialEq, Eq, Default, Debug, Hash)]
    pub struct Reverse<T>(pub T);

    impl<T: PartialOrd> PartialOrd for Reverse<T> {
      fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        other.0.partial_cmp(&self.0)
      }
    }

    impl<T: Ord> Ord for Reverse<T> {
      fn cmp(&self, other: &Self) -> Ordering {
        other.0.cmp(&self.0)
      }
    }
  }
}

pub mod data_structures {
  pub use self::pairing_heap::PairingHeap;

  mod pairing_heap {
    use std::collections::LinkedList;
    use std::mem::{replace, swap};

    #[derive(Clone, Debug)]
    pub struct PairingHeap<T> {
      root: Option<Node<T>>,
      len: usize,
    }

    #[derive(Clone, Debug)]
    struct Node<T> {
      key: T,
      children: LinkedList<Option<Node<T>>>,
    }

    impl<T> Node<T> {
      fn new(x: T) -> Self {
        Node { key: x, children: LinkedList::new() }
      }
    }

    impl<T: Ord> PairingHeap<T> {
      pub fn new() -> Self {
        PairingHeap { root: None, len: 0 }
      }

      pub fn peek(&self) -> Option<&T> {
        self.root.as_ref().map(|node| &node.key)
      }

      pub fn pop(&mut self) -> Option<T> {
        replace(&mut self.root, None).map(|node| {
          self.root = Self::merge_list(node.children);
          self.len -= 1;
          node.key
        })
      }

      pub fn push(&mut self, x: T) {
        self.root = Self::merge(replace(&mut self.root, None), Some(Node::new(x)));
        self.len += 1;
      }

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

      pub fn is_empty(&self) -> bool {
        debug_assert_eq!(self.root.is_none(), self.len == 0);
        self.len == 0
      }

      pub fn clear(&mut self) {
        self.root = None;
        self.len = 0;
      }

      pub fn append(&mut self, other: &mut Self) {
        self.root = Self::merge(replace(&mut self.root, None), replace(&mut other.root, None));
        self.len += other.len;
        other.len = 0;
        debug_assert!(other.is_empty());
      }

      fn merge(l: Option<Node<T>>, r: Option<Node<T>>) -> Option<Node<T>> {
        match (l, r) {
          (l, None) => l,
          (None, r) => r,
          (Some(mut l), Some(mut r)) => {
            if l.key < r.key {
              swap(&mut l, &mut r);
            }
            debug_assert!(l.key >= r.key);
            l.children.push_back(Some(r));
            Some(l)
          }
        }
      }

      fn merge_list(mut xs: LinkedList<Option<Node<T>>>) -> Option<Node<T>> {
        let mut acc = None;
        loop {
          match (xs.pop_back(), xs.pop_back()) {
            (Some(l), Some(r)) => acc = Self::merge(Self::merge(l, r), acc),
            (Some(x), None) => acc = Self::merge(x, acc),
            (None, None) => break,
            _ => unreachable!(),
          }
        }
        acc
      }
    }

    impl<T: Ord> Default for PairingHeap<T> {
      fn default() -> Self {
        Self::new()
      }
    }

    impl<T: Ord> Extend<T> for PairingHeap<T> {
      fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        for x in iter {
          self.push(x);
        }
      }
    }

    impl<T: Ord> IntoIterator for PairingHeap<T> {
      type Item = T;
      type IntoIter = IntoIter<T>;

      fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
      }
    }

    pub struct IntoIter<T>(PairingHeap<T>);

    impl<T: Ord> Iterator for IntoIter<T> {
      type Item = T;

      fn next(&mut self) -> Option<T> {
        self.0.pop()
      }
    }
  }
}

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