oj.uz

Submission #635721

# Submission time Handle Problem Language Result Execution time Memory
635721 2022-08-26T17:46:22 Z karolb2011 Furniture (JOI20_furniture) PyPy 3
100 / 100
 1027 ms 53104 KB 
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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 19304 KB Output is correct
2 Correct 107 ms 24280 KB Output is correct
3 Correct 109 ms 25228 KB Output is correct
4 Correct 133 ms 27048 KB Output is correct
5 Correct 138 ms 26468 KB Output is correct
6 Correct 151 ms 26808 KB Output is correct
7 Correct 125 ms 25800 KB Output is correct
8 Correct 116 ms 26500 KB Output is correct
9 Correct 117 ms 25888 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 19304 KB Output is correct
2 Correct 107 ms 24280 KB Output is correct
3 Correct 109 ms 25228 KB Output is correct
4 Correct 133 ms 27048 KB Output is correct
5 Correct 138 ms 26468 KB Output is correct
6 Correct 151 ms 26808 KB Output is correct
7 Correct 125 ms 25800 KB Output is correct
8 Correct 116 ms 26500 KB Output is correct
9 Correct 117 ms 25888 KB Output is correct
10 Correct 158 ms 26484 KB Output is correct
11 Correct 120 ms 25512 KB Output is correct
12 Correct 489 ms 42692 KB Output is correct
13 Correct 218 ms 36140 KB Output is correct
14 Correct 864 ms 46596 KB Output is correct
15 Correct 862 ms 46676 KB Output is correct
16 Correct 849 ms 48064 KB Output is correct
17 Correct 922 ms 49488 KB Output is correct
18 Correct 986 ms 48120 KB Output is correct
19 Correct 960 ms 53104 KB Output is correct
20 Correct 1027 ms 51620 KB Output is correct
21 Correct 896 ms 51344 KB Output is correct