Submission #296920

#	Time	Username	Problem	Language	Result	Execution time	Memory
296920		nafis_shifat	Furniture (JOI20_furniture)	C++14	100 / 100	550 ms	19748 KiB

furniture

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;
int a[1002][1002]={};

int cnt[3000]={};

int di[]={0,0,-1,1};
int dj[]={-1,1,0,0};
bool f=false;
int n,m;
vector<pii> v;
void dfs(int i,int j) {
	if(a[i][j]) return;

	int v1=a[i][j+1]+a[i+1][j];
	int v2=a[i-1][j]+a[i][j-1];

	if(v1!=2 && v2!=2) return;

	a[i][j]=1; 
	cnt[i+j]--;
	
	v.push_back({i,j});

	if(i==1 && j==1) {
	    a[i][j]=0;
	    if(v1==2) {
		    f=true;
	    }
	    return;
	}
	
	if(i==n && j==m) {
	    a[i][j]=0;
	    if(v2==2) {
	        f=true;
	    }
	    return;
	}
	
	

	for(int k=0;k<4;k++) {
		int ii=i+di[k];
		int jj=j+dj[k];
		dfs(ii,jj);
	}



}

int main() {

	cin>>n>>m;

	for(int i=0;i<=m+1;i++) {
		a[0][i]=1;
		a[n+1][i]=1;
	}
	for(int i=0;i<=n+1;i++) {
		a[i][0]=a[i][m+1]=1;
	}

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


	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			int x;
			scanf("%d",&x);
			if(!x) continue;
			a[i][j]=x;

			for(int k=0;k<4;k++) {
				int ii=i+di[k];
				int jj=j+dj[k];
				dfs(ii,jj);
			}
		}
	}
	


	int q;
	cin>>q;

	while(q--) {
	    v.clear();
		int i,j;
		scanf("%d%d",&i,&j);

		if(a[i][j]==1) {
			printf("1\n");
			continue;
		}
		if(cnt[i+j]==1) {
			printf("0\n");
			continue;
		}
		f=false;

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

		for(int k=0;k<4;k++) {
			int ii=i+di[k];
			int jj=j+dj[k];
			dfs(ii,jj);
		}
		if(f) {
		    
			printf("0\n");
			a[i][j]=0;
			cnt[i+j]++;
			
			for(pii x:v) {
			    a[x.first][x.second]=0;
			    cnt[x.first+x.second]++;
			}

		} else {
			printf("1\n");
		}

	}
	
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:75:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |    scanf("%d",&x);
      |    ~~~~~^~~~~~~~~
furniture.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |   scanf("%d%d",&i,&j);
      |   ~~~~~^~~~~~~~~~~~~~

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