結果
| 問題 | No.179 塗り分け |
| ユーザー |
 Keroru
|
| 提出日時 | 2020-04-29 15:54:26 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 252 ms / 3,000 ms |
| コード長 | 8,462 bytes |
| コンパイル時間 | 294 ms |
| コンパイル使用メモリ | 87,016 KB |
| 実行使用メモリ | 81,428 KB |
| 最終ジャッジ日時 | 2023-09-30 21:27:23 |
| 合計ジャッジ時間 | 10,395 ms |
|
ジャッジサーバーID （参考情報） |
judge12 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 173 ms
78,348 KB |
| testcase_01 | AC | 169 ms
78,552 KB |
| testcase_02 | AC | 166 ms
78,460 KB |
| testcase_03 | AC | 166 ms
78,344 KB |
| testcase_04 | AC | 165 ms
78,488 KB |
| testcase_05 | AC | 193 ms
80,676 KB |
| testcase_06 | AC | 167 ms
78,460 KB |
| testcase_07 | AC | 168 ms
78,700 KB |
| testcase_08 | AC | 189 ms
81,096 KB |
| testcase_09 | AC | 181 ms
80,636 KB |
| testcase_10 | AC | 174 ms
80,360 KB |
| testcase_11 | AC | 175 ms
80,368 KB |
| testcase_12 | AC | 223 ms
81,372 KB |
| testcase_13 | AC | 167 ms
78,472 KB |
| testcase_14 | AC | 167 ms
78,284 KB |
| testcase_15 | AC | 168 ms
78,424 KB |
| testcase_16 | AC | 166 ms
78,476 KB |
| testcase_17 | AC | 166 ms
78,140 KB |
| testcase_18 | AC | 177 ms
80,276 KB |
| testcase_19 | AC | 175 ms
80,364 KB |
| testcase_20 | AC | 222 ms
80,928 KB |
| testcase_21 | AC | 225 ms
81,428 KB |
| testcase_22 | AC | 252 ms
81,264 KB |
| testcase_23 | AC | 179 ms
80,384 KB |
| testcase_24 | AC | 209 ms
81,264 KB |
| testcase_25 | AC | 174 ms
80,428 KB |
| testcase_26 | AC | 180 ms
80,448 KB |
| testcase_27 | AC | 209 ms
81,116 KB |
| testcase_28 | AC | 179 ms
80,504 KB |
| testcase_29 | AC | 213 ms
80,980 KB |
| testcase_30 | AC | 183 ms
80,944 KB |
| testcase_31 | AC | 215 ms
80,896 KB |
| testcase_32 | AC | 182 ms
80,488 KB |
| testcase_33 | AC | 217 ms
81,004 KB |
| testcase_34 | AC | 181 ms
80,324 KB |
| testcase_35 | AC | 221 ms
81,408 KB |
| testcase_36 | AC | 165 ms
78,408 KB |
| testcase_37 | AC | 168 ms
78,564 KB |
| testcase_38 | AC | 165 ms
78,468 KB |
| testcase_39 | AC | 162 ms
78,352 KB |
| testcase_40 | AC | 163 ms
78,160 KB |
| testcase_41 | AC | 165 ms
78,452 KB |
| testcase_42 | AC | 166 ms
78,512 KB |
| testcase_43 | AC | 174 ms
80,084 KB |
| testcase_44 | AC | 186 ms
80,932 KB |
| testcase_45 | AC | 167 ms
78,120 KB |
ソースコード
import sys,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
org_inp=[];g=[[] for i in range(V)]
FromStdin=True if ls==None else False
for i in range(E):
if FromStdin:
inp=LI()
a,b,c=(inp+[1])[:3]
org_inp.append(inp)
else:
index=0
a,b,c=(ls[i]+[1])[:3]
if index==1:a-=1;b-=1
aa=(a,c);bb=(b,c);g[a].append(bb)
if not Directed:g[b].append(aa)
return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
mp=[boundary]*(w+2);found={}
for i in range(h):
s=input()
for char in search:
if char in s:
found[char]=((i+1)*(w+2)+s.index(char)+1)
mp_def[char]=mp_def[replacement_of_found]
mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
mp+=[boundary]*(w+2)
return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
rt=[]
for tb in range(n**k):
s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
return rt
def show(*inp,end='\n'):
if show_flg:print(*inp,end=end)
YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
class Comb:
def __init__(self,n,mo=10**9+7):
self.fac=[0]*(n+1)
self.inv=[1]*(n+1)
self.fac[0]=1
self.fact(n)
for i in range(1,n+1):
self.fac[i]=i*self.fac[i-1]%mo
self.inv[n]*=i
self.inv[n]%=mo
self.inv[n]=pow(self.inv[n],mo-2,mo)
for i in range(1,n):
self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
return
def fact(self,n):
return self.fac[n]
def invf(self,n):
return self.inv[n]
def comb(self,x,y):
if y<0 or y>x:
return 0
return self.fac[x]*self.inv[x-y]*self.inv[y]%mo
show_flg=False
show_flg=True
## Segment Tree ##
## Initializer Template ##
# Range Sum: sg=SegTree(n)
# Range Minimum: sg=SegTree(n,inf,min,inf)
class SegTree:
def __init__(self,n,init_ls=None,init_val=0,function=lambda a,b:a+b,ide=0):
self.n=n
self.ide_ele=ide_ele=ide
self.num=num=2**(n-1).bit_length()
self.seg=seg=[self.ide_ele]*2*self.num
self.lazy=lazy=[self.ide_ele]*2*self.num
self.segfun=segfun=function
#set_val
if init_ls==None:
for i in range(n):
self.seg[i+self.num-1]=init_val
else:
for i in range(n):
self.seg[i+self.num-1]=init_ls[i]
#build
for i in range(self.num-2,-1,-1):
self.seg[i]=self.segfun(self.seg[2*i+1],self.seg[2*i+2])
def update(self,k,x):
k += self.num-1
self.seg[k] = x
while k:
k = (k-1)//2
self.seg[k] = self.segfun(self.seg[k*2+1],self.seg[k*2+2])
def evaluate(k,l,r): #遅延評価処理
if lazy[k]!=0:
node[k]+=lazy[k]
if(r-l>1):
lazy[2*k+1]+=lazy[k]//2
lazy[2*k+2]+=lazy[k]//2
lazy[k]=0
def query(self,p,q):
if q<=p:
return self.ide_ele
p += self.num-1
q += self.num-2
res=self.ide_ele
while q-p>1:
if p&1 == 0:
res = self.segfun(res,self.seg[p])
if q&1 == 1:
res = self.segfun(res,self.seg[q])
q -= 1
p = p//2
q = (q-1)//2
if p == q:
res = self.segfun(res,self.seg[p])
else:
res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
return res
def find_min_index(self,p,q,m):
if q<=p:
return self.ide_ele
p += self.num-1
q += self.num-2
res=self.ide_ele
while q-p>1:
if p&1 == 0:
res = self.segfun(res,self.seg[p])
if q&1 == 1:
res = self.segfun(res,self.seg[q])
q -= 1
p >>= 1
q = (q-1)//2
if p == q:
res = self.segfun(res,self.seg[p])
else:
res = self.segfun(self.segfun(res,self.seg[p]),self.seg[q])
return res
def __str__(self):
# 生配列を表示
rt=self.seg[self.num-1:self.num-1+self.n]
return str(rt)
class Tree:
def __init__(self,inp_size=None,init=True):
if init:
self.stdin(inp_size)
return
def stdin(self,inp_size=None):
if inp_size==None:
self.size=int(input())
else:
self.size=inp_size
self.edges,_=GI(self.size,self.size-1)
return
def listin(self,ls):
self.size=len(ls)+1
self.edges,_=GI(self.size,self.size-1,ls)
return
def __str__(self):
return str(self.edges)
def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
q=deque()
q.append(x)
v=[-1]*self.size
v[x]=root_v
while q:
c=q.pop()
for nb,d in self.edges[c]:
if v[nb]==-1:
q.append(nb)
v[nb]=func(v[c],nb,d)
return v
def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
q=deque()
q.append((-1,x))
v=[None]*self.size
v[x]=root_v
et=[]
while q:
cb,ce=q.pop()
et.append(ce)
for nb,d in self.edges[ce]:
if v[nb]==None:
q.append((nb,ce))
q.append((ce,nb))
v[nb]=func(v[ce],nb,d)
vid=[[-1,-1]for i in range(self.size)]
for i,j in enumerate(et):
if vid[j][0]==-1:
vid[j][0]=i
else:
vid[j][1]=i
return v,et,vid
def LCA_init(self,depth,et):
self.st=SegTree(self.size*2-1,func=min,ide=inf)
for i,j in enumerate(et):
self.st.update(i,j)
self.LCA_init_stat==True
return
def LCA(self,root,x,y):
if self.LCA_init_stat==False:
depth,et,vid=self.EulerTour(root)
self.LCA_init(depth,et)
return self.st.query(x,y+1)
h,w=LI()
h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=0) # sample usage
if 1 not in g:
print("NO")
exit()
for dh in range(h):
for dw in range(w):
mp=g[:]
dd=dh*w+dw
fl=True
for i in range(1,h-1):
for j in range(1,w-1):
c=i*w+j
if mp[c]==0:
continue
if c+dd>=h*w or c+dd<0 or mp[c+dd]==0:
fl=False
break
else:
mp[c+dd]=0
if not fl:break
if fl:
ans=dh,dw
if ans==(0,0):
continue
print("YES")
exit()
for dh in range(h):
for dw in range(-w+1,1):
mp=g[:]
dd=dh*w+dw
fl=True
for i in range(1,h-1):
for j in range(1,w-1)[::-1]:
c=i*w+j
if mp[c]==0:
continue
if c+dd>=h*w or c+dd<0 or mp[c+dd]==0:
fl=False
break
else:
mp[c+dd]=0
if not fl:break
if fl:
ans=dh,dw
if ans==(0,0):
continue
print("YES")
exit()
print("NO")