#258864 (Rust) No.688 E869120 and Constructing Array 2

• 問題: No.688 E869120 and Constructing Array 2
• ユーザー: くれちー
• 提出日時: 2018-05-19 00:12:47
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 1 ms / 1,000 ms
• コード長: 3,759 bytes
• コンパイル時間: 11,753 ms
• コンパイル使用メモリ: 400,780 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-07-07 13:44:31
• 合計ジャッジ時間: 12,697 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	0 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	1 ms; 5,376 KB
testcase_05	AC	1 ms; 5,376 KB
testcase_06	AC	1 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	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>() };
    ($($t:ty),+) => { ($(scan!($t)),+) };
    ($t:ty; $n:expr) => {{
      let mut vec = Vec::with_capacity($n);
      for _ in 0..$n {
        vec.push(scan!($t));
      }
      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! println {
    () => { writeln!(_writer).unwrap() };
    ($fmt:expr) => { writeln!(_writer, $fmt).unwrap() };
    ($fmt:expr, $($arg:tt)*) => { writeln!(_writer, $fmt, $($arg)*).unwrap() };
  }

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

  let k = scan!(u64);
  if k == 0 {
    println!("{}", 1);
    println!("{}", 0);
    return;
  }

  fn noel_chan(x: u64) -> Option<u64> {
    let x = x * 2;
    let a = f64::sqrt(x as f64) as u64;
    let b = x / a;
    if a * b == x && max(a, b) - min(a, b) == 1 {
      Some(max(a, b))
    } else {
      None
    }
  }

  fn taplis_chan(k: u64, min_cnt0: u64) -> Result<(u64, String), u64> {
    let mut cnt0 = min_cnt0;
    let mut comb0 = 2u64.pow(cnt0 as u32);
    while k % comb0 != 0 || noel_chan(k / comb0).is_none() {
      cnt0 += 1;
      comb0 *= 2;
    }
    let cnt1 = noel_chan(k / comb0).unwrap();
    let n = cnt0 + cnt1;
    if n < 1 || 30 < n {
      return Err(cnt0);
    }

    let mut b_str = String::new();
    for _ in 0..cnt0 {
      b_str += "0 ";
    }
    for _ in 0..cnt1 {
      b_str += "1 ";
    }
    Ok((n, b_str))
  }

  let mut min_cnt0 = 0;
  loop {
    match taplis_chan(k, min_cnt0) {
      Ok((n, b_str)) => {
        println!("{}", n);
        println!("{}", b_str);
        return;
      }
      Err(cnt_0) => {
        min_cnt0 = cnt_0 + 1;
      }
    }
  }
}

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

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

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

  mod scanner {
    use std::fmt::Debug;
    use std::io::BufRead;
    use std::str;
    use std::str::FromStr;

    pub struct Scanner<R: BufRead> {
      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: FromStr>(&mut self) -> T
      where
        T::Err: Debug,
      {
        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 => panic!("EOF reached"),
          }
        }
        let start = self.position;
        loop {
          match self.buffer.get(self.position) {
            Some(&b' ') | Some(&b'\n') | None => break,
            Some(_) => self.position += 1,
          }
        }
        str::from_utf8(&self.buffer[start..self.position]).unwrap().parse().unwrap()
      }

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