Submission #1326453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326453		vtnoo	Furniture (JOI20_furniture)	C++20	0 / 100	5 ms	4664 KiB

furniture

#include <bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define all(x) x.begin(), x.end()
#define sz(a) ((int) a.size())
#define pb push_back
#define fst first
#define snd second
using namespace std;
typedef long long ll;
const int N=1005;
int C[N][N],alc[N][N],cntDiag[N*2],szDiag[N*2],n,m;
bool safe(int i,int j){
	return i>=0&&i<n&&j>=0&&j<m;
}
bool bck(int x,int y){
	if(!safe(x,y))return false;
    if(C[x][y]==1)return (alc[x][y]=0);
	if(alc[x][y]!=-1)return alc[x][y];
    if(x==n-1&&y==m-1)return (alc[x][y] = 1);
    bool reach=false;
    if(safe(x+1,y)&&C[x+1][y]==0){
        if(bck(x+1,y))reach=true;
    }
    if(safe(x,y+1)&&C[x][y+1]==0){
        if(bck(x,y+1))reach=true;
    }
    alc[x][y]=reach?1:0;
    return alc[x][y];
}
void act(int x,int y){
	if(safe(x+1,y-1)&&alc[x+1][y]&&!alc[x+1][y-1]){
		alc[x+1][y]=0;
		cntDiag[x+y+1]--;
		act(x+1,y);
	}
	if(safe(x-1,y+1)&&alc[x][y+1]&&!alc[x-1][y+1]){
		alc[x][y+1]=0;
		cntDiag[x+y+1]--;
		act(x,y+1);
	}
}
int main(){
	ios::sync_with_stdio(false); 
	cin.tie(nullptr);
	cin>>n>>m;
	L(i,0,n-1)L(j,0,m-1){
		cin>>C[i][j];
	}
	memset(alc,-1,sizeof(alc));
	bck(0,0);
	L(i,0,n-1)L(j,0,m-1){
		if(alc[i][j]==-1)alc[i][j]=0;
		//~ cout<<alc[i][j]<<" ";
		//~ if(j==m-1)cout<<endl;
		cntDiag[i+j]+=alc[i][j];
	}
	L(i,0,m-1){
		int x=0,y=i,cnt=0;
		while(safe(x+1,y-1)){
			cnt++;
			x++;y--;
		}
		szDiag[i]=cnt+1;
	}
	L(i,1,n-1){
		int x=i,y=m-1,cnt=0;
		while(safe(x+1,y-1)){
			cnt++;
			x++;y--;
		}
		szDiag[m+i-1]=cnt+1;
	}
	//~ L(i,0,n+m-2){
		//~ cout<<cntDiag[i]<<" "<<szDiag[i]<<endl;
	//~ }
	//~ cout<<"=========="<<endl;
	int q;cin>>q;
	while(q--){
		int x,y;cin>>x>>y;
		x--;y--;
		if(alc[x][y]==0){
			cout<<1<<endl;
			continue;
		}
		alc[x][y]=0;
		//~ cout<<cntDiag[x+y]<<" "<<szDiag[x+y]<<endl;
		if(cntDiag[x+y]-1==0){
			//~ cout<<"TAPO CAMINO"<<endl;
			cout<<0<<endl;
		}else{
			//~ cout<<"EXISTE CAMINO"<<endl;
			cntDiag[x+y]--;
			cout<<1<<endl;
			act(x,y);
		}
	}
}

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