Submission #787007

#	Time	Username	Problem	Language	Result	Execution time	Memory
787007		Rafi22	Furniture (JOI20_furniture)	C++14	100 / 100	226 ms	13932 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=1007;

int ile[2*N];
bool a[N][N];
bool odw[N][N];

int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

int n,m;
bool good(int i,int j)
{
    return min(i,j)>0&&i<=n&&j<=m;
}

bool check(int i,int j)
{
    bool is=1,is1=1;
    if((i==n&&j==m)||(i==1&&j==1)) return 0;
    if(good(i-1,j)&&!odw[i-1][j]) is=0;
    if(good(i,j-1)&&!odw[i][j-1]) is=0;
    if(good(i+1,j)&&!odw[i+1][j]) is1=0;
    if(good(i,j+1)&&!odw[i][j+1]) is1=0;
    return is|is1;
}

void dfs(int i,int j)
{
    odw[i][j]=1;
    ile[i+j]--;
    for(int l=0;l<4;l++)
    {
        int ni=i+dx[l],nj=j+dy[l];
        if(good(ni,nj)&&!odw[ni][nj]&&check(ni,nj)) dfs(ni,nj);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            ile[i+j]++;
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]&&!odw[i][j]) dfs(i,j);
        }
    }
    int q;
    cin>>q;
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        if(a[x][y]||(!odw[x][y]&&ile[x+y]==1)) cout<<0<<endl;
        else
        {
            a[x][y]=1;
            if(!odw[x][y]) dfs(x,y);
            cout<<1<<endl;
        }
    }



    return 0;
}

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