Submission #1092846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092846		maxFedorchuk	Furniture (JOI20_furniture)	C++17	100 / 100	157 ms	19852 KiB

furniture

#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 / 5
• Subtask 2: 95 / 95