#377971 (Nim) No.13 囲みたい！

提出ソース
結果

問題	No.13 囲みたい！
ユーザー	JOLM93QXTJYermP
提出日時	2019-09-10 20:21:40
言語	Nim (2.0.2)
結果	AC
実行時間	31 ms / 5,000 ms
コード長	17,551 bytes
コンパイル時間	2,536 ms
コンパイル使用メモリ	62,104 KB
実行使用メモリ	43,264 KB
最終ジャッジ日時	2024-07-02 16:19:32
合計ジャッジ時間	3,357 ms
ジャッジサーバーID （参考情報）	judge2 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	16 ms 22,528 KB
testcase_06	AC	2 ms 5,376 KB
testcase_07	AC	21 ms 28,160 KB
testcase_08	AC	31 ms 43,264 KB
testcase_09	AC	31 ms 42,624 KB
testcase_10	AC	6 ms 9,344 KB
testcase_11	AC	24 ms 33,024 KB
testcase_12	AC	4 ms 5,376 KB
testcase_13	AC	11 ms 15,488 KB
testcase_14	AC	12 ms 16,384 KB
testcase_15	AC	2 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
###################
###   utility   ###
###################
type lint = int64
template exit = quit 0
proc write[T]( x :T ) = stdout.write( $x )
proc alloc( T :typedesc ) :ptr T = cast[ptr T]( T.sizeof.alloc )
proc make[T]( f :proc():T ) :T = f()
# template make[T]( body :untyped ) :T =
#     block:
#         proc f() :T =
#             body
#         f()


####################
###   function   ###
####################
proc less[T1,T2]( x :T1, y :T2 ) :bool = x < y
proc more[T1,T2]( x :T1, y :T2 ) :bool = x > y

#proc add[T1,T2]( x :T1, y :T2 ) :T1 = x + y
proc mul[T1,T2]( x :T1, y :T2 ) :T1 = x * y

proc big[T1,T2]( x :T1, y :T2 ) :T1 = max(x, y)
proc sml[T1,T2]( x :T1, y :T2 ) :T1 = min(x, y)

# proc id[T]( x :T ) :T = x

proc `max=`*[T]( x :var T; y :T ) =
    if x < y:
        x = y

####################
###   iterator   ###
####################
iterator items( p :(int,int) ) :int =
    let (L,R) = p
    for i in L..<R:
        yield i

iterator items( N :int ) :int =
    for i in 0..<N:
        yield i

iterator reverse( L, R :int ) :int =
    var i = R
    while i > L:
        i.dec
        yield i

iterator reverse( N :int ) :int =
    for i in reverse(0, N):
        yield i


################
###   vect   ###
################
type vect[T] = seq[T]

proc Vect[T]( n :int ): vect[T] =
    newSeq[T]( result, n )

proc Vect[T]( N :int; X :T ) :vect[T] =
    result = Vect[T] N
    for i in N:
        result[i] = X

proc Vect[T]( S :openArray[T] ) :vect[T] =
    result = Vect[T]( S.len )
    for i, e in S:
        result[i] = e

proc elem[T]( e :T, s :varargs[T] ) :bool =
    for a in s:
        if e == a: return true
    return false

proc append[T]( V :var vect[T]; X :T ) =
    V = V & X

proc countIf[T]( S :openArray[T], f :proc(x:T):bool ) :int =
    for e in S:
        if f(e):
            result.inc

proc each*[T1;T2]( V :vect[T1]; F :proc(x:T1):T2 ) :vect[T2] =
    let N = V.len
    result = Vect[T2] N
    for i in N:
        result[i] = F V[i]



################
###   tens   ###
################
type tens[T] = object
    data :vect[T]
    shape :vect[int]

proc Tens[T]( S :varargs[int] ) :tens[T] =
    var N :int = 1
    for s in S: N *= s
    result.data = Vect[T](N)
    result.shape = @S

proc `[]`[T]( t :tens[T], s :varargs[int] ) :T =
    var n = 0
    var r = 1
    for i in reverse(s.len):
        n += s[i] * r
        r *= t.shape[i]
    return t.data[n]

proc `[]=`[T]( t :var tens[T], s :varargs[int], e :T ) =
    var n = 0
    var r = 1
    for i in reverse(s.len):
        n += s[i] * r
        r *= t.shape[i]
    t.data[n] = e

