#861371 (Nim) No.2277 Honest or Dishonest ?

提出ソース

結果

問題	No.2277 Honest or Dishonest ?
ユーザー	Daylight
提出日時	2023-04-21 21:55:05
言語	Nim (2.0.2)
結果	AC
実行時間	96 ms / 2,000 ms
コード長	17,179 bytes
コンパイル時間	6,629 ms
コンパイル使用メモリ	78,208 KB
実行使用メモリ	9,984 KB
最終ジャッジ日時	2024-11-08 06:30:48
合計ジャッジ時間	10,827 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	1 ms 5,248 KB
testcase_02	AC	1 ms 5,248 KB
testcase_03	AC	75 ms 6,912 KB
testcase_04	AC	77 ms 9,088 KB
testcase_05	AC	31 ms 8,704 KB
testcase_06	AC	66 ms 5,376 KB
testcase_07	AC	52 ms 5,888 KB
testcase_08	AC	28 ms 9,344 KB
testcase_09	AC	51 ms 8,064 KB
testcase_10	AC	40 ms 5,248 KB
testcase_11	AC	19 ms 5,248 KB
testcase_12	AC	38 ms 5,248 KB
testcase_13	AC	73 ms 5,888 KB
testcase_14	AC	51 ms 5,248 KB
testcase_15	AC	26 ms 7,552 KB
testcase_16	AC	52 ms 5,760 KB
testcase_17	AC	27 ms 5,248 KB
testcase_18	AC	74 ms 9,088 KB
testcase_19	AC	77 ms 8,960 KB
testcase_20	AC	60 ms 7,296 KB
testcase_21	AC	56 ms 5,248 KB
testcase_22	AC	51 ms 6,784 KB
testcase_23	AC	74 ms 5,248 KB
testcase_24	AC	46 ms 6,784 KB
testcase_25	AC	58 ms 9,216 KB
testcase_26	AC	20 ms 9,088 KB
testcase_27	AC	36 ms 5,248 KB
testcase_28	AC	28 ms 7,040 KB
testcase_29	AC	43 ms 8,192 KB
testcase_30	AC	34 ms 5,248 KB
testcase_31	AC	55 ms 5,248 KB
testcase_32	AC	38 ms 8,064 KB
testcase_33	AC	76 ms 8,576 KB
testcase_34	AC	79 ms 5,248 KB
testcase_35	AC	12 ms 6,656 KB
testcase_36	AC	47 ms 5,248 KB
testcase_37	AC	75 ms 5,248 KB
testcase_38	AC	18 ms 5,248 KB
testcase_39	AC	25 ms 5,248 KB
testcase_40	AC	11 ms 5,632 KB
testcase_41	AC	80 ms 5,248 KB
testcase_42	AC	56 ms 5,248 KB
testcase_43	AC	82 ms 5,248 KB
testcase_44	AC	95 ms 9,856 KB
testcase_45	AC	93 ms 9,984 KB
testcase_46	AC	90 ms 9,984 KB
testcase_47	AC	96 ms 9,984 KB
testcase_48	AC	94 ms 9,984 KB
testcase_49	AC	82 ms 5,248 KB
testcase_50	AC	81 ms 5,376 KB
testcase_51	AC	83 ms 5,376 KB
testcase_52	AC	83 ms 5,376 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

/home/judge/data/code/Main.nim(25, 12) Warning: imported and not used: 'sugar' [UnusedImport]

ソースコード

raw source code

import macros
macro Please(x): untyped = nnkStmtList.newTree()

Please use Nim-ACL
Please use Nim-ACL
Please use Nim-ACL



