結果

問題 No.3 ビットすごろく
ユーザー 💕💖💞💕💖💞
提出日時 2017-07-22 20:11:46
言語 Rust
(1.77.0)
結果
AC  
実行時間 39 ms / 5,000 ms
コード長 1,809 bytes
コンパイル時間 1,828 ms
コンパイル使用メモリ 161,972 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-14 00:47:00
合計ジャッジ時間 3,628 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 0 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 4 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 13 ms
4,376 KB
testcase_06 AC 5 ms
4,376 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 8 ms
4,376 KB
testcase_09 AC 19 ms
4,376 KB
testcase_10 AC 25 ms
4,376 KB
testcase_11 AC 17 ms
4,376 KB
testcase_12 AC 12 ms
4,376 KB
testcase_13 AC 3 ms
4,376 KB
testcase_14 AC 25 ms
4,376 KB
testcase_15 AC 38 ms
4,380 KB
testcase_16 AC 32 ms
4,380 KB
testcase_17 AC 36 ms
4,380 KB
testcase_18 AC 3 ms
4,380 KB
testcase_19 AC 39 ms
4,380 KB
testcase_20 AC 2 ms
4,376 KB
testcase_21 AC 1 ms
4,376 KB
testcase_22 AC 26 ms
4,376 KB
testcase_23 AC 39 ms
4,380 KB
testcase_24 AC 39 ms
4,376 KB
testcase_25 AC 38 ms
4,384 KB
testcase_26 AC 1 ms
4,380 KB
testcase_27 AC 3 ms
4,376 KB
testcase_28 AC 32 ms
4,376 KB
testcase_29 AC 18 ms
4,376 KB
testcase_30 AC 1 ms
4,384 KB
testcase_31 AC 1 ms
4,376 KB
testcase_32 AC 16 ms
4,380 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `LinkedList`
 --> Main.rs:2:33
  |
2 | use std::collections::{HashMap, LinkedList};
  |                                 ^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unnecessary parentheses around `for` iterator expression
  --> 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 { ... }`
  --> Main.rs:29:3
   |
29 |   while true {
   |   ^^^^^^^^^^ help: use `loop`
   |
   = note: `#[warn(while_true)]` on by default

warning: unused variable: `buf`
  --> 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`
  --> 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
  --> 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`
  --> 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`
  --> 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
  --> 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 mutable
  --> Main.rs:22:7
   |
22 |   le

ソースコード

diff # 

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