proc full[T]( S :var tens[T]; X :T ) =
    S.data.full X

iterator items[T]( t :tens[T] ) :T = items(t.data)


####################
###   priority   ###
####################
type priority[T] = object
    data :vect[T]
    compare :proc(x,y:T):bool

proc Priority[T]() :priority[T] =
    result.data = Vect[T](1)
    result.compare = less

proc Priority[T]( compare :proc(x,y:T):bool ) :priority[T] =
    result.data = Vect[T](1)
    result.compare = compare

proc exist[T]( p :priority[T] ) :bool = p.data.len > 1
proc push[T]( p :var priority[T], e :T ) =
    var n = p.data.len
    p.data.add(e)
    while n div 2 != 0 and p.compare( p.data[n], p.data[n div 2] ):
        swap( p.data[n], p.data[n div 2] )
        n = n div 2
proc front[T]( p :priority[T] ) :T = p.data[1]
proc trash[T]( p :var priority[T] ) =
    let N = p.data.len - 1
    p.data[1] = p.data[N]
    p.data.setLen(N)
    var n = 1
    while true:
        if n * 2 >= N: break
        if n * 2 + 1 >= N:
            if p.compare( p.data[n], p.data[n * 2] ): break
            swap( p.data[n], p.data[n * 2] )
            n = n * 2
            continue
        if not p.compare( p.data[n * 2], p.data[n] ) and
           not p.compare( p.data[n * 2 + 1], p.data[n] ):
            break
        if p.compare( p.data[n * 2], p.data[n * 2 + 1] ):
            swap( p.data[n], p.data[n * 2] )
            n = n * 2
        else:
            swap( p.data[n], p.data[n * 2 + 1] )
            n = n * 2 + 1
proc pop[T]( p :var priority[T] ) :T =
    result = p.front
    p.trash


##################
###   number   ###
##################
proc `^`[T](n :T, m :int) :T =
    var n = n
    var m = m
    result = 1.T
    while m > 0:
        if m mod 2 != 0: result = result * n
        n = n * n
        m = m div 2

proc `%`[N,M]( n :N, m :M ) :N =
    result = n mod m.N
    if n < 0: result += m.N

proc fact[I]( n :I ) :I =
    var memo {.global.} :seq[I] = @[I(1)]
    if n.int >= memo.len:
        let m :int = memo.len
        memo.setLen(n.int + 1)
        for i in m..n.int:
            memo[i] = memo[i-1] * i
    return memo[n.int]

proc triangular[I]( n :I ) :I =
    var memo {.global.} :seq[I] = @[I(0)]
    if n.int >= memo.len:
        let m :int = memo.len
        memo.setLen(n.int + 1)
        for i in m..n.int:
            memo[i] = memo[i-1] + i
    return memo[n.int]

proc sum[T]( V :vect[T]) :T =
    result = 0
    for x in V:
        result += x

iterator divisor( N :int ) :int =
    var i = 1
    while i * i < N:
        if N mod i == 0:
            yield i
            yield N div i
        i.inc
    if i * i == N:
        yield i

proc divisor( N :int ) :vect[int] =
    result = @[]
    for d in N.divisor:
        result.add d


proc perm[N,K]( n :N, k :K ) :N =
    fact(n) div fact(n-k)

proc comb[N,K]( n :N, k :K ) :N =
    fact(n) div fact(k.N) div fact(n-k)

proc eratos( N :int ) :vect[bool] =
    result = Vect[bool](N+1)
    for i in (2,N+1): result[i] = true
    var i = 2
    while i * i <= N:
        if result[i]:
            var j = i * 2
            while j <= N:
                result[j] = false
                j += i
        i += 1

proc ceilDiv( n: int, m: int ) :int =
    return (n + m - 1) div m


################
###   list   ###
################
const ListNodeSize = 1024

type listNode[T] = object
    data :array[ListNodeSize,T]
    prev, next :ptr listNode[T]

type list[T] = object
    head,  tail :ptr listNode[T]
    first, last :int

proc List[T]() :list[T] =
    result.head = listNode[T].alloc
    result.tail = result.head

proc empty[T]( li :list[T] ) :bool =
    li.head == li.tail and li.first == li.last

proc exist[T]( li :list[T] ) :bool =
    not li.empty()

