제출 #1326187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326187		joacru	Furniture (JOI20_furniture)	C++20	100 / 100	571 ms	14340 KiB

furniture

#include <iostream>
#include <algorithm>
#include <vector>

#define forn(i,n) for(int i=0;i<(int)n;++i)

#define DBG(a) cerr<<#a<<" = "<<a<<endl
#define DBGA(a) cerr<<#a<<" = "<<a<<", ";
#define DBG2(a,b) do{DBGA(a)DBG(b);}while(0)
#define DBG3(a,b,c) do{DBGA(a)DBGA(b)DBG(c);}while(0)
#define DBG4(a,b,c,d) do{DBGA(a)DBGA(b)DBGA(c)DBG(d);}while(0)
#define SZ(v) (int)v.size()

using namespace std;

template<typename T>
ostream &operator<<(ostream &os, vector<T> &v){
	os<<"[";
	forn(i,SZ(v)){
		if(i) os<<", ";
		os<<v[i];
	}
	os<<"]";
	return os;
}

const int MAXNM = 1005, DIR = 2;

vector<pair<int,int>> rd = {{0, 1}, {1, 0}};
vector<pair<int,int>> ul = {{-1, 0}, {0, -1}};

typedef vector<vector<int>> Matrix;

int n, m;
Matrix grid, cnt1, cnt2, tch;

bool valid(int r, int c){
	return r>=0&&r<n&&c>=0&&c<m;
}

void erase(int r, int c, vector<pair<int,int>> &v, vector<vector<int>> &cnt){
	if(cnt[r][c] == 0) return;
	--cnt[r][c];
	//~ DBG2(r, c);
	if(cnt[r][c]) return;
	forn(i, SZ(v)){
		int nr = r + v[i].first;
		int nc = c + v[i].second;
		//~ DBG2(nr, nc);
		if(!valid(nr, nc)) continue;
		if(grid[nr][nc]) continue;
		//~ --cnt[nr][nc];
		erase(nr, nc, v, cnt);
	}
}

void erase(int r, int c){
	//~ cnt1[r][c] = 0;
	//~ cnt2[r][c] = 0;
	//~ DBG("erase 1");
	if(cnt1[r][c]) cnt1[r][c] = 1;
	erase(r, c, rd, cnt1);
	//~ DBG("erase 2");
	if(cnt2[r][c]) cnt2[r][c] = 1;
	erase(r, c, ul, cnt2);
}

void add(int r, int c, vector<pair<int,int>> &v, vector<vector<int>> &cnt){
	for(auto x: v){
		int nr = r + x.first;
		int nc = c + x.second;
		if(!valid(nr,nc)) continue;
		if(grid[nr][nc]) continue;
		++cnt[nr][nc];
	}
}

void add1(int r, int c){
	add(r, c, rd, cnt1);
}

void add2(int r, int c){
	add(r, c, ul, cnt2);
}

void solve(){
	
	cin>>n>>m;
	grid = Matrix(n, vector<int>(m));
	cnt1 = Matrix(n, vector<int>(m));
	cnt2 = Matrix(n, vector<int>(m));
	
	forn(i,n) forn(j,m) cin>>grid[i][j];

	cnt1[0][0] = 1;
	cnt2[n-1][m-1] = 1;
	
	forn(i,n) forn(j,m){
		if(grid[i][j]) continue;
		if(!cnt1[i][j]) continue;
		add1(i, j);
	}
	
	for(int i=n-1;i>=0;--i) for(int j=m-1;j>=0;--j){
		if(grid[i][j]) continue;
		if(!cnt2[i][j]) continue;
		add2(i, j);
	}
	
	//~ DBG(cnt1);
	//~ DBG(cnt2);
	
	int q;
	cin>>q;
	while(q--){
		int r, c;
		cin>>r>>c;
		--r, --c;
		// comprobar la diagonal
		if(cnt1[r][c] && cnt2[r][c]){ // candidato
			int x = min(c, n-r-1);
			int i = r+x, j = c-x;
			//~ DBG3(i,j,x);
			x = 0;
			while(i >= 0 && j < m){
				if(cnt1[i][j] && cnt2[i][j]) ++x;
				--i, ++j;
			}
			//~ DBG3(i,j,x);
			if(x == 1){ // solo yo
				cout<<"0\n";
			} else{
				erase(r, c);
				cout<<"1\n";
			}
		} else{
			erase(r, c);
			cout<<"1\n";
		}
		//~ DBG(cnt1);
		//~ DBG(cnt2);
		//~ DBG("============");
	}
	
	cerr<<"==="<<endl;
}

int main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	#ifdef LOCAL
	freopen("input.in", "r", stdin);
	int tcs;
	cin>>tcs;
	while(tcs--)
	#endif
	solve();
	
	return 0;
}

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