oj.uz

Submission #1092846

# Submission time Handle Problem Language Result Execution time Memory
1092846 2024-09-25T08:46:28 Z maxFedorchuk Furniture (JOI20_furniture) C++17
100 / 100
 157 ms 19852 KB 
#include <bits/stdc++.h>
using namespace std;

const long long MX=2e3+10;
int a[MX][MX],kvil[MX];

int corx[4]={0,0,1,-1};
int cory[4]={1,-1,0,0};

int n,m;

void upd(int x,int y)
{
    if(a[x][y])
    {
        return;
    }

    a[x][y]=1;
    kvil[x+y]--;

    for(int i=0;i<4;i++)
    {
        int nx=x+corx[i];
        int ny=y+cory[i];

        if(!(nx==1 && ny==1) && !(nx==n && ny==m) && ((a[nx-1][ny]==1 && a[nx][ny-1]==1) || (a[nx+1][ny]==1 && a[nx][ny+1]==1)))
        {
            upd(nx,ny);
        }
    }
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin>>n>>m;

    for(int i=0;i<=n+1;i++)
    {
        for(int j=0;j<=m+1;j++)
        {
            if(i!=0 && j!=0 && i!=n+1 && j!=m+1)
            {
                kvil[i+j]++;
            }
            else
            {
                a[i][j]=1;
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int zn;
            cin>>zn;

            if(zn==1)
            {
                if(!a[i][j])
                {
                    upd(i,j);
                }
            }
        }
    }

    int q;
    cin>>q;

    while(q--)
    {
        int x,y;
        cin>>x>>y;

        if(a[x][y]==1)
        {
            cout<<"1\n";
            continue;
        }

        if(kvil[x+y]==1)
        {
            cout<<"0\n";
        }
        else
        {
            upd(x,y);
            cout<<"1\n";
        }
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 856 KB Output is correct
6 Correct 2 ms 1008 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 996 KB Output is correct
9 Correct 2 ms 860 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 856 KB Output is correct
6 Correct 2 ms 1008 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 996 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 6 ms 1116 KB Output is correct
11 Correct 2 ms 784 KB Output is correct
12 Correct 92 ms 12748 KB Output is correct
13 Correct 40 ms 9552 KB Output is correct
14 Correct 142 ms 17232 KB Output is correct
15 Correct 144 ms 17232 KB Output is correct
16 Correct 153 ms 18492 KB Output is correct
17 Correct 150 ms 19284 KB Output is correct
18 Correct 153 ms 18772 KB Output is correct
19 Correct 155 ms 19792 KB Output is correct
20 Correct 141 ms 19852 KB Output is correct
21 Correct 157 ms 19796 KB Output is correct