結果

問題 No.3 ビットすごろく
コンテスト
ユーザー 💕💖💞
提出日時 2017-07-22 20:11:46
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 35 ms / 5,000 ms
コード長 1,809 bytes
コンパイル時間 12,936 ms
コンパイル使用メモリ 397,780 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-01 08:47:08
合計ジャッジ時間 14,595 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `LinkedList`
 --> src/main.rs:2:33
  |
2 | use std::collections::{HashMap, LinkedList};
  |                                 ^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unnecessary parentheses around `for` iterator expression
  --> src/main.rs:16:12
   |
16 |   for i in (1..max+1) {
   |            ^        ^
   |
   = note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
   |
16 -   for i in (1..max+1) {
16 +   for i in 1..max+1 {
   |

warning: denote infinite loops with `loop { ... }`
  --> src/main.rs:29:3
   |
29 |   while true {
   |   ^^^^^^^^^^ help: use `loop`
   |
   = note: `#[warn(while_true)]` on by default

warning: unused variable: `buf`
  --> src/main.rs:21:11
   |
21 |   let mut buf:i32 = 1;
   |           ^^^ help: if this is intentional, prefix it with an underscore: `_buf`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `cnt`
  --> src/main.rs:22:11
   |
22 |   let mut cnt:i32 = 1;
   |           ^^^ help: if this is intentional, prefix it with an underscore: `_cnt`

warning: value assigned to `prevlen` is never read
  --> src/main.rs:27:11
   |
27 |   let mut prevlen = 0;
   |           ^^^^^^^
   |
   = help: maybe it is overwritten before being read?
   = note: `#[warn(unused_assignments)]` on by default

warning: unused variable: `key`
  --> src/main.rs:33:10
   |
33 |     for (key, val) in que.iter() {
   |          ^^^ help: if this is intentional, prefix it with an underscore: `_key`

warning: unused variable: `key`
  --> src/main.rs:41:10
   |
41 |     for (key, val) in que.iter() {
   |          ^^^ help: if this is intentional, prefix it with an underscore: `_key`

warning: variable does not need to be mutable
  --> src/main.rs:21:7
   |
21 |   let mut buf:i32 = 1;
   |       ----^^^
   |       |
   |       help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

warning: variable does not need to be mutab

ソースコード

diff #
raw source code 

use std::io::{self, BufRead};
use std::collections::{HashMap, LinkedList};

#[derive(Clone)]
struct P { 
  cnt:i32,
  buf:i32,
}
impl Copy for P{ }
fn main() {
  let stdin = io::stdin();
  let line  = stdin.lock().lines().next().unwrap().unwrap();
  let max   = line.parse::<i32>().unwrap();
  
  let mut m:HashMap<i32, i32> = HashMap::new();
  for i in (1..max+1) {
    let bin    = format!("{:b}", i);
    let onenum = bin.chars().filter(|&i| i == '1').count() as i32;
    m.insert(i, onenum);
  }
  let mut buf:i32 = 1;
  let mut cnt:i32 = 1;

  let p = P { cnt:1, buf:1 }; 
  let mut que:HashMap<i32, P> = HashMap::new();
  que.insert(1, p);
  let mut prevlen = 0;
  let mut cnt = 0;
  while true {
    let mut ps:Vec<P> = Vec::new();
    let mut _maxcnt:i32 = 1;
    let mut _maxbuf:i32 = 1;
    for (key, val) in que.iter() {
      if _maxcnt < val.cnt {
        _maxcnt = val.cnt;
      }
      if _maxbuf < val.buf {
        _maxbuf = val.buf;
      }
    }
    for (key, val) in que.iter() {
      if val.cnt == _maxcnt {
        ps.push(*val);
      }
    }
    if ps.len() == 0 {
      break;
    }
    if _maxbuf == max {
      cnt = _maxcnt;
      break;
     } 
    prevlen = que.len();
    for p in ps {
      let buff = p.buf;
      if m.contains_key( &(p.buf - m[&buff]) ) { 
        let pprev = P { cnt: p.cnt+1, buf: p.buf - m[&buff] };
        if ! que.contains_key( &(p.buf - m[&buff]) ) {
          que.insert(p.buf - m[&buff], pprev);
        }
      }
      if m.contains_key( &(p.buf + m[&buff]) ) { 
        let pnext = P { cnt: p.cnt+1, buf: p.buf + m[&buff] };
        if ! que.contains_key( &(p.buf + m[&buff]) ) {
          que.insert(p.buf + m[&buff], pnext);
        }
      }
    }
    if prevlen == que.len() {
      cnt = -1;
      break;
    }

  }
  println!("{}", cnt);
}
0