proc len[T]( li :list[T] ) :int =
    var now = li.head
    while now != nil:
        result += ListNodeSize
        now = now.next
    result -= ListNodeSize + li.first - li.last

proc mostLeft[T]( li :list[T] ) :T =
    li.head.data[li.first]

proc mostRight[T]( li :list[T] ) :T =
    if li.last == 0:
        li.tail.prev.data[ListNodeSize-1]
    else:
        li.tail.data[li.last-1]

proc pushLeft[T]( li :var list[T], e :T ) =
    if li.first == 0:
        li.head.prev = alloc( listNode[T] )
        li.head.prev.next = li.head
        li.head = li.head.prev
    li.first = (li.first - 1) % ListNodeSize
    li.head.data[li.first] = e

proc pushRight[T]( li :var list[T], e :T ) =
    li.tail.data[li.last] = e
    li.last = (li.last + 1) % ListNodeSize
    if li.last == 0:
        li.tail.next = alloc( listNode[T] )
        li.tail.next.prev = li.tail
        li.tail = li.tail.next

proc trashLeft[T]( li :var list[T] ) =
    li.first = (li.first + 1) mod ListNodeSize
    if li.first == 0:
        li.head = li.head.next
        li.head.prev.dealloc
        li.head.prev = nil

proc trashRight[T]( li :var list[T] ) =
    if li.last == 0:
        li.tail = li.tail.prev
        li.tail.next.dealloc
        li.tail.next = nil
    li.last = (li.last - 1) % ListNodeSize

proc popLeft[T]( li :var list[T] ) :T =
    result = li.mostLeft
    li.trashLeft

proc popRight[T]( li :var list[T] ) :T =
    result = li.mostRight
    li.trashRight

proc `[]`[T]( li :list[T], n :int ) :T =
    var p = li.head
    for _ in (n + li.first) div ListNodeSize: p = p.next
    return p.data[(li.first + n) % ListNodeSize]

proc `[]=`[T]( li :var list[T], n :int, e :T ) =
    var p = li.head
    for _ in (n + li.first) div ListNodeSize: p = p.next
    p.data[(li.first + n) % ListNodeSize] = e

iterator items[T]( li :list[T] ) :T =
    var i = li.first
    var now = li.head
    while now != li.tail:
        while i != ListNodeSize:
            yield now.data[i]
            i.inc
        i = 0
        now = now.next
    while i != li.last:
        yield now.data[i]
        i.inc

proc `$`[T]( li :list[T] ) :string =
    if li.empty: return "list[]"
    result = "list["
    for e in li:
        result &= $e
        result &= ", "
    result.setLen(result.len - 2)
    result &= "]"


#################
###   stack   ###
#################
type stack[T] = object
    data :list[T]
proc Stack[T]() :stack[T] = result.data = List[T]()
proc exist[T]( s :stack[T] ) :bool = s.data.exist
proc empty[T]( s :stack[T] ) :bool = s.data.empty
proc push[T]( s :var stack[T], e :T ) = s.data.pushRight(e)
proc front[T]( s :stack[T] ) :T = s.data.mostRight
proc trash[T]( s :var stack[T] ) = s.data.trashRight
proc pop[T]( s :var stack[T] ) :T = s.data.popRight
proc Stack[T](e:T):stack[T] = result = Stack[T](); result.push(e)


#################
###   queue   ###
#################
type queue[T] = object
    data :list[T]
proc Queue[T]() :queue[T] = result.data = List[T]()
proc exist[T]( q :queue[T] ) :bool = q.data.exist
proc empty[T]( q :queue[T] ) :bool = q.data.empty
proc push[T]( q :var queue[T], e :T ) = q.data.pushRight(e)
proc front[T]( q :queue[T] ) :T = q.data.mostLeft
proc trash[T]( q :var queue[T] ) :T = q.data.trashLeft
proc pop[T]( q: var queue[T] ) :T = q.data.popLeft
proc Queue[T](e:T):queue[T] = result = Queue[T](); result.push(e)


