結果
問題 | No.9 モンスターのレベル上げ |
ユーザー | むらため |
提出日時 | 2019-01-28 06:37:32 |
言語 | Nim (2.0.2) |
結果 |
AC
|
実行時間 | 275 ms / 5,000 ms |
コード長 | 2,263 bytes |
コンパイル時間 | 2,751 ms |
コンパイル使用メモリ | 70,348 KB |
実行使用メモリ | 17,352 KB |
最終ジャッジ日時 | 2023-09-14 03:07:06 |
合計ジャッジ時間 | 5,456 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 243 ms
17,336 KB |
testcase_03 | AC | 113 ms
17,348 KB |
testcase_04 | AC | 103 ms
12,264 KB |
testcase_05 | AC | 74 ms
11,012 KB |
testcase_06 | AC | 24 ms
6,912 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 28 ms
9,116 KB |
testcase_09 | AC | 214 ms
17,320 KB |
testcase_10 | AC | 2 ms
4,380 KB |
testcase_11 | AC | 275 ms
17,320 KB |
testcase_12 | AC | 102 ms
17,316 KB |
testcase_13 | AC | 17 ms
17,352 KB |
testcase_14 | AC | 211 ms
17,312 KB |
testcase_15 | AC | 222 ms
17,320 KB |
testcase_16 | AC | 5 ms
4,376 KB |
testcase_17 | AC | 150 ms
14,344 KB |
testcase_18 | AC | 124 ms
14,336 KB |
testcase_19 | AC | 4 ms
4,380 KB |
ソースコード
import sequtils GC_disableMarkAndSweep() template times*(n:int,body) = (for _ in 0..<n: body) 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 Heap*[T] = object nodes: seq[T] compare: proc(x,y:T):int proc newHeap*[T](compare:proc(x,y:T):int): Heap[T] = Heap[T](nodes:newSeq[T](),compare:compare) proc compareNode[T](h:Heap[T],i,j:int):int = h.compare(h.nodes[i],h.nodes[j]) proc size*[T](h:Heap[T]):int = h.nodes.len() proc items*[T](h:Heap[T]):seq[T] = h.nodes proc top*[T](h:Heap[T]): T = h.nodes[0] proc push*[T](h:var Heap[T],node:T):void = h.nodes.add(node) #末尾に追加 var i = h.nodes.len() - 1 while i > 0: # 末尾から木を整形 let parent = (i - 1) div 2 if h.compare(h.nodes[parent],node) <= 0: break h.nodes[i] = h.nodes[parent] i = parent h.nodes[i] = node proc shiftdown*[T](h:var Heap[T]): void = let size = h.nodes.len() var i = 0 while true : let L = i * 2 + 1 let R = i * 2 + 2 if L >= size : break let child = if R < size and h.compareNode(R,L) <= 0 : R else: L if h.compareNode(i,child) <= 0: break swap(h.nodes[i],h.nodes[child]) i = child proc pop*[T](h:var Heap[T]):T = result = h.nodes[0] # rootと末尾を入れ替えて木を整形 h.nodes[0] = h.nodes[^1] h.nodes.setLen(h.nodes.len() - 1) h.shiftdown() proc replaceTop*[T](h:var Heap[T],node:T):void = h.nodes[0] = node h.shiftdown() let n = scan() # 一番レベルの低い 一番戦ってないものを戦わせる type monster = tuple[lv:int,cnt:int] var myInitialHeap = newHeap( proc (a,b:monster):int = if a.lv == b.lv : a.cnt - b.cnt else: a.lv - b.lv ) n.times: myInitialHeap.push((scan(),0)) let B = newSeqWith(n,scan()) # enemy var res = 1e12.int for i in 0..<n: var myHeap = myInitialHeap var mx = 0 for j in 0..<n: let b = B[(i + j) mod n] var me = myHeap.top() me.lv += b shr 1 # (b div 2)ぶんレベルアップ me.cnt += 1 myHeap.replaceTop(me) if me.cnt > mx : mx = me.cnt if res <= mx: break res .min= mx echo res