結果
| 問題 | No.2007 Arbitrary Mod (Easy) |
| ユーザー |
 chaemon
|
| 提出日時 | 2022-07-15 21:42:47 |
| 言語 | Nim (2.0.2) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 36,931 bytes |
| コンパイル時間 | 3,978 ms |
| コンパイル使用メモリ | 94,872 KB |
| 実行使用メモリ | 6,948 KB |
| 最終ジャッジ日時 | 2024-06-27 17:18:39 |
| 合計ジャッジ時間 | 6,494 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,816 KB |
| testcase_01 | AC | 1 ms
6,816 KB |
| testcase_02 | AC | 2 ms
6,940 KB |
| testcase_03 | AC | 2 ms
6,940 KB |
| testcase_04 | AC | 2 ms
6,940 KB |
| testcase_05 | AC | 2 ms
6,944 KB |
| testcase_06 | AC | 1 ms
6,944 KB |
| testcase_07 | AC | 1 ms
6,944 KB |
| testcase_08 | AC | 2 ms
6,940 KB |
| testcase_09 | AC | 2 ms
6,940 KB |
| testcase_10 | AC | 2 ms
6,944 KB |
| testcase_11 | AC | 1 ms
6,944 KB |
| testcase_12 | AC | 1 ms
6,944 KB |
| testcase_13 | AC | 2 ms
6,940 KB |
| testcase_14 | AC | 1 ms
6,940 KB |
| testcase_15 | AC | 2 ms
6,940 KB |
| testcase_16 | AC | 1 ms
6,940 KB |
| testcase_17 | AC | 2 ms
6,944 KB |
| testcase_18 | AC | 1 ms
6,944 KB |
| testcase_19 | AC | 1 ms
6,948 KB |
| testcase_20 | AC | 1 ms
6,940 KB |
| testcase_21 | AC | 2 ms
6,944 KB |
| testcase_22 | AC | 2 ms
6,940 KB |
| testcase_23 | AC | 2 ms
6,944 KB |
| testcase_24 | AC | 1 ms
6,940 KB |
| testcase_25 | AC | 1 ms
6,944 KB |
| testcase_26 | AC | 2 ms
6,940 KB |
| testcase_27 | AC | 1 ms
6,940 KB |
| testcase_28 | AC | 1 ms
6,940 KB |
| testcase_29 | AC | 2 ms
6,940 KB |
| testcase_30 | AC | 2 ms
6,940 KB |
| testcase_31 | AC | 1 ms
6,944 KB |
| testcase_32 | AC | 1 ms
6,940 KB |
コンパイルメッセージ
check is on
ソースコード
import macros
macro Please(x): untyped = nnkStmtList.newTree()
Please use Nim-ACL
Please use Nim-ACL
Please use Nim-ACL
#[ include atcoder/extra/header/chaemon_header ]#
when not declared ATCODER_CHAEMON_HEADER_HPP:
const ATCODER_CHAEMON_HEADER_HPP* = 1
{.hints:off warnings:off assertions:on optimization:speed.}
when declared(DO_CHECK):
when DO_CHECK:
static: echo "check is on"
{.checks:on.}
else:
static: echo "check is off"
{.checks:off.}
else:
static: echo "check is on"
{.checks:on.}
import std/algorithm as algorithm_lib
import std/sequtils as sequtils_lib
import std/macros as macros_lib
import std/math as math_lib
import std/sets as sets_lib
import std/tables as tables_lib
import std/strutils as strutils_lib
import std/strformat as strformat_lib
import std/options as options_lib
import std/bitops as bitops_lib
import std/streams as streams_lib
import std/deques as deques_lib
#[ import atcoder/extra/forward_compatibility/internal_sugar ]#
when not declared ATCODER_INTERNAL_SUGAR_HPP:
const ATCODER_INTERNAL_SUGAR_HPP* = 1
import std/macros
import std/typetraits
proc checkPragma(ex, prag: var NimNode) =
# since (1, 3):
block:
if ex.kind == nnkPragmaExpr:
prag = ex[1]
if ex[0].kind == nnkPar and ex[0].len == 1:
ex = ex[0][0]
else:
ex = ex[0]
proc createProcType(p, b: NimNode): NimNode {.compileTime.} =
result = newNimNode(nnkProcTy)
var
formalParams = newNimNode(nnkFormalParams).add(b)
p = p
prag = newEmptyNode()
checkPragma(p, prag)
case p.kind
of nnkPar, nnkTupleConstr:
for i in 0 ..< p.len:
let ident = p[i]
var identDefs = newNimNode(nnkIdentDefs)
case ident.kind
of nnkExprColonExpr:
identDefs.add ident[0]
identDefs.add ident[1]
else:
identDefs.add newIdentNode("i" & $i)
identDefs.add(ident)
identDefs.add newEmptyNode()
formalParams.add identDefs
else:
var identDefs = newNimNode(nnkIdentDefs)
identDefs.add newIdentNode("i0")
identDefs.add(p)
identDefs.add newEmptyNode()
formalParams.add identDefs
result.add formalParams
result.add prag
macro `=>`*(p, b: untyped): untyped =
## Syntax sugar for anonymous procedures.
## It also supports pragmas.
var
params = @[ident"auto"]
name = newEmptyNode()
kind = nnkLambda
pragma = newEmptyNode()
p = p
checkPragma(p, pragma)
if p.kind == nnkInfix and p[0].kind == nnkIdent and p[0].eqIdent"->":
params[0] = p[2]
p = p[1]
checkPragma(p, pragma) # check again after -> transform
# since (1, 3):
block:
# if p.kind == nnkCall:
if p.kind in {nnkCall, nnkObjConstr}:
# foo(x, y) => x + y
kind = nnkProcDef
name = p[0]
let newP = newNimNode(nnkPar)
for i in 1..<p.len:
newP.add(p[i])
p = newP
case p.kind
of nnkPar, nnkTupleConstr:
var untypedBeforeColon = 0
for i, c in p:
var identDefs = newNimNode(nnkIdentDefs)
case c.kind
of nnkExprColonExpr:
let t = c[1]
# since (1, 3):
block:
# + 1 here because of return type in params
for j in (i - untypedBeforeColon + 1) .. i:
params[j][1] = t
untypedBeforeColon = 0
identDefs.add(c[0])
identDefs.add(t)
identDefs.add(newEmptyNode())
of nnkIdent:
identDefs.add(c)
identDefs.add(newIdentNode("auto"))
identDefs.add(newEmptyNode())
inc untypedBeforeColon
of nnkInfix:
if c[0].kind == nnkIdent and c[0].eqIdent"->":
var procTy = createProcType(c[1], c[2])
params[0] = procTy[0][0]
for i in 1 ..< procTy[0].len:
params.add(procTy[0][i])
else:
error("Expected proc type (->) got (" & c[0].strVal & ").", c)
break
else:
error("Incorrect procedure parameter list.", c)
params.add(identDefs)
of nnkIdent:
var identDefs = newNimNode(nnkIdentDefs)
identDefs.add(p)
identDefs.add(ident"auto")
identDefs.add(newEmptyNode())
params.add(identDefs)
else:
error("Incorrect procedure parameter list.", p)
result = newProc(body = b, params = params,
pragmas = pragma, name = name,
procType = kind)
macro `->`*(p, b: untyped): untyped =
result = createProcType(p, b)
macro dump*(x: untyped): untyped =
let s = x.toStrLit
let r = quote do:
debugEcho `s`, " = ", `x`
return r
# TODO: consider exporting this in macros.nim
proc freshIdentNodes(ast: NimNode): NimNode =
# Replace NimIdent and NimSym by a fresh ident node
# see also https://github.com/nim-lang/Nim/pull/8531#issuecomment-410436458
proc inspect(node: NimNode): NimNode =
case node.kind:
of nnkIdent, nnkSym:
result = ident($node)
of nnkEmpty, nnkLiterals:
result = node
else:
result = node.kind.newTree()
for child in node:
result.add inspect(child)
result = inspect(ast)
macro capture*(locals: varargs[typed], body: untyped): untyped =
var params = @[newIdentNode("auto")]
let locals = if locals.len == 1 and locals[0].kind == nnkBracket: locals[0]
else: locals
for arg in locals:
if arg.strVal == "result":
error("The variable name cannot be `result`!", arg)
params.add(newIdentDefs(ident(arg.strVal), freshIdentNodes getTypeInst arg))
result = newNimNode(nnkCall)
result.add(newProc(newEmptyNode(), params, body, nnkProcDef))
for arg in locals: result.add(arg)
#[ import atcoder/extra/forward_compatibility/internal_underscored_calls ]#
when not declared ATCODER_INTERNAL_UNDERSCORED_CALLS_HPP:
const ATCODER_INTERNAL_UNDERSCORED_CALLS_HPP* = 1
import macros
proc underscoredCall(n, arg0: NimNode): NimNode =
proc underscorePos(n: NimNode): int =
for i in 1 ..< n.len:
if n[i].eqIdent("_"): return i
return 0
if n.kind in nnkCallKinds:
result = copyNimNode(n)
result.add n[0]
let u = underscorePos(n)
for i in 1..u-1: result.add n[i]
result.add arg0
for i in u+1..n.len-1: result.add n[i]
elif n.kind in {nnkAsgn, nnkExprEqExpr}:
var field = n[0]
if n[0].kind == nnkDotExpr and n[0][0].eqIdent("_"):
# handle _.field = ...
field = n[0][1]
result = newDotExpr(arg0, field).newAssignment n[1]
else:
# handle e.g. 'x.dup(sort)'
result = newNimNode(nnkCall, n)
result.add n
result.add arg0
proc underscoredCalls*(result, calls, arg0: NimNode) =
expectKind calls, {nnkArgList, nnkStmtList, nnkStmtListExpr}
for call in calls:
if call.kind in {nnkStmtList, nnkStmtListExpr}:
underscoredCalls(result, call, arg0)
else:
result.add underscoredCall(call, arg0)
discard
macro dup*[T](arg: T, calls: varargs[untyped]): T =
result = newNimNode(nnkStmtListExpr, arg)
let tmp = genSym(nskVar, "dupResult")
result.add newVarStmt(tmp, arg)
underscoredCalls(result, calls, tmp)
result.add tmp
proc transLastStmt(n, res, bracketExpr: NimNode): (NimNode, NimNode, NimNode) =
# Looks for the last statement of the last statement, etc...
case n.kind
of nnkIfExpr, nnkIfStmt, nnkTryStmt, nnkCaseStmt:
result[0] = copyNimTree(n)
result[1] = copyNimTree(n)
result[2] = copyNimTree(n)
for i in ord(n.kind == nnkCaseStmt)..<n.len:
(result[0][i], result[1][^1], result[2][^1]) = transLastStmt(n[i], res, bracketExpr)
of nnkStmtList, nnkStmtListExpr, nnkBlockStmt, nnkBlockExpr, nnkWhileStmt,
nnkForStmt, nnkElifBranch, nnkElse, nnkElifExpr, nnkOfBranch, nnkExceptBranch:
result[0] = copyNimTree(n)
result[1] = copyNimTree(n)
result[2] = copyNimTree(n)
if n.len >= 1:
(result[0][^1], result[1][^1], result[2][^1]) = transLastStmt(n[^1], res, bracketExpr)
of nnkTableConstr:
result[1] = n[0][0]
result[2] = n[0][1]
if bracketExpr.len == 1:
bracketExpr.add([newCall(bindSym"typeof", newEmptyNode()), newCall(
bindSym"typeof", newEmptyNode())])
template adder(res, k, v) = res[k] = v
result[0] = getAst(adder(res, n[0][0], n[0][1]))
of nnkCurly:
result[2] = n[0]
if bracketExpr.len == 1:
bracketExpr.add(newCall(bindSym"typeof", newEmptyNode()))
template adder(res, v) = res.incl(v)
result[0] = getAst(adder(res, n[0]))
else:
result[2] = n
if bracketExpr.len == 1:
bracketExpr.add(newCall(bindSym"typeof", newEmptyNode()))
template adder(res, v) = res.add(v)
result[0] = getAst(adder(res, n))
macro collect*(init, body: untyped): untyped =
# analyse the body, find the deepest expression 'it' and replace it via
# 'result.add it'
let res = genSym(nskVar, "collectResult")
expectKind init, {nnkCall, nnkIdent, nnkSym}
let bracketExpr = newTree(nnkBracketExpr,
if init.kind == nnkCall: init[0] else: init)
let (resBody, keyType, valueType) = transLastStmt(body, res, bracketExpr)
if bracketExpr.len == 3:
bracketExpr[1][1] = keyType
bracketExpr[2][1] = valueType
else:
bracketExpr[1][1] = valueType
let call = newTree(nnkCall, bracketExpr)
if init.kind == nnkCall:
for i in 1 ..< init.len:
call.add init[i]
result = newTree(nnkStmtListExpr, newVarStmt(res, call), resBody, res)
discard
# import std/sugar
#[ import atcoder/extra/other/reader ]#
when not declared ATCODER_READER_HPP:
const ATCODER_READER_HPP* = 1
import streams
import strutils
import sequtils
# proc scanf*(formatstr: cstring){.header: "<stdio.h>", varargs.}
#proc getchar(): char {.header: "<stdio.h>", varargs.}
# proc nextInt*(): int = scanf("%lld",addr result)
# proc nextFloat*(): float = scanf("%lf",addr result)
proc nextString*(f:auto = stdin): string =
var get = false
result = ""
while true:
let c = f.readChar
#doassert c.int != 0
if c.int > ' '.int:
get = true
result.add(c)
elif get: return
proc nextInt*(f:auto = stdin): int = parseInt(f.nextString)
proc nextFloat*(f:auto = stdin): float = parseFloat(f.nextString)
# proc nextString*():string = stdin.nextString()
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 = " ")
discard
#[ import atcoder/extra/other/cfor ]#
when not declared ATCODER_CFOR_HPP:
import std/macros
const ATCODER_CFOR_HPP* = 1
macro For*(preLoop, condition, postLoop, body:untyped):NimNode =
var
preLoop = if preLoop.repr == "()": ident("discard") else: preLoop
condition = if condition.repr == "()": ident("true") else: condition
postLoop = if postLoop.repr == "()": ident("discard") else: postLoop
quote do:
`preLoop`
var start_cfor {.gensym.} = true
while true:
if start_cfor:
start_cfor = false
else:
`postLoop`
if not `condition`:
break
`body`
template cfor*(preLoop, condition, postLoop, body:untyped):NimNode =
For(preLoop, condition, postLoop, body)
discard
#[ import atcoder/extra/other/sliceutils ]#
when not declared ATCODER_SLICEUTILS_HPP:
const ATCODER_SLICEUTILS_HPP* = 1
proc index*[T](a:openArray[T]):Slice[int] =
a.low..a.high
type ReversedSlice[T] = distinct Slice[T]
type StepSlice[T] = object
s:Slice[T]
d:T
proc rev*[T](p:Slice[T]):ReversedSlice[T] = ReversedSlice[T](p)
iterator items*(n:int):int = (for i in 0..<n: yield i)
iterator items*[T](p:ReversedSlice[T]):T =
if Slice[T](p).b >= Slice[T](p).a:
var i = Slice[T](p).b
while true:
yield i
if i == Slice[T](p).a:break
i.dec
proc `>>`*[T](s:Slice[T], d:T):StepSlice[T] =
assert d != 0
StepSlice[T](s:s, d:d)
proc `<<`*[T](s:Slice[T], d:T):StepSlice[T] =
assert d != 0
StepSlice[T](s:s, d: -d)
proc low*[T](s:StepSlice[T]):T = s.s.a
proc high*[T](s:StepSlice[T]):T =
let p = s.s.b - s.s.a
if p < 0: return s.low - 1
let d = abs(s.d)
return s.s.a + (p div d) * d
iterator items*[T](p:StepSlice[T]):T =
assert p.d != 0
if p.s.a <= p.s.b:
if p.d > 0:
var i = p.low
let h = p.high
while i <= h:
yield i
if i == h: break
i += p.d
else:
var i = p.high
let l = p.low
while i >= l:
yield i
if i == l: break
i += p.d
proc `[]`*[T:SomeInteger, U](a:openArray[U], s:Slice[T]):seq[U] =
for i in s:result.add(a[i])
proc `[]=`*[T:SomeInteger, U](a:var openArray[U], s:StepSlice[T], b:openArray[U]) =
var j = 0
for i in s:
a[i] = b[j]
j.inc
discard
#[ import atcoder/extra/other/assignment_operator ]#
when not declared ATCODER_ASSIGNMENT_OPERATOR_HPP:
import std/macros
import std/strformat
const ATCODER_ASSIGNMENT_OPERATOR_HPP* = 1
proc `max=`*[S, T](a: var S, b: T):bool {.discardable.} =
return if a < b: a = b; true else: false
proc `min=`*[S, T](a: var S, b: T):bool {.discardable.} =
return if a > b: a = b; true else: false
template `>?=`*(x,y:typed):bool = x.max= y
template `<?=`*(x,y:typed):bool = x.min= y
proc `//`*[T:SomeInteger](x,y:T):T = x div y
proc `%`*[T:SomeInteger](x,y:T):T = x mod y
macro generateAssignmentOperator*(ops:varargs[untyped]) =
var strBody = ""
for op in ops:
let op = op.repr
var op_raw = op
if op_raw[0] == '`':
op_raw = op_raw[1..^2]
strBody &= fmt"""proc `{op_raw}=`*[S, T](a:var S, b:T):auto {{.inline discardable.}} = (mixin {op};a = `{op_raw}`(a, b);return a){'\n'}"""
parseStmt(strBody)
generateAssignmentOperator(`mod`, `div`, `and`, `or`, `xor`, `shr`, `shl`, `<<`, `>>`, `%`, `//`, `&`, `|`, `^`)
discard
#[ import atcoder/extra/other/inf ]#
when not declared ATCODER_INF_HPP:
const ATCODER_INF_HPP* = 1
import sequtils
template inf*(T:typedesc): untyped =
when T is SomeFloat: T(Inf)
elif T is SomeInteger: T.high div 2
else:
static: assert(false)
template infRepr*[T](x:T):string =
when T is seq or T is array:
"@[" & x.mapIt(it.infRepr).join(", ") & "]"
elif x is SomeInteger or x is SomeFloat:
if x >= T.inf: "inf"
elif x <= -T.inf: "-inf"
else: $x
else:
$x
proc `∞`*(T:typedesc):T = T.inf
proc `*!`*[T:SomeInteger](a, b:T):T =
if a == T(0) or b == T(0): return T(0)
var sgn = T(1)
if a < T(0): sgn = -sgn
if b < T(0): sgn = -sgn
let a = abs(a)
let b = abs(b)
if b > T.inf div a: result = T.inf
else: result = min(T.inf, a * b)
result *= sgn
proc `+!`*[T:SomeInteger](a, b:T):T =
result = a + b
result = min(T.inf, result)
result = max(-T.inf, result)
proc `-!`*[T:SomeInteger](a, b:T):T =
result = a - b
result = min(T.inf, result)
result = max(-T.inf, result)
discard
#[ import atcoder/extra/other/warlus_operator ]#
when not declared ATCODER_CHAEMON_WARLUS_OPERATOR_HPP:
const ATCODER_CHAEMON_WARLUS_OPERATOR_HPP* = 1
import macros
proc discardableId*[T](x: T): T {.discardable.} = x
proc warlusImpl(x, y:NimNode):NimNode =
return quote do:
when declaredInScope(`x`):
`x` = `y`
else:
var `x` = `y`
macro `:=`*(x, y: untyped): untyped =
result = newStmtList()
if x.kind == nnkCurly:
for i,xi in x: result.add warlusImpl(xi, y)
elif x.kind == nnkPar:
for i,xi in x: result.add warlusImpl(xi, y[i])
else:
result.add warlusImpl(x, y)
result.add quote do:
discardableId(`x`)
discard
#[ import atcoder/extra/other/seq_array_utils ]#
when not declared ATCODER_SEQ_ARRAY_UTILS:
const ATCODER_SEQ_ARRAY_UTILS* = 1
import std/strformat
import std/macros
type SeqType = object
type ArrayType = object
let
Seq* = SeqType()
Array* = ArrayType()
template fill*[T](a:var T, init:untyped) =
when T is init.type:
a = init
else:
for x in a.mitems: fill(x, init)
template makeSeq*(x:int; init):auto =
when init is typedesc: newSeq[init](x)
else:
var a = newSeq[typeof(init, typeofProc)](x)
a.fill(init)
a
template makeArray*(x:int or Slice[int]; init):auto =
var v:array[x, init.type]
v
macro `[]`*(x:ArrayType or SeqType, args:varargs[untyped]):auto =
var a:string
if $x == "Seq" and args.len == 1 and args[0].kind != nnkExprColonExpr:
a = fmt"newSeq[{args[0].repr}]()"
else:
let tail = args[^1]
assert tail.kind == nnkExprColonExpr, "Wrong format of tail"
let
args = args[0 .. ^2] & tail[0]
init = tail[1]
a = fmt"{init.repr}"
if $x == "Array":
for i in countdown(args.len - 1, 0): a = fmt"makeArray({args[i].repr}, {a})"
a = fmt"{'\n'}block:{'\n'} var a = {a}{'\n'} when {init.repr} isnot typedesc:{'\n'} a.fill({init.repr}){'\n'} a"
elif $x == "Seq":
for i in countdown(args.len - 1, 0): a = fmt"makeSeq({args[i].repr}, {a})"
a = fmt"{'\n'}block:{'\n'} {a}"
else:
assert(false)
parseStmt(a)
discard
#[ include atcoder/extra/other/debug ]#
when not declared ATCODER_DEBUG_HPP:
const ATCODER_DEBUG_HPP* = 1
import macros
import strformat
import terminal
#[ import atcoder/extra/other/inf ]#
macro debugImpl*(n:varargs[untyped]): untyped =
# var a = "stderr.write "
var a = ""
# a.add "setForegroundColor fgYellow\n"
# a.add "stdout.write "
# a.add "stderr.write "
a.add "styledWriteLine stderr, fgYellow, "
for i,x in n:
if x.kind == nnkStrLit:
a &= fmt"{x.repr} "
else:
a &= fmt""" "{x.repr} = ", {x.repr}.infRepr """
if i < n.len - 1:
a.add(""", ", ",""")
# a.add(", \"\\n\"")
a.add "\n"
# a.add "resetAttributes()"
parseStmt(a)
template debug*(n: varargs[untyped]): untyped =
const EVAL =
when declared DEBUG: DEBUG
else: false
when EVAL:
debugImpl(n)
discard
#[ import atcoder/extra/other/reference ]#
when not declared ATCODER_REFERENCE_HPP:
const ATCODER_REFERENCE_HPP* = 1
import std/macros
import std/strformat
template byaddr*(lhs, typ, ex) =
when typ is typeof(nil):
let tmp = addr(ex)
else:
let tmp: ptr typ = addr(ex)
template lhs: untyped = tmp[]
macro `=&`*(lhs, rhs:untyped) =
parseStmt(fmt"""byaddr({lhs.repr}, {rhs.repr}.type, {rhs.repr})""")
discard
#[ import atcoder/extra/other/floatutils ]#
when not declared ATCODER_FLOAT_UTILS_HPP:
const ATCODER_FLOAT_UTILS_HPP* = 1
import std/math as math_lib_floatutils
import std/strutils
#[ import atcoder/element_concepts ]#
when not declared ATCODER_ELEMENT_CONCEPTS_HPP:
const ATCODER_ELEMENT_CONCEPTS_HPP* = 1
proc inv*[T:SomeFloat](a:T):auto = T(1) / a
proc init*(self:typedesc[SomeFloat], a:SomeNumber):auto = self(a)
type AdditiveGroupElem* = concept x, y, type T
x + y
x - y
-x
T(0)
type MultiplicativeGroupElem* = concept x, y, type T
x * y
x / y
# x.inv()
T(1)
type RingElem* = concept x, y, type T
x + y
x - y
-x
x * y
T(0)
T(1)
type FieldElem* = concept x, y, type T
x + y
x - y
x * y
x / y
-x
# x.inv()
T(0)
T(1)
type FiniteFieldElem* = concept x, type T
T is FieldElem
T.mod
T.mod() is int
x.pow(1000000)
type hasInf* = concept x, type T
T(Inf)
discard
#[ import atcoder/extra/other/static_var ]#
when not declared ATCODER_STATIC_VAR_HPP:
const ATCODER_STATIC_VAR_HPP* = 1
import std/macros
import std/strformat
macro staticVar*(T:typedesc, body: untyped) =
var s = ""
for n in body:
let name = n[0]
let t = n[1]
let t2 = fmt"{t.repr[1..<t.repr.len]}"
s &= fmt"""{'\n'}proc get_global_addr_of_{name.repr}*[U:{T.repr}](self:typedesc[U] or U):ptr[{t2}] ={'\n'} when self is typedesc:{'\n'} var a {{.global.}}:{t2}.type{'\n'} a.addr{'\n'} else:{'\n'} get_global_addr_of_{name.repr}(self.type){'\n'}
"""
parseStmt(s)
macro `$.`*(t, name:untyped):untyped =
let s = fmt"{t.repr}.get_global_addr_of_{name.repr}()[]"
parseStmt(s)
discard
proc getParameters*(Real:typedesc):ptr[tuple[n:int, pi, eps, inf:Real]] =
var p {.global.}:tuple[n:int, pi, eps, inf:Real]
return p.addr
converter floatConverter*(a:SomeInteger):float = a.float
converter float64Converter*(a:SomeInteger):float64 = a.float64
converter float32Converter*(a:SomeInteger):float32 = a.float32
converter floatConverter*(a:string):float = a.parseFloat
converter float64Converter*(a:string):float64 = a.parseFloat.float64
converter float32Converter*(a:string):float32 = a.parseFloat.float32
staticVar FieldElem:
pi:U.type
eps:U.type
inf:U.type
proc getPi*(Real:typedesc):Real = Real.getParameters()[].pi
proc getEPS*(Real:typedesc):Real = Real.getParameters()[].eps
proc getINF*(Real:typedesc):Real = Real.getParameters()[].inf
proc setEPS*(Real:typedesc, x:Real) = Real.getParameters()[].eps = x
proc valid_range*[Real](l, r:Real):bool =
# assert(l <= r)
var (l, r) = (l, r)
if l > r: swap(l, r)
let d = r - l
let eps = Real$.eps
if d < eps: return true
if l <= Real(0) and Real(0) <= r: return false
return d < eps * min(abs(l), abs(r))
template initPrec*(Real:typedesc) =
Real$.pi = PI.Real
Real$.inf = Inf.Real
when Real is float or Real is float64:
Real$.eps = 1e-9.Real
elif Real is float32:
Real$.eps = 1e-9.Real
# float comp
# TODO: relative error
proc `=~`*(a,b:Real):bool = abs(a - b) < Real$.eps
proc `!=~`*(a,b:Real):bool = abs(a - b) > Real$.eps
proc `<~`*(a,b:Real):bool = a + Real$.eps < b
proc `>~`*(a,b:Real):bool = a > b + Real$.eps
proc `<=~`*(a,b:Real):bool = a < b + Real$.eps
proc `>=~`*(a,b:Real):bool = a + Real$.eps > b
# for OMC
proc estimateRational*[Real](x:Real, n:int) =
var m = Real$.inf
var q = 1
while q <= n:
let p = round(x * q.Real)
let d = abs(p / q.Real - x)
if d < m:
m = d
echo "found: ", p, "/", q, " ", "error: ", d
q.inc
return
float.initPrec()
# float64.initPrec()
float32.initPrec()
discard
#[ import atcoder/extra/other/zip ]#
when not declared ATCODER_ZIP_HPP:
const ATCODER_ZIP_HPP* = 1
import macros
macro zip*(v:varargs[untyped]):untyped =
result = newStmtList()
var par = newPar()
for i,a in v:
var ts = newNimNode(nnkTypeSection)
par.add(ident("T" & $i))
ts.add(newNimNode(nnkTypeDef).add(
ident("T" & $i),
newEmptyNode(),
newDotExpr(newNimNode(nnkBracketExpr).add(a, newIntLitNode(0)), ident("type"))
))
result.add ts
var varSection = newNimNode(nnkVarSection)
varSection.add newIdentDefs(ident("a"), newEmptyNode(), newCall(
newNimNode(nnkBracketExpr).add(
ident("newSeq"),
par
),
ident("n")
))
result.add newNimNode(nnkLetSection).add(newIdentDefs(ident("n"), newEmptyNode(),
newDotExpr(v[0] , ident("len"))
))
result.add(varSection)
var forStmt = newNimNode(nnkForStmt).add(ident("i")).add(
newNimNode(nnkInfix).add(ident("..<")).add(newIntLitNode(0), ident("n"))
)
var fs = newStmtList()
for j,a in v:
fs.add newAssignment(
newNimNode(nnkBracketExpr).add(
newNimNode(nnkBracketExpr).add(
ident("a"),
ident("i")
),
newIntLitNode(j)),
newNimNode(nnkBracketExpr).add(
a,
ident("i")
)
)
forStmt.add fs
result.add(forStmt)
result.add(ident("a"))
result = newBlockStmt(newEmptyNode(), result)
macro unzip*(n:int, p:tuple):untyped =
result = newStmtList()
result.add(newNimNode(nnkLetSection).add(newIdentDefs(ident("n"), newEmptyNode(), n)))
for i,a in p:
var a = newPar(a)
var t = newCall(
newNimNode(nnkBracketExpr).add(
ident("newSeq"),
newDotExpr(a, ident("type"))
),
ident("n")
)
var varSection = newNimNode(nnkVarSection).add(
newIdentDefs(ident("a" & $i), newEmptyNode(), t),
)
result.add(varSection)
var forStmt = newNimNode(nnkForStmt).add(ident("i"))
var rangeDef = newNimNode(nnkInfix).add(ident("..<")).add(newIntLitNode(0), ident("n"))
forStmt.add(rangeDef)
var fs = newStmtList()
for i,a in p:
fs.add newAssignment(
newNimNode(nnkBracketExpr).add(
ident("a" & $i),
ident("i")),
a
)
forStmt.add fs
result.add(forStmt)
var par = newPar()
for i, a in p:
par.add(ident("a" & $i))
result.add(par)
result = newBlockStmt(newEmptyNode(), result)
discard
#[ import atcoder/extra/other/solve_proc ]#
when not declared ATCODER_SOLVEPROC_HPP:
const ATCODER_SOLVEPROC_HPP* = 1
import std/macros
import std/strformat
import std/algorithm
import std/sequtils
import std/streams
import std/strutils
import math
proc compare_answer_string*(s, t:string, error:float = NaN):bool =
if error.classify == fcNaN:
return s == t
else:
var
s = s.split("\n")
t = t.split("\n")
if s.len != t.len: return false
for i in 0 ..< s.len:
var s = s[i].split()
var t = t[i].split()
if s.len != t.len: return false
for j in 0 ..< s.len:
if s[j].len == 0:
if t[j].len != 0: return false
elif t[j].len == 0:
return false
else:
var fs = s[j].parseFloat
var ft = t[j].parseFloat
if abs(fs - ft) > error and abs(fs - ft) > min(abs(ft), abs(fs)) * error: return false
return true
doAssert false
proc mainBodyHeader():NimNode =
# let macro_def = "(for s in {x.repr}: (result &= $s;(when output_stdout: stdout.write $s)));(result &= \"\\n\";when output_stdout: stdout.write \"\\n\")"
result = newStmtList()
result.add quote("@@") do:
mixin echo
result = ""
var resultPointer = result.addr
proc echo(x:varargs[string, `$`]) =
for s in x:
resultPointer[] &= $s
when output_stdout: stdout.write $s
resultPointer[] &= "\n"
when output_stdout: stdout.write "\n"
macro solveProc*(head, body:untyped):untyped =
var prev_type:NimNode
var params:seq[NimNode]
for i in countdown(head.len - 1, 1):
var identDefs = newNimNode(nnkIdentDefs)
if head[i].kind == nnkExprColonExpr:
identDefs.add(head[i][0])
prev_type = head[i][1]
elif head[i].kind == nnkIdent:
identDefs.add(head[i])
identDefs.add(prev_type)
identDefs.add(newEmptyNode())
params.add(identDefs)
params.add(ident"auto")
params.reverse()
var callparams:seq[NimNode]
for i in 1..<params.len:
callparams.add(params[i][0])
# var mainBody, naiveBody = mainBodyHeader()
var mainBody, checkBody, naiveBody, testBody, generateBody = newStmtList()
var hasNaive, hasCheck, hasTest, hasGenerate = false
for b in body:
if b.kind == nnkCall:
if b[0] == ident"Check":
hasCheck = true
var checkStmt = if b.len == 2: b[1] else: b[2]
var strmName = if b.len == 2: ident("strm") else: b[1]
checkBody.add(newNimNode(nnkWhenStmt).add(
newNimNode(nnkElifBranch).add(ident"DO_CHECK").add(
newBlockStmt(newEmptyNode(),
newStmtList().add(
quote do:
var `strmName` = newStringStream(resultOutput)
).add(checkStmt)
))))
elif b[0] == ident"Naive":
hasNaive = true
naiveBody.add b[1]
elif b[0] == ident"Test":
hasTest = true
testBody.add b[1]
elif b[0] == ident"Generate":
hasGenerate = true
generateBody.add b[1]
else:
mainBody.add b
else:
mainBody.add b
mainBody = newStmtList().add(mainBodyHeader()).add(mainBody)
#if hasCheck:
# mainBody.add(checkBody)
result = newStmtList()
let procName = head[0]
var discardablePragma = newNimNode(nnkPragma).add(ident("discardable"))
var mainParams = params
mainParams[0] = ident"string"
# var identDefsSub = newNimNode(nnkIdentDefs).add(ident"output_stdout").add(newNimNode(nnkBracketExpr).add(ident"static").add(ident"bool")).add(ident"true")
var identDefs = newNimNode(nnkIdentDefs).add(ident"output_stdout").add(newNimNode(nnkBracketExpr).add(ident"static").add(ident"bool")).add(ident"true")
proc copy(a:seq[NimNode]):seq[NimNode] = a.mapIt(it.copy)
# var identDefs = newNimNode(nnkIdentDefs).add(ident"output_stdout").add(newNimNode(nnkBracketExpr).add(ident"static").add(ident"bool")).add(newEmptyNode())
mainParams.add(identDefs)
#var mainProcDef = newNimNode(nnkProcDef).add(ident"solve").add(newEmptyNode()).add(newEmptyNode()).add(newNimNode(nnkFormalParams).add(mainParams.copy())).add(discardablePragma).add(newEmptyNode()).add(newEmptyNode())
#result.add(mainProcDef)
if hasCheck:
result.add(quote do:
type CheckResult {.inject.} = ref object of Exception
output, err:string
template check(b:untyped) =
if not b:
raise CheckResult(err: b.astToStr, output: resultOutput)
)
if hasNaive:
var naiveProcDef = newNimNode(nnkProcDef).add(ident"solve_naive").add(newEmptyNode()).add(newEmptyNode()).add(newNimNode(nnkFormalParams).add(mainParams.copy())).add(discardablePragma).add(newEmptyNode()).add(newEmptyNode())
result.add(naiveProcDef)
var naiveParams = mainParams.copy()
#result.add newProc(name = ident(procName), params = mainParams.copy(), body = mainBody, pragmas = discardablePragma)
var mainProcImpl =
newStmtList().add(parseStmt("mixin echo")).add quote do:
proc solve():string =
`mainBody`
var resultOutput {.inject.} = solve()
var mainTemplateBody = newStmtList().add quote do:
`mainProcImpl`
if hasCheck:
mainTemplateBody.add checkBody
mainTemplateBody.add quote do:
resultOutput
var mainTemplate = quote do:
proc `procName`():string {.discardable.} =
`mainTemplateBody`
mainTemplate[3].add mainParams[1..^1].copy()
result.add mainTemplate
if hasNaive:
let naiveProcName = $procName & "naive"
naiveBody = mainBodyHeader().add(newBlockStmt(newEmptyNode(), naiveBody))
result.add newProc(name = ident(naiveProcName), params = naiveParams, body = naiveBody, pragmas = discardablePragma)
var test_body = newStmtList()
var var_names = newSeq[string]()
for procName in [$procName, $procName & "_naive"]:
let var_name = "v" & procName
var_names.add(var_name)
var l = newNimNode(nnkCall).add(ident(procName))
for c in callparams: l.add(c)
l.add(ident"false")
test_body.add(
newNimNode(nnkLetSection).add(
newNimNode(nnkIdentDefs).add(ident(var_name)).add(newEmptyNode()).add(l)
))
var test_params = params
var vars = ""
for i in 1..<params.len:
let p = params[i][0]
vars &= &" {p.repr} = {{{p.repr}}}\\n"
test_params[0] = ident"bool"
var identDefs = newNimNode(nnkIdentDefs).add(ident"error").add(ident"float").add(ident("NaN"))
test_params.add identDefs
test_body.add parseStmt(&"if not compare_answer_string(vsolve, vsolve_naive, error): echo &\"test failed for\\n{vars}\", \"[solve]\\n\", vsolve, \"[solve_naive]\\n\", vsolve_naive;doAssert false")
result.add newProc(name = ident"test", params = test_params, body = test_body, pragmas = discardablePragma)
elif hasCheck:
var test_body_sub = newStmtList()
var var_names = newSeq[string]()
for procName in [$procName]:
let var_name = "v" & procName
var_names.add(var_name)
var l = newNimNode(nnkCall).add(ident(procName))
for c in callparams: l.add(c)
l.add(ident"false")
test_body_sub.add(
newNimNode(nnkLetSection).add(
newNimNode(nnkIdentDefs).add(ident(var_name)).add(newEmptyNode()).add(l)
))
var test_params = params
var vars = ""
for i in 1..<params.len:
let p = params[i][0]
vars &= &" {p.repr} = {{{p.repr}}}\\n"
test_params[0] = ident"bool"
var test_body = newStmtList()
var d = &"try:\n {test_body_sub.repr.strip}\nexcept CheckResult as e:\n echo &\"check failed for\\n{vars}\", \"[failed statement]\\n\", e.err.strip, \"\\n[output]\\n\", e.output;doAssert false"
test_body.add parseStmt(d)
result.add newProc(name = ident"test", params = test_params, body = test_body, pragmas = discardablePragma)
if hasGenerate:
discard
if hasTest:
discard
discard
when declared USE_DEFAULT_TABLE:
when USE_DEFAULT_TABLE:
proc `[]`[A, B](self: var Table[A, B], key: A): var B =
discard self.hasKeyOrPut(key, B.default)
tables_lib.`[]`(self, key)
# converter toBool[T:ref object](x:T):bool = x != nil
# converter toBool[T](x:T):bool = x != T(0)
# misc
proc `<`[T](a, b:seq[T]):bool =
for i in 0 ..< min(a.len, b.len):
if a[i] < b[i]: return true
elif a[i] > b[i]: return false
if a.len < b.len: return true
else: return false
proc ceilDiv*[T:SomeInteger](a, b:T):T =
assert b != 0
if b < 0: return ceilDiv(-a, -b)
result = a.floorDiv(b)
if a mod b != 0: result.inc
template `/^`*[T:SomeInteger](a, b:T):T = ceilDiv(a, b)
discard
block:
var
a, n = nextInt()
x = 1
for i in 0 ..< n:
x *= a
if x in 10^7 .. 10^18:
echo x
echo 0
break
echo 10^18
echo x