結果
| 問題 | No.13 囲みたい！ |
| ユーザー |
 JOLM93QXTJYermP
|
| 提出日時 | 2019-09-10 20:25:58 |
| 言語 | Nim (2.0.2) |
| 結果 |
AC
|
| 実行時間 | 31 ms / 5,000 ms |
| コード長 | 17,551 bytes |
| コンパイル時間 | 2,527 ms |
| コンパイル使用メモリ | 62,608 KB |
| 実行使用メモリ | 43,008 KB |
| 最終ジャッジ日時 | 2024-07-02 16:19:40 |
| 合計ジャッジ時間 | 3,393 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| 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,400 KB |
| testcase_06 | AC | 2 ms
5,376 KB |
| testcase_07 | AC | 21 ms
28,160 KB |
| testcase_08 | AC | 31 ms
43,008 KB |
| testcase_09 | AC | 31 ms
42,752 KB |
| testcase_10 | AC | 6 ms
9,472 KB |
| testcase_11 | AC | 24 ms
33,152 KB |
| testcase_12 | AC | 4 ms
5,504 KB |
| testcase_13 | AC | 12 ms
15,488 KB |
| testcase_14 | AC | 12 ms
16,512 KB |
| testcase_15 | AC | 2 ms
5,376 KB |
ソースコード
###################
### 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 = Stack[(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