oj.uz

답안 #709750

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
709750 2023-03-14T11:27:59 Z Antekb Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 84544 KB 
#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];
set<int> S[N], S2[N];
#define dobre(x, y) (czy[0][x][y]&czy[1][x][y])
void upd(int x, int y){
	if(dobre(x, y))S[x].erase(y);
	if(dobre(x, y))S2[y].erase(x);
	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]);
	if(dobre(x, y))S[x].insert(y);
	if(dobre(x, y))S2[y].insert(x);
}
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].size() && S2[y].size()){
			int mx=*S[x].begin(), Mx=*(--S[x].end());
			int my=*S2[y].begin(), My=*(--S2[y].end());
			//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);
	}
}

Compilation message

furniture.cpp: In function 'int main()':
furniture.cpp:105: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]
  105 |     for(int i=0; i<todo.size(); i++){
      |                  ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 1108 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 9 ms 1188 KB Output is correct
4 Correct 15 ms 1336 KB Output is correct
5 Correct 15 ms 1416 KB Output is correct
6 Correct 45 ms 1688 KB Output is correct
7 Correct 17 ms 1716 KB Output is correct
8 Correct 14 ms 1688 KB Output is correct
9 Correct 10 ms 1748 KB Output is correct

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 1108 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 9 ms 1188 KB Output is correct
4 Correct 15 ms 1336 KB Output is correct
5 Correct 15 ms 1416 KB Output is correct
6 Correct 45 ms 1688 KB Output is correct
7 Correct 17 ms 1716 KB Output is correct
8 Correct 14 ms 1688 KB Output is correct
9 Correct 10 ms 1748 KB Output is correct
10 Correct 18 ms 952 KB Output is correct
11 Correct 16 ms 1284 KB Output is correct
12 Correct 3557 ms 77092 KB Output is correct
13 Correct 585 ms 53624 KB Output is correct
14 Correct 3607 ms 75880 KB Output is correct
15 Execution timed out 5035 ms 84544 KB Time limit exceeded
16 Halted 0 ms 0 KB -