Submission #301087

#	Time	Username	Problem	Language	Result	Execution time	Memory
301087		milisav	Furniture (JOI20_furniture)	C++14	100 / 100	560 ms	19192 KiB

furniture

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define maxn 1010
using namespace std;
bool p1[maxn][maxn];
bool p2[maxn][maxn];
bool tp[maxn][maxn];
int tc[2*maxn];
int n,m;
int c[maxn][maxn];
int q;
int x,y;
void rec1(int u,int v) {
    if(!p1[u][v]) return;
    if(c[u][v]==0) {
        if(u==1 && v==1) p1[u][v]=true;
        else {
            if(u==1) p1[u][v]=p1[u][v-1];
            else {
                if(v==1) p1[u][v]=p1[u-1][v];
                else p1[u][v]=p1[u-1][v]||p1[u][v-1];
            }
        }
    }
    else p1[u][v]=false;
    if(p1[u][v]) return;
    if(p2[u][v]) {
        tp[u][v]=false;
        tc[u+v]--;
    }
    if(u<n) rec1(u+1,v);
    if(v<m) rec1(u,v+1);
}
void rec2(int u,int v) {
    if(!p2[u][v]) return;
    if(c[u][v]==0) {
        if(u==n && v==m) p2[u][v]=true;
        else {
            if(u==n) p2[u][v]=p2[u][v+1];
            else {
                if(v==m) p2[u][v]=p2[u+1][v];
                else p2[u][v]=p2[u+1][v]||p2[u][v+1];
            }
        }
    }
    else p2[u][v]=false;
    if(p2[u][v]) return;
    if(p1[u][v]) {
        tp[u][v]=false;
        tc[u+v]--;
    }
    if(u>1) rec2(u-1,v);
    if(v>1) rec2(u,v-1);
}
int main() {
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            scanf("%d",&c[i][j]);
        }
	}
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(c[i][j]==1) continue;
            if(i==1 && j==1) {
                p1[i][j]=true;
                continue;
            }
            if(i==1) p1[i][j]=p1[i][j-1];
            else {
                if(j==1) p1[i][j]=p1[i-1][j];
                else p1[i][j]=p1[i][j-1]||p1[i-1][j];
            }
        }
    }
    for(int i=n;i>=1;i--) {
        for(int j=m;j>=1;j--) {
            if(c[i][j]==1) continue;
            if(i==n && j==m) {
                p2[i][j]=true;
                continue;
            }
            if(i==n) p2[i][j]=p2[i][j+1];
            else {
                if(j==m) p2[i][j]=p2[i+1][j];
                else p2[i][j]=p2[i][j+1]||p2[i+1][j];
            }
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(p1[i][j] && p2[i][j]) {
                tp[i][j]=true;
                tc[i+j]++;
            }
        }
    }
    scanf("%d",&q);
    while(q--) {
        scanf("%d %d",&x,&y);
        if(tp[x][y] && tc[x+y]==1) printf("0\n");
        else {
            printf("1\n");
            c[x][y]=1;
            if(p1[x][y]) rec1(x,y);
            if(p2[x][y]) rec2(x,y);
        }
    }
	return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |  scanf("%d %d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
furniture.cpp:59:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |             scanf("%d",&c[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~
furniture.cpp:98:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
furniture.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  100 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~

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