Submission #478994

#	Time	Username	Problem	Language	Result	Execution time	Memory
478994		nicolaalexandra	Furniture (JOI20_furniture)	C++14	100 / 100	2099 ms	15868 KiB

furniture

#include <bits/stdc++.h>
#define DIM 1010
using namespace std;

int a[DIM][DIM],viz[DIM][DIM],cnt[DIM*2];
int n,m,i,j,q,x,y;

void mark (int i, int j){
    if (i <= 0 || i > n || j <= 0 || j > m)
        return;
    if (a[i][j])
        return;

    a[i][j] = 1;
    cnt[i+j]--;

    if (i == 1 || j == m || a[i-1][j+1]){
        mark (i,j+1);
        mark (i-1,j);
    }

    if (i == n || j == 1 || a[i+1][j-1]){
        mark (i+1,j);
        mark (i,j-1);
    }

}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;

    /// cnt[i] - in cate locuri de pe diagonala secundara i pot sa ajung

    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            cnt[i+j]++;

    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            cin>>x;
            if (x)
                mark (i,j);
        }

    cin>>q;
    for (;q--;){
        cin>>x>>y;
        if (a[x][y]){
            cout<<"1\n";
            continue;
        }
        if (cnt[x+y] == 1){
            cout<<"0\n";
            continue;
        }
        cout<<"1\n";
        mark(x,y);
    }

    return 0;
}

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