結果
問題 | No.3 ビットすごろく |
ユーザー |
![]() |
提出日時 | 2021-09-27 00:51:05 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,082 bytes |
コンパイル時間 | 1,997 ms |
コンパイル使用メモリ | 219,320 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-22 12:39:29 |
合計ジャッジ時間 | 3,107 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 33 |
ソースコード
import std; import core.bitop; struct Sugoroku { int pos; int cnt; } void main() { int N; readf("%d\n", N); auto heap = new BinaryHeap!(Array!Sugoroku, "a.cnt > b.cnt")(); heap.insert(Sugoroku(1, 1)); auto passed = new bool[](N+1); passed[0..2] = true; int res = int.max; while (!heap.empty) { Sugoroku sugoroku = heap.front; heap.popFront; if (sugoroku.pos == N) { res = min(res, sugoroku.cnt); } int forward = sugoroku.pos + sugoroku.pos.popcnt; if (forward == N) { res = min(res, sugoroku.cnt+1); } else if (forward < N && !passed[forward]) { passed[forward] = true; heap.insert(Sugoroku(forward, sugoroku.cnt+1)); } int backward = sugoroku.pos - sugoroku.pos.popcnt; if (backward >= 1 && !passed[backward]) { passed[backward] = true; heap.insert(Sugoroku(backward, sugoroku.cnt+1)); } } if (res == int.max) { res = -1; } res.writeln; }