Submission #1269766

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269766		herominhsteve	Furniture (JOI20_furniture)	C++20	0 / 100	1 ms	836 KiB

furniture

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "furniture"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const int MAXN = 1005;

int n,m,q;
int grid[MAXN][MAXN];

bool isBlocked[MAXN][MAXN];
// ? # of unblocked block in the diagonal
int diagCnt[2 * MAXN + 2];

void init(){
	cin>>n>>m;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			cin>>grid[i][j];
			diagCnt[i+j]++;
		}
	}
	cin>>q;
}

bool isValid(int x,int y){
	return (x>=1 and x<=n and y>=1 and y<=m);
}

bool place(int x,int y){
	if (isBlocked[x][y]) return true;
	if (diagCnt[x+y]==1) return false;
	queue<pair<int,int>> qu;
	
	function<void(int,int)> push = [&] (int x,int y) -> void {
		if (!isBlocked[x][y]){
			isBlocked[x][y] = 1;
			diagCnt[x+y]--;
			qu.emplace(x,y);
		}
	};

	push(x,y);
	while (!qu.empty()){
		int newx,newy; tie(newx,newy) = qu.front(); qu.pop();
		if (isValid(newx-1,newy+1) and isBlocked[newx-1][newy+1]){
			push(newx,newy+1);
			push(newx-1,newy);
		}
		if (isValid(newx+1,newy-1) and isBlocked[newx+1][newy-1]){
			push(newx+1,newy);
			push(newx,newy-1);
		}
	}
	return true;
}

void sol(){
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			if (grid[i][j]) place(i,j);
		}
	}
	while (q--){
		int x,y;
		cin>>x>>y;
		cout<<place(x,y)<<el;
	}
}

int main(){
    setup();
    init();
    sol();
}

Compilation message (stderr)

furniture.cpp: In function 'void setup()':
furniture.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
furniture.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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