Submission #330364

#	Time	Username	Problem	Language	Result	Execution time	Memory
330364		YJU	Furniture (JOI20_furniture)	C++14	0 / 100	4 ms	1024 KiB

furniture

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll N=1e3+5;
const ll K=350;
const ld pi=3.14159265359;
const ll INF=(1LL<<40);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,m,vis[N][N],d[4*N*N],ck[4*N*N],q,x,y;
ll di[8]={1,1,1,0,-1,-1,-1,0};
ll dj[8]={-1,0,1,1,1,0,-1,-1};

ll id(ll a,ll b){
	return (a*(m+2)+b);
}

ll f(ll id){
	return (d[id]==id?id:d[id]=f(d[id]));
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP1(ii,id(n+1,m+1))d[ii]=ii;
	//REP(i,n+2)REP(j,m+2)cout<<setw(2)<<id(i,j)<<(j==m+1?"\n":" ");
	REP1(j,m){
		vis[0][j]=vis[n+1][j]=1;
		if(j>1)d[f(id(0,j))]=f(id(0,j-1)),d[f(id(n+1,j))]=f(id(n+1,j-1));
	}
	REP1(i,n){
		vis[i][0]=vis[i][m+1]=1;
		if(i>1)d[f(id(i,0))]=f(id(i-1,0)),d[f(id(i,m+1))]=f(id(i-1,m+1));
	}
	ll left=id(1,0),right=id(1,m+1),up=id(0,1),down=id(n+1,1);
	REP1(i,n)REP1(j,m){
		cin>>vis[i][j];
		if(!vis[i][j])continue;
		REP(k,8){
			ll ni=i+di[k],nj=j+dj[k];
			if(vis[ni][nj]){
				d[f(id(ni,nj))]=f(id(i,j));
			}
		}
	}
	cin>>q;
	while(q--){
		ll ans=1;
		vector<ll> lis;
		
		cin>>x>>y;
		if(vis[x][y]){ans=0;}
		REP(k,8){
			ll ni=x+di[k],nj=y+dj[k];
			ck[f(id(ni,nj))]=1;lis.pb(f(id(ni,nj)));
		}
		if((ck[f(up)]&&ck[f(left)])||(ck[f(up)]&&ck[f(down)]))ans=0;
		if((ck[f(right)]&&ck[f(left)])||(ck[f(right)]&&ck[f(down)]))ans=0;
		if(ans){
			vis[x][y]=1;
			REP(k,8){
				ll ni=x+di[k],nj=y+dj[k];
				if(vis[ni][nj])d[f(id(ni,nj))]=f(id(x,y));
			}
		}
		cout<<ans<<"\n";
		//REP(i,n+2)REP(j,m+2)cout<<setw(2)<<f(id(i,j))<<(j==m+1?"\n":" ");
		for(ll i:lis)ck[i]=0;
	}
	return 0;
}

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