結果

問題 No.3 ビットすごろく
コンテスト
ユーザー n_knuu
提出日時 2017-01-04 20:05:13
言語 Nim
(2.2.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,969 bytes
コンパイル時間 4,353 ms
コンパイル使用メモリ 66,172 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 08:16:25
合計ジャッジ時間 5,265 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(7, 20) Warning: inherit from a more precise exception type like ValueError, IOError or OSError. If these don't suit, inherit from CatchableError or Defect. [InheritFromException]

ソースコード

diff #
raw source code 

import strutils, sequtils
type
  Heap[T]= object
    data: seq[T]
    size: int
    comp: proc (x: T, y: T): int
  EmptyHeapError = object of Exception

proc siftup[T](h: var Heap[T]) =
  var i = h.size - 1
  while i > 0:
    var par = (i-1) div 2
    if h.comp(h.data[par], h.data[i]) > 0:
      swap(h.data[i], h.data[par])
      i = par
    else:
      break
proc siftdown[T](h: var Heap[T]) =
  var par = 0
  while par < h.size:
    let (left, right) = (2*par+1, 2*par+2)
    if right < h.size:
      if h.comp(h.data[par], min(h.data[left], h.data[right])) <= 0:
        break
      elif h.comp(h.data[left], h.data[right]) < 0:
        swap(h.data[par], h.data[left])
        par = left
      else:
        swap(h.data[par], h.data[right])
        par = right
    elif left < h.size:
      if h.comp(h.data[left], h.data[par]) < 0:
        swap(h.data[par], h.data[left])
        par = left
      else:
        break
    else:
      break
proc initHeap[T](comparator: proc (x: T, y: T): int = cmp): Heap[T] =
  Heap[T](data: newSeq[T](), size: 0, comp: comparator)
proc push[T](h: var Heap[T], x: T) =
  h.data.add(x)
  h.size.inc
  h.siftup
proc pop[T](h: var Heap[T]): T =
  if h.size <= 0:
    raise newException(EmptyHeapError, "cannot pop element, heap is empty")
  result = h.data[0]
  h.data[0] = h.data[^1]
  h.size.dec
  h.data.setlen(h.size)
  h.siftdown
proc empty[T](h: var Heap[T]): bool {. inline .} = h.data.len == 0

proc popcount(x: int): cint {.
  importc: "__builtin_popcount", nodecl, nosideeffect.}

let N = stdin.readline.parseInt
var
  dist = newSeqWith(N+1, 1e9.int)
  pque = initHeap[(int, int)]()
pque.push((1, 1))
while not pque.empty:
  let (c, v) = pque.pop
  if dist[v] <= c:
    continue
  dist[v] = c
  if v == N:
    echo(c)
    quit()
  let pcnt = popcount(v)
  for sgn in @[-1, 1]:
    if 0 < v + sgn * pcnt and v + sgn * pcnt <= N and dist[v] + 1 < dist[v + sgn * pcnt]:
      pque.push((dist[v] + 1, v + sgn * pcnt))
echo(-1)
0