#273873 (Rust) No.702 中央値を求めよ LIMITED

• 問題: No.702 中央値を求めよ LIMITED
• ユーザー: くれちー
• 提出日時: 2018-07-20 22:29:00
• 言語: Rust (1.83.0 + proconio)
• 結果: CE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 7,958 bytes
• コンパイル時間: 13,343 ms
• コンパイル使用メモリ: 392,912 KB
• 最終ジャッジ日時: 2024-11-14 20:33:25
• 合計ジャッジ時間: 14,040 ms
• ジャッジサーバーID （参考情報）: judge1 / judge2

コンパイルメッセージ

error[E0432]: unresolved import `io`
   --> src/main.rs:160:9
    |
160 |     use io::FromBytes;
    |         ^^ help: a similar path exists: `crate::io`
    |
    = 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[E0432]: unresolved import `misc`
   --> src/main.rs:239:9
    |
239 |     use misc::{ByteChar, ByteString};
    |         ^^^^ help: a similar path exists: `crate::misc`
    |
    = 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[E0432]: unresolved import `misc`
   --> src/main.rs:306:9
    |
306 |     use misc::ByteChar;
    |         ^^^^ help: a similar path exists: `crate::misc`
    |
    = note: `use` statements changed in Rust 2018; read more at <https://doc.rust-lang.org/edition-guide/rust-2018/module-system/path-clarity.html>

For more information about this error, try `rustc --explain E0432`.
error: could not compile `main` (bin "main") due to 3 previous errors

ソースコード

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 {
    ($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 {
    ($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 std::num::Wrapping;
  use std::u32;

  let seed = scan!(u32);

  let mut x = Wrapping(seed);
  let mut y = Wrapping(1u32);
  let mut z = Wrapping(2u32);
  let mut w = Wrapping(3u32);
  let mut generate = || {
    let t = x ^ (x << 11);
    x = y;
    y = z;
    z = w;
    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    w.0
  };

  const A_LEN: usize = 10000001;
  const A_MID: u32 = u32::MAX / 2;
  const DIFF: u32 = 5000000;

  let mut less_cnt = 0;
  let mut vec = Vec::with_capacity(10000);
  for _ in 0..A_LEN {
    let v = generate();
    if v < A_MID - DIFF {
      less_cnt += 1;
    } else if v > A_MID + DIFF {
    } else {
      vec.push(v);
    }
  }
  vec.sort();
  dump!(less_cnt, vec.len());
  println!("{}", vec[A_LEN / 2 - less_cnt]);
}

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 io {
  pub use self::from_bytes::*;
  pub use self::scanner::*;

  mod scanner {
    use io::FromBytes;
    use std::io::BufRead;
    use std::marker::PhantomData;

    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: FromBytes>(&mut self) -> Result<T, T::Err> {
        FromBytes::from_bytes(self.next_bytes().unwrap_or(&[]))
      }

      pub fn take<T: FromBytes>(&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: FromBytes> Iterator for Take<'a, R, T> {
      type Item = Result<T, T::Err>;

      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: FromBytes> ExactSizeIterator for Take<'a, R, T> {}
  }

  mod from_bytes {
    use misc::{ByteChar, ByteString};
    use std::str;
    use std::str::FromStr;

    pub struct FromBytesError;

    pub trait FromBytes: Sized {
      type Err;

      fn from_bytes(bytes: &[u8]) -> Result<Self, Self::Err>;
    }

    impl FromBytes for ByteChar {
      type Err = FromBytesError;

      fn from_bytes(bytes: &[u8]) -> Result<Self, Self::Err> {
        if bytes.len() == 1 {
          Ok(ByteChar(*unsafe { bytes.get_unchecked(0) }))
        } else {
          Err(FromBytesError)
        }
      }
    }

    impl FromBytes for ByteString {
      type Err = FromBytesError;

      fn from_bytes(bytes: &[u8]) -> Result<Self, Self::Err> {
        Ok(ByteString(bytes.iter().cloned().map(ByteChar).collect()))
      }
    }

    impl<T: FromStr> FromBytes for T {
      type Err = T::Err;

      fn from_bytes(bytes: &[u8]) -> Result<Self, Self::Err> {
        let s = if cfg!(debug_assertions) { str::from_utf8(bytes).unwrap() } else { unsafe { str::from_utf8_unchecked(bytes) } };
        T::from_str(s)
      }
    }
  }
}

pub mod misc {
  pub use self::byte_char::*;
  pub use self::byte_string::*;

  mod byte_char {
    use std::fmt::{Debug, Display, Error, Formatter};

    #[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Hash)]
    pub struct ByteChar(pub u8);

    impl Debug for ByteChar {
      fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
        write!(f, "b\'{}\'", self.0 as char)
      }
    }

    impl Display for ByteChar {
      fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
        write!(f, "{}", self.0 as char)
      }
    }
  }

  mod byte_string {
    use misc::ByteChar;
    use std::fmt::{Debug, Display, Error, Formatter};

    #[derive(Clone, PartialOrd, Ord, PartialEq, Eq, Hash)]
    pub struct ByteString(pub Vec<ByteChar>);

    impl Debug for ByteString {
      fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
        write!(f, "b\"")?;
        for &c in &self.0 {
          write!(f, "{}", c.0 as char)?;
        }
        write!(f, "b\"")
      }
    }

    impl Display for ByteString {
      fn fmt(&self, f: &mut Formatter) -> Result<(), Error> {
        for &c in &self.0 {
          write!(f, "{}", c.0 as char)?;
        }
        Ok(())
      }
    }
  }
}