제출 #709762

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
709762		Antekb	Furniture (JOI20_furniture)	C++17	100 / 100	784 ms	17460 KiB

furniture

#include<bits/stdc++.h>

#define st first
#define nd second
#define eb emplace_back
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

void debug(){cerr<<"\n";}
template<typename H, typename... T>
void debug(H h, T... t){cerr<<h;if(sizeof...(t))cerr<<", ";debug(t...);};
#define deb(x...) cerr<<#x<<" = ";debug(x);

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N=1e3+5, INF=1e9+5;
bool czy[2][N][N], blo[N][N];
bitset<N> S[N], S2[N];
bitset<N> SS[N], SS2[N];
#define dobre(x, y) (czy[0][x][y]&czy[1][x][y])
void upd(int x, int y){
	czy[0][x][y]=(!blo[x][y])&(czy[0][x-1][y]|czy[0][x][y-1]);
	czy[1][x][y]=(!blo[x][y])&(czy[1][x+1][y]|czy[1][x][y+1]);
	S[x][y]=dobre(x, y);
	S2[y][x]=dobre(x, y);
	SS[x][N-y]=dobre(x, y);
	SS2[y][N-x]=dobre(x, y);
}
vector<pii> edg={{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m;
	cin>>n>>m;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			cin>>blo[i][j];
		}
	}
	czy[0][1][0]=1;
	czy[1][n][m+1]=1;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			upd(i, j);
		}
	}
	for(int i=n; i>0; i--){
		for(int j=m; j>0; j--){
			upd(i, j);
		}
	}
	int q;
	cin>>q;
	while(q--){
		int x, y;
		cin>>x>>y;
		/*for(int i=1; i<=n; i++){
			for(int j=1; j<=m; j++){
				cout<<dobre(i, j)<<" \n"[j==m];
			}
		}*/
		if(!dobre(x, y)){
			cout<<1<<"\n";
			continue;
		}
		blo[x][y]=1;
		upd(x, y);
		vector<pii> todo;
		todo.eb(x, y);
		for(int i=x+1; i<=n; i++){
			if(!dobre(i, y))break;
			todo.eb(i, y);
			upd(i, y);
			if(dobre(i, y))break;
		}
		for(int i=x-1; i>=1; i--){
			if(!dobre(i, y))break;
			todo.eb(i, y);
			upd(i, y);
			if(dobre(x, y))break;
		}
		for(int i=y+1; i<=m; i++){
			if(!dobre(x, i))break;
			todo.eb(x, i);
			upd(x, i);
			if(dobre(x, i))break;
		}
		for(int i=y-1; i>=1; i--){
			if(!dobre(x, i))break;
			todo.eb(x, i);
			upd(x, i);
			if(dobre(x, i))break;
		}
		if(S[x].count() && S2[y].count()){
			int mx=S[x]._Find_first();
			int Mx=N-SS[x]._Find_first();

			int my=S2[y]._Find_first();
			int My=N-SS2[y]._Find_first();
			//deb(mx, Mx,my,My);
			if(!(mx>y && my>x) && !(Mx<y && My<x)){
				cout<<1<<"\n";
				for(int i=0; i<todo.size(); i++){
					int xx=todo[i].st, yy=todo[i].nd;
					for(pii e:edg){
						int xxx=xx+e.st, yyy=yy+e.nd;
						if(!(xxx%(n+1)) || !(yyy%(m+1)))continue;
						int sta=czy[0][xxx][yyy]+2*czy[1][xxx][yyy];
						upd(xxx, yyy);
						sta-=czy[0][xxx][yyy]+2*czy[1][xxx][yyy];
						if(sta){
							todo.eb(xxx, yyy);
						}
					}
				}
				continue;
			}
		}
		cout<<0<<"\n";
		blo[x][y]=0;
		for(pii i:todo)upd(i.st, i.nd);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

furniture.cpp: In function 'int main()':
furniture.cpp:109:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int i=0; i<todo.size(); i++){
      |                  ~^~~~~~~~~~~~

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