Submission #635721

#	Time	Username	Problem	Language	Result	Execution time	Memory
635721		karolb2011	Furniture (JOI20_furniture)	Pypy 3	100 / 100	1027 ms	53104 KiB

furniture

import sys
input=sys.stdin.readline
n,m=list(map(int,input().split()))
f=[]
for i in range(n):
    f.append(list(map(int,input().split())))
i,j=0,0
h=[0 for i in range(n)]
v=[0 for i in range(m)]
while True:
    if j<m-1 and f[i][j+1]==0:
        j+=1
        h[i]=j
        f[i][j]+=2
    elif f[i+1][j]==0:
        i+=1
        h[i]=j
        f[i][j]+=10
    elif f[i][j]==2:
        f[i][j]=1
        j-=1
        h[i]=j
    else:
        f[i][j]=1
        i-=1
    if i==n-1 and j==m-1:
        break
i,j=0,0
while True:
    if i<n-1 and f[i+1][j]%2==0:
        i+=1
        v[j]=i
        f[i][j]+=4
    elif f[i][j+1]%2==0:
        j+=1
        v[j]=i
        f[i][j]+=20
    elif f[i][j]//16==0:
        f[i][j]=1
        i-=1
        v[j]=i
    else:
        f[i][j]=1
        j-=1
    if i==n-1 and j==m-1:
        break
q=int(input())
for _ in range(q):
    i,j=list(map(int,input().split()))
    i-=1
    j-=1
    w=False
    if j>h[i] or i>v[j]:
        print(1)
    elif f[i][j]%8==6:
        print(0)
    elif f[i][j]%8==0:
        print(1)
        f[i][j]=1
    else:
        print(1)
        if f[i][j]%8==2:
            if f[i][j]==2:
                f[i][j]=1
                j-=1
                h[i]=j
            else:
                f[i][j]=1
                h[i]=0
                i-=1
            while True:
                while j<m-1 and f[i][j+1]%2==0:
                    j+=1
                    if (f[i][j]//2)%2==1:
                        w=True
                        break
                    else:
                        f[i][j]+=2
                if w:
                    h[i]=max(h[i],j)
                    f[i][j]-=8
                    break
                h[i]=j               
                if i<n-1 and f[i+1][j]%2==0:
                    i+=1
                    f[i][j]+=10
                elif (f[i][j]//8)%2==0:
                    f[i][j]=1
                    j-=1
                    h[i]=j
                else:
                    f[i][j]=1
                    h[i]=0
                    i-=1
        else:
            if f[i][j]==4:
                f[i][j]=1
                i-=1
                v[j]=i
            else:
                f[i][j]=1
                v[j]=0
                j-=1
            while True:
                while i<n-1 and f[i+1][j]%2==0:
                    i+=1
                    if (f[i][j]//4)%2==1:
                        w=True
                        break
                    else:
                        f[i][j]+=4
                if w:
                    v[j]=max(v[j],i)
                    f[i][j]-=16
                    break
                v[j]=i                
                if j<m-1 and f[i][j+1]%2==0:
                    j+=1
                    f[i][j]+=20
                elif (f[i][j]//16)%2==0:
                    f[i][j]=1
                    i-=1
                    v[j]=i
                else:
                    f[i][j]=1
                    v[j]=0
                    j-=1

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95