################
###   sort   ###
################
proc sort[T]( S :var vect[T], compare :proc(x,y:T):bool ) =
    var stack = Stack[ (bool,int,int) ]()
    stack.push( (true, 0, S.len) )
    while stack.exist:
        var (B, L, R) = stack.pop
        if R - L < 2: continue
        if B:
            stack.push( (false, L, R) )
            stack.push( (true, L, (L+R) div 2) )
            stack.push( (true, (L+R) div 2, R) )
            continue

        var temp = Vect[T]( (L+R) div 2 - L )
        for i in temp.len: temp[i] = S[L+i]
        var (t, r) = (0, (L+R) div 2)
        for i in (L,R):
            if r == R or t != temp.len and compare(temp[t], S[r] ):
                S[i] = temp[t]
                t.inc
            else:
                S[i] = S[r]
                r.inc

proc sort[T]( S :var vect[T] ) =
    S.sort(less)

proc Sort[T]( S :vect[T], comp :proc(x,y:T):bool ) :vect[T] =
    result = Vect[T](S)
    sort[T](result,comp)

proc Sort[T]( S :vect[T] ) :vect[T] =
    result = Vect[T](S)
    result.sort


####################
###   min, max   ###
###################
proc argMax[T]( V :openArray[T] ) :int =
    var max = T.low
    for i, e in V:
        if e > max:
            result = i
            max = e

proc upperBound[T]( L, R :T, f :proc(n:T):bool ) :T =
    var (ok, ng) = (L, R)
    while ng - ok > 1:
        let mid = (ng + ok) div 2
        if f( mid ):
            ok = mid
        else:
            ng = mid
    return ok

proc lowerBound[T]( L, R :T, f :proc(n:T):bool ) :T =
    upperBound( L, R, proc(n:T) :bool = not f(n) ) + 1


################
###   read   ###
################
proc read( T :typedesc ) :T =
    proc getchar() :char
        {.header:"stdio.h",importc:"getchar_unlocked".}

    when T is char:
        result = getchar()
        discard getchar()

    when T is string:
        result = ""
        while true:
            var c = getchar()
            if c.elem( ' ', '\10', '\255' ): break
            result.add c

    when T is (int or lint):
        var
            sign = 1
            c = getchar()

        if c == '-':
            sign = -1
            c = getchar()

        while '0' <= c and c <= '9':
            result *= 10
            result += c.int() - '0'.int()
            c = getchar()

        result *= sign

    when T is tuple:
        for r in result.fields:
            r = r.type.read

proc read( T :typedesc, N :int ) :vect[T] =
    result = Vect[T](N)
    for i in N:
        result[i] = T.read


####################
###   disjoint   ###
####################
type disjoint = object
    data :vect[int]

proc Disjoint( n :int ) :disjoint =
    result.data = Vect[int](n)
    for i in n: result.data[i] = -1

proc find( d :var disjoint, n :int ) :int =
    if d.data[n] < 0: return n
    d.data[n] = d.find( d.data[n] )
    return d.data[n]

proc union( d :var disjoint, n, m :int ) =
    var n = d.find(n)
    var m = d.find(m)
    if n == m: return
    if d.data[m] < d.data[n]: swap( n, m )
    d.data[m] += d.data[n]
    d.data[n] = m

proc same( d :var disjoint, n, m :int ) :bool =
    d.find(n) == d.find(m)

proc size( d :var disjoint, n :int ) :int =
    - d.data[d.find(n)]


###############
###   bit   ###
###############
iterator allBit[I]() :I =
    var i :I = 1.I
    while i != 0.I:
        yield i
        i = i shl 1.I

proc bitCount( b :int ) :int =
    var b :int64 = b
    b = (b        and 0x5555555555555555) +
        (b shr  1 and 0x5555555555555555)
    b = (b        and 0x3333333333333333) +
        (b shr  2 and 0x3333333333333333)
    b = (b        and 0x0f0f0f0f0f0f0f0f) +
        (b shr  4 and 0x0f0f0f0f0f0f0f0f)
    b = (b        and 0x00ff00ff00ff00ff) +
        (b shr  8 and 0x00ff00ff00ff00ff)
    b = (b        and 0x0000ffff0000ffff) +
        (b shr 16 and 0x0000ffff0000ffff)
    b = (b        and 0x00000000ffffffff) +
        (b shr 32 and 0x00000000ffffffff)
    result = b.int


###################
###   segment   ###
###################
type segment[T] = object
    size :int
    data :vect[T]
    id :T
    op :proc(x,y:T):T