#[ include daylight/base ]#
when not declared DAYLIGHT_BASE_HPP:
    const DAYLIGHT_BASE_HPP* = 1
    import system
    import macros
    import algorithm
    import tables
    import sets
    import lists
    import intsets
    import critbits
    import sequtils
    import strutils
    import std/math
    import strformat
    import sugar
    let readToken* = iterator(oneChar: bool = false): string {.closure.}= 
        while true:
            var line = stdin.readLine.split
            for s in line:
                if oneChar:
                    for i in 0..<s.len():
                        yield s[i..i]
                else:
                    yield s
    proc read*(t: typedesc[string]): string = 
        result = readToken()
        while result == "":
            result = readToken()
    proc read*(t: typedesc[int]): int = read(string).parseInt
    proc read*(t: typedesc[float]): float = read(string).parseFloat
    proc read*(t: typedesc[char]): char = readToken(true)[0]

    macro readSeq*(t: typedesc, n: varargs[int]): untyped =
        var repStr = ""
        for arg in n:
            repStr &= &"({arg.repr}).newSeqWith "
        parseExpr(&"{repStr}read({t})")
    
    macro read*(ts: varargs[auto]): untyped=
        var tupStr = ""
        for t in ts:
            tupStr &= &"read({t.repr}),"
        parseExpr(&"({tupStr})")
        
    macro readTupleSeq*(n: int, ts:varargs[auto]): untyped=
        for typ in ts:
            if typ.typeKind != ntyAnything:
                error("Expected typedesc, got " & typ.repr, typ)
        parseExpr(&"({n.repr}).newSeqWith read({ts.repr})")
        
    macro initSeq*(t: typedesc, n: varargs[int]): untyped =
        var repStr = ""
        for i, arg in n:
            if i == n.len - 1:
                repStr &= &"newSeq[{t}]({arg.repr}) "
            else:
                repStr &= &"({arg.repr}).newSeqWith "
        parseExpr(repStr)
    
    
    proc `-`*(a,b: char): int = ord(a) - ord(b)
    proc `+`*(a: char,b: int): char = char(ord(a) + b)
    proc `-`*(a: char,b: int): char = char(ord(a) - b)
    proc `++`*(a: var int) = a += 1
    proc `--`*(a: var int) = a += 1

    proc chmin*[T](a: var T, b: T): bool {.discardable.} =
        if a > b:
            a = b
            return true
        return false
    
    proc chmax*[T](a: var T, b: T): bool {.discardable.} =
        if a < b:
            a = b
            return true
        return false
    const INF* = (1e9+100).int
    const LINF* = (4e18 + 100).int
    discard
#[ import atcoder/dsu ]#
when not declared ATCODER_DSU_HPP:
    const ATCODER_DSU_HPP* = 1

    import std/sequtils

    type
        DSU* = ref object
            n: int
            par_or_siz: seq[int]

    proc initDSU*(n: int): DSU {.inline.} =
        return DSU(n: n, par_or_siz: newSeqWith(n, -1))

    proc leader*(self: DSU; a: int): int {.inline.} =
        if self.par_or_siz[a] < 0: return a
        self.par_or_siz[a] = self.leader(self.par_or_siz[a])
        return self.par_or_siz[a]

    proc same*(self: DSU; a, b: int): bool {.inline.} =
        self.leader(a) == self.leader(b)

    proc size*(self: DSU; a: int): int {.inline.} =
        - self.par_or_siz[self.leader(a)]

    proc merge*(self: DSU; a, b: int): int {.inline, discardable.} =

        var
            x = self.leader(a)
            y = self.leader(b)

        if x == y: return x
        if self.par_or_siz[x] > self.par_or_siz[y]: swap(x, y)
        self.par_or_siz[x] += self.par_or_siz[y]
        self.par_or_siz[y] = x
        return x

    proc groups*(self: DSU): seq[seq[int]] {.inline.} =
        var
            leaderBuf = newSeq[int](self.n)
            groupsize = newSeq[int](self.n)
        for i in 0 ..< self.n:
            leaderBuf[i] = self.leader(i)
            groupsize[leaderBuf[i]].inc
        result = (0 ..< self.n).mapIt(newSeqOfCap[int](groupsize[it]))
        for i, ldr in leaderBuf:
            result[ldr].add i
        result.keepItIf(it.len > 0)
    discard
