結果

問題 No.120 傾向と対策：門松列（その１）
コンテスト
ユーザー むらため
提出日時 2019-10-12 16:08:25
言語 Nim
(2.2.0)
結果
AC  
実行時間 18 ms / 5,000 ms
コード長 3,168 bytes
コンパイル時間 2,522 ms
コンパイル使用メモリ 61,764 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-28 02:08:53
合計ジャッジ時間 3,000 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4
権限があれば一括ダウンロードができます
コンパイルメッセージ
/home/judge/data/code/Main.nim(2, 8) Warning: imported and not used: 'sequtils' [UnusedImport]

ソースコード

diff # 

{.checks:off,optimization:speed.}
import sequtils,algorithm
template times*(n:int,body) = (for _ in 0..<n: body)
template `max=`*(x,y) = x = max(x,y)
template `min=`*(x,y) = x = min(x,y)

proc getchar_unlocked():char {. importc:"getchar_unlocked",header: "<stdio.h>" .}
proc scan(): int =
  while true:
    let k = getchar_unlocked()
    if k < '0': break
    result = 10 * result + k.ord - '0'.ord

type HeapQueue*[T] = object
  ## A heap queue, commonly known as a priority queue.
  data: seq[T]

proc initHeapQueue*[T](): HeapQueue[T] =
  ## Create a new empty heap.
  discard

proc len*[T](heap: HeapQueue[T]): int {.inline.} =
  ## Return the number of elements of `heap`.
  heap.data.len

proc `[]`*[T](heap: HeapQueue[T], i: Natural): T {.inline.} =
  ## Access the i-th element of `heap`.
  heap.data[i]

proc heapCmp[T](x, y: T): bool {.inline.} =
  return (x < y)

proc siftdown[T](heap: var HeapQueue[T], startpos, p: int) =
  ## 'heap' is a heap at all indices >= startpos, except possibly for pos.  pos
  ## is the index of a leaf with a possibly out-of-order value.  Restore the
  ## heap invariant.
  var pos = p
  var newitem = heap[pos]
  # Follow the path to the root, moving parents down until finding a place
  # newitem fits.
  while pos > startpos:
    let parentpos = (pos - 1) shr 1
    let parent = heap[parentpos]
    if heapCmp(newitem, parent):
      heap.data[pos] = parent
      pos = parentpos
    else:
      break
  heap.data[pos] = newitem

proc siftup[T](heap: var HeapQueue[T], p: int) =
  let endpos = len(heap)
  var pos = p
  let startpos = pos
  let newitem = heap[pos]
  # Bubble up the smaller child until hitting a leaf.
  var childpos = 2*pos + 1 # leftmost child position
  while childpos < endpos:
    # Set childpos to index of smaller child.
    let rightpos = childpos + 1
    if rightpos < endpos and not heapCmp(heap[childpos], heap[rightpos]):
      childpos = rightpos
    # Move the smaller child up.
    heap.data[pos] = heap[childpos]
    pos = childpos
    childpos = 2*pos + 1
  # The leaf at pos is empty now.  Put newitem there, and bubble it up
  # to its final resting place (by sifting its parents down).
  heap.data[pos] = newitem
  siftdown(heap, startpos, pos)

proc push*[T](heap: var HeapQueue[T], item: T) =
  ## Push `item` onto heap, maintaining the heap invariant.
  heap.data.add(item)
  siftdown(heap, 0, len(heap)-1)

proc pop*[T](heap: var HeapQueue[T]): T =
  ## Pop and return the smallest item from `heap`,
  ## maintaining the heap invariant.
  let lastelt = heap.data.pop()
  if heap.len > 0:
    result = heap[0]
    heap.data[0] = lastelt
    siftup(heap, 0)
  else:
    result = lastelt


proc solve() : int =
  let n = scan()
  var L = newSeq[int](n)
  for i in 0..<n: L[i] = scan()
  L.sort(cmp)
  var R = @[1]
  for i in 1..<n:
    if L[i-1] == L[i] : R[^1] += 1
    else: R .add 1
  if R.len < 3: return 0
  var q = initHeapQueue[int]()
  for r in R: q.push(-r)
  while true:
    let a = -q.pop() - 1
    let b = -q.pop() - 1
    let c = -q.pop() - 1
    if a < 0 or b < 0 or c < 0 : return
    result += 1
    q.push(-b)
    q.push(-c)
    q.push(-a)

scan().times: echo solve()
0