proc Segment[T]( V :vect[T], e :T, F :proc(x,y:T):T ) :segment[T] =
    result.id = e
    result.op = F
    result.size = 1
    while result.size < V.len: result.size = result.size shl 1
    result.data = Vect[T](result.size * 2)
    for i in V.len: result.data[result.size + i] = V[i]
    for i in (V.len,result.size): result.data[result.size+i] = e
    for i in reverse(1,result.size):
        result.data[i] = F( result.data[2*i], result.data[2*i+1] )

proc update[T]( S :var segment[T], K :int, X :T ) =
    var k = K + S.size
    S.data[k] = X
    while(k != 0):
        k = k div 2
        S.data[k] = S.op( S.data[k*2], S.data[2*k+1] )

proc query[T]( S :segment[T], L, R :int ) :T =
    var
        X = S.id
        Y = S.id
        L = L + S.size
        R = R + S.size
    while L < R:
        if (L and 1) != 0:
            X = S.op( X, S.data[L] )
            L.inc
        if (R and 1) != 0:
            R.dec
            Y = S.op( S.data[R], Y )
        L = L div 2
        R = R div 2
    return S.op(X,Y)


#####################
###   shakutori   ###
#####################
proc shakutori( N, M :int, C :proc(x,y:int):bool ) :int =
    result = 0
    var R = N
    for L in (N,M):
        while R < M and C(L, R+1): R.inc
        result += R - L
        if L == R: R.inc


################
###   mint   ###
################
const MOD :int = 1000000007
type mint = distinct int

proc Mint[I]( n :I ) :mint =
    var n = n.int mod MOD
    if n < 0: n = n + MOD
    return n.mint

proc `$`( m :mint ) :string = $m.int
proc `+`[I]( m: mint, n: I ) :mint = (m.int + n.int).Mint
proc `-`[I]( m: mint, n: I ) :mint = (m.int - n.int).Mint
proc `*`[I]( m: mint, n: I ) :mint = (m.int * n.int).Mint
proc `/`[I]( m :mint, n :I ) :mint =
    var
        a = n.int
        b = MOD
        u = 1
        v = 0
    while b > 0:
        var t = a div b
        a -= t * b
        u -= t * v
        swap( a, b )
        swap( u, v )
    return m * u

proc `div`[I]( m :mint, n :I ) :mint = m / n

proc `+=`[I]( m :var mint, n :I ) = m = m + n
proc `-=`[I]( m :var mint, n :I ) = m = m - n
proc `*=`[I]( m :var mint, n :I ) = m = m * n
proc `/=`[I]( m :var mint, n :I ) = m = m / n

proc `==`[I]( m :mint, n :I ) :bool = m.int == n.Mint.int


#######################
###   topological   ###
#######################
proc topological( G :vect[vect[int]] ) :vect[int] =
    let N = G.len

    var h = Vect[int] N
    for p in G:
        for c in p:
            h[c].inc

    var q = Queue[int]()
    for i in N:
        if h[i] == 0:
            q.push i

    result = Vect[int] N
    var now = 0
    while q.exist:
        let n = q.pop
        result[now] = n
        now.inc

        for c in G[n]:
            h[c].dec
            if h[c] == 0:
                q.push c

    for i in N:
        if h[i] != 0:
            raise




##########################
####                  ####
####       main       ####
####                  ####
##########################
let (W, H) = (int,int).read
var M = Tens[int]( H, W )
for y in H:
    for x in W:
        M[y,x] = int.read

var v = Tens[bool]( H, W )

for y in H:
    for x in W:
        if v[y,x] == true:
            continue
        var q = Queue[(int,int,int,int)]()
        q.push (-1,-1,x,y)
        while q.exist:
            let (px, py, X, Y) = q.pop
            v[Y,X] = true
            let D = [(0,1),(0,-1),(1,0),(-1,0)]

            for d in D:
                let (nx,ny) = (X+d[0], Y+d[1])
                if (px, py) == (nx, ny):
                    continue
                if nx < 0 or ny < 0 or nx >= W or ny >= H:
                    continue
                if M[y,x] != M[ny,nx]:
                    continue
                if v[ny,nx] == true:
                    "possible".echo
                    exit
                q.push (X, Y, nx, ny)
"impossible".echo
yukicoder

結果

テストケース

ソースコード