#[ import atcoder/modint ]#
when not declared ATCODER_MODINT_HPP:
    const ATCODER_MODINT_HPP* = 1
    import std/macros
    #[ import atcoder/generate_definitions ]#
    when not declared ATCODER_GENERATE_DEFINITIONS_NIM:
        const ATCODER_GENERATE_DEFINITIONS_NIM* = 1
        import std/macros
    
        type hasInv* = concept x
            x.inv()
    
        template generateDefinitions*(name, l, r, typeObj, typeBase, body: untyped): untyped {.dirty.} =
            proc name*(l, r: typeObj): auto {.inline.} =
                type T = l.type
                body
            proc name*(l: typeBase; r: typeObj): auto {.inline.} =
                type T = r.type
                body
            proc name*(l: typeObj; r: typeBase): auto {.inline.} =
                type T = l.type
                body
    
        template generatePow*(name) {.dirty.} =
            proc pow*(m: name; p: SomeInteger): name {.inline.} =
                when name is hasInv:
                    if p < 0: return pow(m.inv(), -p)
                else:
                    doAssert p >= 0
                if (p.type)(0) <= p:
                    var
                        p = p.uint
                        m = m
                    result = m.unit()
                    while p > 0'u:
                        if (p and 1'u) != 0'u: result *= m
                        m *= m
                        p = p shr 1'u
            proc `^`*[T:name](m: T; p: SomeInteger): T {.inline.} = m.pow(p)
    
        macro generateConverter*(name, from_type, to_type) =
            let fname = ident("to" & $`name` & "OfGenerateConverter")
            quote do:
                type `name`* = `to_type`
                converter `fname`*(a:`from_type`):`name` {.used.} =
                    `name`.init(a)
        discard

    type
        StaticModInt*[M: static[int]] = object
            a:uint32
        DynamicModInt*[T: static[int]] = object
            a:uint32

    type ModInt* = StaticModInt or DynamicModInt

    proc isStaticModInt*(T:typedesc[ModInt]):bool = T is StaticModInt
    proc isDynamicModInt*(T:typedesc[ModInt]):bool = T is DynamicModInt
    proc isStatic*(T:typedesc[ModInt]):bool = T is StaticModInt

    #[ import atcoder/internal_math ]#
    when not declared ATCODER_INTERNAL_MATH_HPP:
        const ATCODER_INTERNAL_MATH_HPP* = 1
        import std/math
    
        type Barrett* = object
            m*, im*:uint
    
        proc initBarrett*(m:uint):auto = Barrett(m:m, im:cast[uint](-1) div m + 1)
    
        proc umod*(self: Barrett):uint =
            self.m
    
        {.emit: """
    inline unsigned long long calc_mul(const unsigned long long &a, const unsigned long long &b){
        return (unsigned long long)(((unsigned __int128)(a)*b) >> 64);
    }
    """.}
        proc calc_mul*(a,b:culonglong):culonglong {.importcpp: "calc_mul(#,#)", nodecl, inline.}
        proc quo*(self: Barrett, n:int | uint):int =
            let n = n.uint
            let x = calc_mul(n.culonglong, self.im.culonglong).uint
            let r = n - x * self.m
            return int(if self.m <= r: x - 1 else: x)
        proc rem*(self: Barrett, n:int | uint):int =
            let n = n.uint
            let x = calc_mul(n.culonglong, self.im.culonglong).uint
            let r = n - x * self.m
            return int(if self.m <= r: r + self.m else: r)
        proc quorem*(self: Barrett, n:int | uint):(int, int) =
            let n = n.uint
            let x = calc_mul(n.culonglong, self.im.culonglong).uint
            let r = n - x * self.m
            return if self.m <= r: (int(x - 1), int(r + self.m)) else: (int(x), int(r))
    
        proc pow*(self: Barrett, n:uint | int, p:int):int =
            var
                a = self.rem(n)
                r:uint = if self.m == 1: 0 else: 1
                p = p
            while p > 0:
                if (p and 1) != 0: r = self.mul(r, a.uint)
                a = self.mul(a.uint, a.uint).int
                p = p shr 1
            return int(r)
    
        proc mul*(self: Barrett, a:uint, b:uint):uint {.inline.} =
    
            let z = a * b
            return self.rem(z).uint
    
        proc pow_mod_constexpr*(x, n, m:int):int =
            if m == 1: return 0
            var
                r = 1
                y = floorMod(x, m)
                n = n
            while n != 0:
                if (n and 1) != 0: r = (r * y) mod m
                y = (y * y) mod m
                n = n shr 1
            return r.int
        
        proc is_prime_constexpr*(n:int):bool =
            if n <= 1: return false
            if n == 2 or n == 7 or n == 61: return true
            if n mod 2 == 0: return false
            var d = n - 1
            while d mod 2 == 0: d = d div 2
            for a in [2, 7, 61]:
                var
                    t = d
                    y = pow_mod_constexpr(a, t, n)
                while t != n - 1 and y != 1 and y != n - 1:
                    y = y * y mod n
                    t =    t shl 1
                if y != n - 1 and t mod 2 == 0:
                    return false
            return true
        proc is_prime*[n:static[int]]():bool = is_prime_constexpr(n)
        proc inv_gcd*(a, b:int):(int,int) =
            var a = floorMod(a, b)
            if a == 0: return (b, 0)
        
            var
                s = b
                t = a
                m0 = 0
                m1 = 1
        
            while t != 0:
                var u = s div t
                s -= t * u;
                m0 -= m1 * u;    # |m1 * u| <= |m1| * s <= b
        
        
                var tmp = s
                s = t;t = tmp;
                tmp = m0;m0 = m1;m1 = tmp;
            if m0 < 0: m0 += b div s
            return (s, m0)
    
        proc primitive_root_constexpr*(m:int):int =
            if m == 2: return 1
            if m == 167772161: return 3
            if m == 469762049: return 3
            if m == 754974721: return 11
            if m == 998244353: return 3
            var divs:array[20, int]
            divs[0] = 2
            var cnt = 1
            var x = (m - 1) div 2
            while x mod 2 == 0: x = x div 2
            var i = 3
            while i * i <= x:
                if x mod i == 0:
                    divs[cnt] = i
                    cnt.inc
                    while x mod i == 0:
                        x = x div i
                i += 2
            if x > 1:
                divs[cnt] = x
                cnt.inc
            var g = 2
            while true:
                var ok = true
                for i in 0..<cnt:
                    if pow_mod_constexpr(g, (m - 1) div divs[i], m) == 1:
                        ok = false
                        break
                if ok: return g
                g.inc
        proc primitive_root*[m:static[int]]():auto =
            primitive_root_constexpr(m)
    
        proc floor_sum_unsigned*(n, m, a, b:uint):uint =
            result = 0
            var (n, m, a, b) = (n, m, a, b)
            while true:
                if a >= m:
                    result += n * (n - 1) div 2 * (a div m)
                    a = a mod m
                if b >= m:
                    result += n * (b div m)
                    b = b mod m
    
                let y_max = a * n + b
                if y_max < m: break
                n = y_max div m
                b = y_max mod m
                swap(m, a)
        discard

    proc getBarrett*[T:static[int]](t:typedesc[DynamicModInt[T]]):ptr Barrett =
        var Barrett_of_DynamicModInt {.global.} = initBarrett(998244353.uint)
        return Barrett_of_DynamicModInt.addr
    
    proc getMod*[T:static[int]](t:typedesc[DynamicModInt[T]]):uint32 {.inline.} =
        (t.getBarrett)[].m.uint32
    proc setMod*[T:static[int]](t:typedesc[DynamicModInt[T]], M:SomeInteger){.inline.} =
        (t.getBarrett)[] = initBarrett(M.uint)

    proc val*(m: ModInt): int {.inline.} = int(m.a)

    proc `$`*(m: StaticModInt or DynamicModInt): string {.inline.} = $(m.val())

    template umod*[T:ModInt](self: typedesc[T] or T):uint32 =
        when T is typedesc:
            when T is StaticModInt:
                T.M.uint32
            elif T is DynamicModInt:
                T.getMod()
            else:
                static: assert false
        else: T.umod

    template `mod`*[T:ModInt](self:typedesc[T] or T):int = T.umod.int

    proc init*[T:ModInt](t:typedesc[T], v: SomeInteger or T): auto {.inline.} =
        when v is T: return v
        else:
            when v is SomeUnsignedInt:
                if v.uint < T.umod:
                    return T(a:v.uint32)
                else:
                    return T(a:(v.uint mod T.umod.uint).uint32)
            else:
                var v = v.int
                if 0 <= v:
                    if v < T.mod: return T(a:v.uint32)
                    else: return T(a:(v mod T.mod).uint32)
                else:
                    v = v mod T.mod
                    if v < 0: v += T.mod
                    return T(a:v.uint32)
    proc unit*[T:ModInt](t:typedesc[T] or T):T = T.init(1)

    template initModInt*(v: SomeInteger or ModInt; M: static[int] = 1_000_000_007): auto =
        StaticModInt[M].init(v)


    proc raw*[T:ModInt](t:typedesc[T], v:SomeInteger):auto = T(a:v)

    proc inv*[T:ModInt](v:T):T {.inline.} =
        var
            a = v.a.int
            b = T.mod
            u = 1
            v = 0
        while b > 0:
            let t = a div b
            a -= t * b;swap(a, b)
            u -= t * v;swap(u, v)
        return T.init(u)


    proc `-`*[T:ModInt](m: T): T {.inline.} =
        if int(m.a) == 0: return m
        else: return T(a:m.umod() - m.a)

    proc `+=`*[T:ModInt](m: var T; n: SomeInteger | T):T {.inline discardable.} =
        m.a += T.init(n).a
        if m.a >= T.umod: m.a -= T.umod
        return m

    proc `-=`*[T:ModInt](m: var T; n: SomeInteger | T):T {.inline discardable.} =
        m.a -= T.init(n).a
        if m.a >= T.umod: m.a += T.umod
        return m

    proc `*=`*[T:ModInt](m: var T; n: SomeInteger | T):T {.inline discardable.} =
        when T is StaticModInt:
            m.a = (m.a.uint * T.init(n).a.uint mod T.umod).uint32
        elif T is DynamicModInt:
            m.a = T.getBarrett[].mul(m.a.uint, T.init(n).a.uint).uint32
        else:
            static: assert false
        return m

    proc `/=`*[T:ModInt](m: var T; n: SomeInteger | T):T {.inline discardable.} =
        m.a = (m.a.uint * T.init(n).inv().a.uint mod T.umod).uint32
        return m

    generateDefinitions(`+`, m, n, ModInt, SomeInteger):
        result = T.init(m)
        result += n

    generateDefinitions(`-`, m, n, ModInt, SomeInteger):
        result = T.init(m)
        result -= n

    generateDefinitions(`*`, m, n, ModInt, SomeInteger):
        result = T.init(m)
        result *= n

    generateDefinitions(`/`, m, n, ModInt, SomeInteger):
        result = T.init(m)
        result /= n

    generateDefinitions(`==`, m, n, ModInt, SomeInteger):
        result = (T.init(m).val() == T.init(n).val())

    proc inc*(m: var ModInt):ModInt {.inline discardable.} =
        m.a.inc
        if m.a == m.umod.uint32:
            m.a = 0
        return m
    proc `++`*(m: var ModInt):ModInt {.inline discardable.} = m.inc

    proc dec*(m: var ModInt):ModInt {.inline discardable.} =
        if m.a == 0.uint32:
            m.a = m.umod - 1
        else:
            m.a.dec
        return m
    proc `--`*(m: var ModInt):ModInt {.inline discardable.} = m.dec

    generatePow(ModInt)
    
    template useStaticModint*(name, M) =
        generateConverter(name, int, StaticModInt[M])
    template useDynamicModInt*(name, M) =
        generateConverter(name, int, DynamicModInt[M])

    useStaticModInt(modint998244353, 998244353)
    useStaticModInt(modint1000000007, 1000000007)
    useDynamicModInt(modint, -1)

    import std/math as math_lib_modint
    proc estimateRational*(a:ModInt, ub:int = int(sqrt(float(ModInt.mod))), output_stderr:static[bool] = false):string =
        var v:seq[tuple[s, n, d: int]]
        for d in 1 .. ub:
            var n = (a * d).val
            if n * 2 > a.mod:
                n = - (a.mod - n)
            if gcd(n, d) > 1: continue
            v.add((n.abs + d, n, d))
        v.sort
        when output_stderr:
            stderr.write "estimation result: ", v
        return $v[0].n & "/" & $v[0].d



    discard

type mint = modint998244353

proc solve() =
    var
        N = read(int)
        Q = read(int)
        dsu = initDSU(2 * N)
        dsu2 = initDSU(N)
    for i in 0..<Q:
        var
            (A, B, C) = read(int,int,int)
        A -= 1
        B -= 1
        if C == 0:
            dsu.merge(A, B)
            dsu.merge(A+N, B+N)
        else:
            dsu.merge(A, B+N)
            dsu.merge(A+N,B)
        dsu2.merge(A, B)
    for i in 0..<N:
        if dsu.same(i,i+N):
            echo 0
            return
    echo mint(2)^(dsu2.groups().len())

solve()

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード