Submission #715978

#	Time	Username	Problem	Language	Result	Execution time	Memory
715978		KiaRez	Furniture (JOI20_furniture)	C++17	0 / 100	8 ms	5460 KiB

furniture

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<int, pii> ipii;
typedef pair<pii, int> piii;
typedef pair<ll, pll> lpll;
typedef pair<pll, ll> plll;
typedef pair<pii, pii> piipii;
typedef pair<pll, pll> pllpll;
typedef long double ld;

#define SQ									   350
#define endl                                   '\n'
#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define PQ                                     priority_queue
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define set_dec(x)	                           cout << fixed << setprecision(x);
#define ios				                       ios_base::sync_with_stdio(false), cin.tie(0)
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define file_io(x,y)	                       freopen(x, "r", stdin); freopen(y, "w", stdout);

const int N = 1005, lg=18;
const ll MOD = 1e9+7; // 998244353

ll getmod(ll a, ll mod=MOD)                   {return (a>=0&&a<mod ? a : ((a%mod+mod)%mod));}
ll max(ll a, ll b)                             {return (a>b ? a : b);}
ll min(ll a, ll b)                             {return (a<b ? a : b);}
ll abso(ll a)                                  {return (a<0?-a:a);}
inline ll poww(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = getmod(ans*a);
        b >>= 1;
        a = getmod(a*a);
    }
    return ans;
}

int n, m, q, A[N][N], cnt[N], dp[N][N], pd[N][N], mark[N][N], OK[N][N];
int dx[4]={0, 0, 1, -1}, dy[4]={1, -1, 0, 0};
int main () {
	ios;

	cin>>n>>m;
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=m; ++j) {
			cin>>mark[i][j];
		}
	}
	for(int i=0;i<N;++i) {
		mark[n+1][i]=mark[0][i]=mark[i][m+1]=mark[i][0]=1;
	}

	pd[n][m]=dp[1][1]=1;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j){
			dp[i][j]|=(dp[i-1][j] && mark[i-1][j]==0 && mark[i][j]==0);
			dp[i][j]|=(dp[i][j-1] && mark[i][j-1]==0 && mark[i][j]==0);
		}
	}
	for(int i=n;i;--i) {
		for(int j=m;j;--j){
			pd[i][j]|=(pd[i+1][j] && mark[i+1][j]==0 && mark[i][j]==0);
			pd[i][j]|=(pd[i][j+1] && mark[i][j+1]==0 && mark[i][j]==0);
			if(pd[i][j] == dp[i][j] && pd[i][j] == 1) {
				OK[i][j]=1;
				cnt[i+j]++;
			}
		}
	}

	cin>>q;
	while(q--) {
		int x,y;
		cin>>x>>y;
		if(cnt[x+y]==1) {
			cout<<"0\n";
			continue;
		}
		cout<<"1\n";
		if(OK[x][y] == 0){
			continue;
		}
		queue<pii> q;
		q.push({x, y});
		mark[x][y]=1;
		while(!q.empty()) {
			pii v = q.front();
			q.pop();
			cnt[v.F+v.S]--;
			dp[v.F][v.S] = pd[v.F][v.S] = OK[v.F][v.S] = 0;
			for(int i=0;i<4;++i) {
				int a=v.F+dx[i], b=v.S+dy[i];
				if(Mp(a,b)==Mp(1,1) || Mp(a,b)==Mp(n,m)) {
					continue;
				}
				if(mark[a][b]==0 && OK[a][b]==1 && ((dp[a-1][b]==0&&dp[a][b-1]==0) || (pd[a+1][b]==0&&pd[a][b+1]==0))) {
					dp[a][b]=pd[a][b]=OK[a][b]=0;
					q.push({a,b});
				}
			}
		}
	}

	return 0;
}

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