#{{{ header {.hints:off warnings:off optimization:speed.} import algorithm, sequtils, tables, macros, math, sets, strutils, strformat, sugar when defined(MYDEBUG): import header import streams proc scanf(formatstr: cstring){.header: "", varargs.} #proc getchar(): char {.header: "", varargs.} proc nextInt(): int = scanf("%lld",addr result) proc nextFloat(): float = scanf("%lf",addr result) proc nextString[F](f:F): string = var get = false result = "" while true: # let c = getchar() let c = f.readChar if c.int > ' '.int: get = true result.add(c) elif get: return proc nextInt[F](f:F): int = parseInt(f.nextString) proc nextFloat[F](f:F): float = parseFloat(f.nextString) proc nextString():string = stdin.nextString() template `max=`*(x,y:typed):void = x = max(x,y) template `min=`*(x,y:typed):void = x = min(x,y) template inf(T): untyped = when T is SomeFloat: T(Inf) elif T is SomeInteger: ((T(1) shl T(sizeof(T)*8-2)) - (T(1) shl T(sizeof(T)*4-1))) else: assert(false) proc discardableId[T](x: T): T {.discardable.} = return x macro `:=`(x, y: untyped): untyped = var strBody = "" if x.kind == nnkPar: for i,xi in x: strBody &= fmt""" {xi.repr} := {y[i].repr} """ else: strBody &= fmt""" when declaredInScope({x.repr}): {x.repr} = {y.repr} else: var {x.repr} = {y.repr} """ strBody &= fmt"discardableId({x.repr})" parseStmt(strBody) proc toStr[T](v:T):string = proc `$`[T](v:seq[T]):string = v.mapIt($it).join(" ") return $v proc print0(x: varargs[string, toStr]; sep:string):string{.discardable.} = result = "" for i,v in x: if i != 0: addSep(result, sep = sep) add(result, v) result.add("\n") stdout.write result var print:proc(x: varargs[string, toStr]) print = proc(x: varargs[string, toStr]) = discard print0(@x, sep = " ") template makeSeq(x:int; init):auto = when init is typedesc: newSeq[init](x) else: newSeqWith(x, init) macro Seq(lens: varargs[int]; init):untyped = var a = fmt"{init.repr}" for i in countdown(lens.len - 1, 0): a = fmt"makeSeq({lens[i].repr}, {a})" parseStmt(a) template makeArray(x; init):auto = when init is typedesc: var v:array[x, init] else: var v:array[x, init.type] for a in v.mitems: a = init v macro Array(lens: varargs[typed], init):untyped = var a = fmt"{init.repr}" for i in countdown(lens.len - 1, 0): a = fmt"makeArray({lens[i].repr}, {a})" parseStmt(a) # }}} # Graph {{{ import sequtils type Edge[T] = object src,dst:int weight:T rev:int Edges[T] = seq[Edge[T]] Graph[T] = seq[seq[Edge[T]]] Matrix[T] = seq[seq[T]] proc initEdge[T](src,dst:int,weight:T,rev:int = -1):Edge[T] = var e:Edge[T] e.src = src e.dst = dst e.weight = weight e.rev = rev return e proc initGraph[T](n:int):Graph[T] = return newSeqWith(n,newSeq[Edge[T]]()) proc addBiEdge[T](g:var Graph[T],e:Edge[T]):void = var e_rev = e swap(e_rev.src, e_rev.dst) let (r, s) = (g[e.src].len, g[e.dst].len) g[e.src].add(e) g[e.dst].add(e_rev) g[e.src][^1].rev = s g[e.dst][^1].rev = r proc addBiEdge[T](g:var Graph[T],src,dst:int,weight:T=1):void = g.addBiEdge(initEdge(src, dst, weight)) proc initUndirectedGraph[T](n:int, a,b,c:seq[T]):Graph[T] = result = initGraph[T](n) for i in 0..