結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2017-06-10 17:39:51 |
言語 | Nim (2.2.0) |
結果 |
AC
|
実行時間 | 95 ms / 2,000 ms |
コード長 | 3,339 bytes |
コンパイル時間 | 3,716 ms |
コンパイル使用メモリ | 73,088 KB |
実行使用メモリ | 23,416 KB |
最終ジャッジ日時 | 2024-06-30 01:19:52 |
合計ジャッジ時間 | 6,279 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 39) Warning: Use the new 'sugar' module instead; future is deprecated [Deprecated]
ソースコード
import strutils, sequtils, algorithm, future, tables, setstypePrirorityQueue*[T] = ref object of RootObjelms: seq[T]idxs: TableRef[T, int]cmp: (T, T) -> intproc newPriorityQueue*[T](cmp: (T, T) -> int): PrirorityQueue[T] =new(result)result.elms = newSeq[T]()result.idxs = newTable[T, int]()result.cmp = cmptemplate parent(cur: int): int =if cur == 0: -1else: (cur - 1) div 2template childl(cur: int): int =cur * 2 + 1template childr(cur: int): int =cur * 2 + 2proc innerDel[T](self: var PrirorityQueue[T], cur: int) =self.idxs.del(self.elms[cur])self.elms.del(cur)proc innerSwap[T](self: var PrirorityQueue[T], s, t: int) =let (sval, tval) = (self.elms[s], self.elms[t])swap(self.elms[s], self.elms[t])swap(self.idxs[sval], self.idxs[tval])proc valid[T](self: PrirorityQueue[T], upper, lower: int): bool =let val = self.cmp(self.elms[upper], self.elms[lower])assert(val != 0)result = val < 0proc valid[T](self: PrirorityQueue[T], cur: int = 0): bool =var (chl, chr) = (childl(cur), childr(cur))result = trueif chl < self.len:result = result and self.valid(cur, chl)result = result and self.valid(chl)if chr < self.len:result = result and self.valid(cur, chr)result = result and self.valid(chr)proc upHeap[T](self: var PrirorityQueue[T], cur: var int) =var par = parent(cur)while par >= 0 and not self.valid(par, cur):self.innerSwap(cur, par)(cur, par) = (par, parent(par))proc downHeap[T](self: var PrirorityQueue[T], cur: var int) =var (chl, chr) = (childl(cur), childr(cur))while chl < self.elms.len:var ch =if chr >= self.elms.len or self.valid(chl, chr): chlelse: chrif self.valid(cur, ch):breakself.innerSwap(cur, ch)(cur, chl, chr) = (ch, childl(ch), childr(ch))proc len*[T](self: PrirorityQueue[T]): int =assert(self.elms.len == self.idxs.len)self.elms.lenproc push*[T](self: var PrirorityQueue[T], data: T): bool {.discardable.} =if self.idxs.contains(data):return falsevarn = self.elms.lencur = nself.elms.setLen(n + 1)self.elms[cur] = dataself.idxs[data] = curself.upHeap(cur)return trueproc peek*[T](self: var PrirorityQueue[T]): T =self.elms[0]proc pop*[T](self: var PrirorityQueue[T]): T {.discardable.} =assert(self.elms.len > 0)varn = self.elms.lencur = 0result = self.elms[0]self.innerSwap(0, n-1)self.innerDel(n-1)self.downHeap(cur)proc del*[T](self: var PrirorityQueue[T], data: T): bool {.discardable.} =if not self.idxs.contains(data):return falselet n = self.elms.lenvar idx = self.idxs[data]if idx == n - 1:self.innerDel(n-1)else:self.innerSwap(idx, n-1)self.innerDel(n-1)self.downHeap(idx)self.upHeap(idx)return true# ==============================================================================when isMainModule:varn = stdin.readLine.parseInta = stdin.readLine.split.map(parseInt)b = newSeq[int](n)lastIdx = newTable[int, int]()pQ = newPriorityQueue[int]((x: int, y: int) => (y.int64 - x.int64).int)for i in 0..<n:lastIdx[a[i]] = ifor i in 0..<n:pQ.push(a[i])b[i] = pQ.peek()if i == lastIdx[a[i]]:pQ.del(a[i])echo b.join(" ")