oj.uz

Submission #709748

# Submission time Handle Problem Language Result Execution time Memory
709748 2023-03-14T11:26:58 Z Antekb Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 83032 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

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1108 KB Output is correct
2 Correct 8 ms 852 KB Output is correct
3 Correct 21 ms 1108 KB Output is correct
4 Correct 24 ms 1332 KB Output is correct
5 Correct 27 ms 1440 KB Output is correct
6 Correct 56 ms 1732 KB Output is correct
7 Correct 33 ms 1748 KB Output is correct
8 Correct 28 ms 1796 KB Output is correct
9 Correct 26 ms 1764 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1108 KB Output is correct
2 Correct 8 ms 852 KB Output is correct
3 Correct 21 ms 1108 KB Output is correct
4 Correct 24 ms 1332 KB Output is correct
5 Correct 27 ms 1440 KB Output is correct
6 Correct 56 ms 1732 KB Output is correct
7 Correct 33 ms 1748 KB Output is correct
8 Correct 28 ms 1796 KB Output is correct
9 Correct 26 ms 1764 KB Output is correct
10 Correct 51 ms 1100 KB Output is correct
11 Correct 25 ms 1236 KB Output is correct
12 Correct 4019 ms 79060 KB Output is correct
13 Correct 688 ms 55188 KB Output is correct
14 Execution timed out 5046 ms 83032 KB Time limit exceeded
15 Halted 0 ms 0 KB -