제출 #1326045

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326045		joacru	Furniture (JOI20_furniture)	C++20	5 / 100	5092 ms	40768 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;
const int rv[DIR] = {0, 1};
const int cv[DIR] = {1, 0};

typedef vector<vector<int>> Matrix;

int n, m;
Matrix grid, cnt;

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

vector<pair<int&,int>> rb;

void assign(int &a, int b){
	rb.push_back({a,a});
	a = b;
}

void reset(){
	rb.clear();
}

void undo(){
	while(SZ(rb)){
		int &a = rb.back().first, b = rb.back().second;
		rb.pop_back();
		a = b;
	}
}

void erase(int r, int c){
	if(cnt[r][c] != 0) return;
	//~ DBG2(r, c);
	forn(i, DIR){
		int nr = r + rv[i];
		int nc = c + cv[i];
		//~ DBG2(nr, nc);
		if(!valid(nr, nc)) continue;
		assign(cnt[nr][nc], cnt[nr][nc]-1);
		erase(nr, nc);
	}
}

int main(){
	
	#ifdef LOCAL
	freopen("input.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>n>>m;
	grid.resize(n, vector<int>(m));
	forn(i,n) forn(j,m) cin>>grid[i][j];
	
	// poner los contadores
	
	cnt.resize(n, vector<int>(m));

	cnt[0][0] = 1;
	
	forn(i,n) forn(j,m){
		if(grid[i][j]) continue;
		if(!cnt[i][j]) continue;
		forn(k, DIR){
			int nr = i + rv[k];
			int nc = j + cv[k];
			if(!valid(nr, nc)) continue;
			if(grid[nr][nc]) continue;
			cnt[nr][nc]++;
		}
	}
	
	int q;
	cin>>q;
	//~ DBG(cnt);
	while(q--){
		//~ DBG(q);
		reset();
		int r, c;
		cin>>r>>c;
		--r, --c;
		if(cnt[r][c] != 0){
			assign(cnt[r][c], 0);
			erase(r, c);
		}
		if(cnt[n-1][m-1]){
			cout<<"1\n";
		} else{
			cout<<"0\n";
			undo();
		}
		//~ DBG(cnt);
	}
	
	return 0;
}

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