#472499 (PyPy3) No.179 塗り分け

提出ソース

結果

問題	No.179 塗り分け
ユーザー	Keroru
提出日時	2020-04-29 15:41:14
言語	PyPy3 (7.3.15)
結果	WA
実行時間	-
コード長	7,832 bytes
コンパイル時間	700 ms
コンパイル使用メモリ	87,000 KB
実行使用メモリ	81,552 KB
最終ジャッジ日時	2023-08-19 05:26:22
合計ジャッジ時間	11,836 ms
ジャッジサーバーID （参考情報）	judge9 / judge12

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	164 ms 78,660 KB
testcase_01	AC	161 ms 78,872 KB
testcase_02	AC	161 ms 78,928 KB
testcase_03	AC	164 ms 78,764 KB
testcase_04	AC	165 ms 78,820 KB
testcase_05	AC	176 ms 80,788 KB
testcase_06	AC	162 ms 78,852 KB
testcase_07	WA	-
testcase_08	AC	190 ms 81,552 KB
testcase_09	AC	181 ms 80,884 KB
testcase_10	AC	171 ms 80,596 KB
testcase_11	AC	173 ms 80,508 KB
testcase_12	AC	197 ms 81,348 KB
testcase_13	AC	161 ms 78,604 KB
testcase_14	AC	160 ms 78,604 KB
testcase_15	AC	161 ms 78,612 KB
testcase_16	AC	160 ms 78,732 KB
testcase_17	WA	-
testcase_18	AC	171 ms 80,388 KB
testcase_19	AC	171 ms 80,428 KB
testcase_20	AC	193 ms 81,280 KB
testcase_21	AC	194 ms 81,360 KB
testcase_22	AC	215 ms 81,272 KB
testcase_23	AC	172 ms 80,652 KB
testcase_24	AC	189 ms 81,308 KB
testcase_25	AC	178 ms 80,368 KB
testcase_26	AC	177 ms 80,676 KB
testcase_27	AC	182 ms 81,012 KB
testcase_28	AC	174 ms 80,604 KB
testcase_29	AC	192 ms 81,256 KB
testcase_30	AC	178 ms 81,180 KB
testcase_31	AC	188 ms 80,848 KB
testcase_32	AC	179 ms 80,808 KB
testcase_33	AC	192 ms 81,200 KB
testcase_34	AC	176 ms 80,692 KB
testcase_35	AC	193 ms 81,364 KB
testcase_36	AC	162 ms 78,848 KB
testcase_37	AC	161 ms 78,808 KB
testcase_38	AC	160 ms 78,604 KB
testcase_39	AC	164 ms 78,784 KB
testcase_40	AC	163 ms 78,804 KB
testcase_41	AC	161 ms 78,800 KB
testcase_42	AC	162 ms 78,604 KB
testcase_43	AC	163 ms 78,620 KB
testcase_44	AC	174 ms 80,984 KB
testcase_45	AC	162 ms 78,920 KB

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

ソースコード

raw source code

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


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 mp[c+dd]<=0:
                    fl=False
                    break
                else:
                    mp[c+dd]=-1
            if not fl:break
        if fl:
            ans=dh,dw
            if ans==(0,0):
                continue
            print("YES")
            exit()

print("NO")

yukicoder

結果

テストケース

ソースコード