Submission #516305

#	Time	Username	Problem	Language	Result	Execution time	Memory
516305		qwerasdfzxcl	Furniture (JOI20_furniture)	C++14	100 / 100	606 ms	23844 KiB

furniture

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
int a[1010][1010], dp1[1010][1010], dp2[1010][1010], cnt[2020];

void debug(int n, int m){
    printf("DEBUG\n");
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) printf("%d ", dp1[i][j]);
        printf("\n");
    }

    printf("\n");
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) printf("%d ", dp2[i][j]);
        printf("\n");
    }
    printf("\n");
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) scanf("%d", a[i]+j);
    }

    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            dp1[i][j] = dp1[i][j-1] | dp1[i-1][j];
            if (a[i][j]) dp1[i][j] = 0;
            dp1[1][1] = 1;
        }
    }
    for (int i=n;i;i--){
        for (int j=m;j;j--){
            dp2[i][j] = dp2[i][j+1] | dp2[i+1][j];
            if (a[i][j]) dp2[i][j] = 0;
            dp2[n][m] = 1;
        }
    }

    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) if (dp1[i][j] && dp2[i][j]) cnt[i+j]++;
    }

    //debug(n, m);


    int q;
    scanf("%d", &q);
    while(q--){
        int x, y;
        scanf("%d %d", &x, &y);
        if (cnt[x+y]==1 && dp1[x][y] && dp2[x][y]) {printf("0\n"); continue;}
        printf("1\n");
        a[x][y] = 1;

        queue<pair<int, int>> q;
        q.emplace(x, y);
        while(!q.empty()){
            auto p = q.front(); q.pop();
            if (!dp1[p.first][p.second]) continue;
            if (!a[p.first][p.second] && (dp1[p.first-1][p.second] || dp1[p.first][p.second-1])) continue;
            dp1[p.first][p.second] = 0;
            if (dp2[p.first][p.second]) cnt[p.first+p.second]--;

            if (p.first+1<=n) q.emplace(p.first+1, p.second);
            if (p.second+1<=m) q.emplace(p.first, p.second+1);
        }

        q.emplace(x, y);
        while(!q.empty()){
            auto p = q.front(); q.pop();
            if (!dp2[p.first][p.second]) continue;
            if (!a[p.first][p.second] && (dp2[p.first+1][p.second] || dp2[p.first][p.second+1])) continue;
            dp2[p.first][p.second] = 0;
            if (dp1[p.first][p.second]) cnt[p.first+p.second]--;

            if (p.first-1>0) q.emplace(p.first-1, p.second);
            if (p.second-1>0) q.emplace(p.first, p.second-1);
        }

        //debug(n, m);
    }
    return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
furniture.cpp:26:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         for (int j=1;j<=m;j++) scanf("%d", a[i]+j);
      |                                ~~~~~^~~~~~~~~~~~~~
furniture.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
furniture.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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