#263118 (Rust) No.649 ここでちょっとQK！

• 問題: No.649 ここでちょっとQK！
• ユーザー: くれちー
• 提出日時: 2018-06-06 20:34:55
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 34 ms / 3,000 ms
• コード長: 5,160 bytes
• コンパイル時間: 13,560 ms
• コンパイル使用メモリ: 402,488 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-30 10:20:12
• 合計ジャッジ時間: 17,272 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	0 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	10 ms; 5,376 KB
testcase_04	AC	31 ms; 5,376 KB
testcase_05	AC	23 ms; 5,376 KB
testcase_06	AC	23 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	1 ms; 5,376 KB
testcase_09	AC	1 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	14 ms; 5,376 KB
testcase_13	AC	14 ms; 5,376 KB
testcase_14	AC	14 ms; 5,376 KB
testcase_15	AC	16 ms; 5,376 KB
testcase_16	AC	14 ms; 5,376 KB
testcase_17	AC	18 ms; 5,376 KB
testcase_18	AC	20 ms; 5,376 KB
testcase_19	AC	22 ms; 5,376 KB
testcase_20	AC	24 ms; 5,376 KB
testcase_21	AC	26 ms; 5,376 KB
testcase_22	AC	28 ms; 5,376 KB
testcase_23	AC	30 ms; 5,376 KB
testcase_24	AC	30 ms; 5,376 KB
testcase_25	AC	31 ms; 5,376 KB
testcase_26	AC	34 ms; 5,376 KB
testcase_27	AC	1 ms; 5,376 KB
testcase_28	AC	1 ms; 5,376 KB
testcase_29	AC	1 ms; 5,376 KB
testcase_30	AC	11 ms; 5,376 KB
testcase_31	AC	13 ms; 5,376 KB
testcase_32	AC	1 ms; 5,376 KB
testcase_33	AC	1 ms; 5,376 KB
testcase_34	AC	1 ms; 5,376 KB
testcase_35	AC	1 ms; 5,376 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) => {
      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 std::collections::BinaryHeap;

  let (q, k) = scan!(usize, usize);
  let mut max_heap = BinaryHeap::with_capacity(k);
  let mut min_heap = BinaryHeap::with_capacity(q - k);

  for _ in 0..q {
    match scan!(u8) {
      b'1' => {
        let v = scan!(i64);
        if max_heap.len() < k {
          max_heap.push(v);
        } else if max_heap.peek().cloned().unwrap() > v {
          min_heap.push(-max_heap.pop().unwrap());
          max_heap.push(v);
        } else {
          min_heap.push(-v);
        }
      }
      b'2' => {
        if max_heap.len() == k {
          let v = max_heap.pop().unwrap();
          println!("{}", v);
          if let Some(v) = min_heap.pop() {
            max_heap.push(-v);
          }
        } else {
          println!("-1");
        }
      }
      _ => 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 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 }
  }
}