oj.uz

Submission #361734

# Submission time Handle Problem Language Result Execution time Memory
361734 2021-01-31T12:27:16 Z Bill_00 Furniture (JOI20_furniture) C++14
100 / 100
 348 ms 17120 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define N 1005
typedef long long ll;
using namespace std;
bool r[N][N];
int c[N][N];
int a[N*2];
vector<pair<int,int> >v;
void detect(int x,int y){
	r[x][y]=1;
	a[x+y]--;
	if(r[x+1][y-1]==1){
		if(r[x][y-1]==0){
			detect(x,y-1);
		}
		if(r[x+1][y]==0){
			detect(x+1,y);
		}
	}
	if(r[x-1][y+1]==1){
		if(r[x-1][y]==0){
			detect(x-1,y);
		}
		if(r[x][y+1]==0){
			detect(x,y+1);
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin >> c[i][j];
			if(c[i][j]==1) v.pb({i,j});
			a[i+j]++;
		}
	}
	for(int i=0;i<=n+1;i++){
		r[i][0]=1;
		r[i][m+1]=1;
	}
	for(int i=0;i<=m+1;i++){
		r[0][i]=1;
		r[n+1][i]=1;
	}
	for(pair<int,int>fur:v){
		if(r[fur.ff][fur.ss]==0) detect(fur.ff,fur.ss);
	}
	int q;
	cin >> q;
	while(q--){
		int x,y;
		cin >> x >> y;
		if(r[x][y]==1){
			cout << 1 << '\n';
		}
		else{
			if(a[x+y]>1){
				cout << 1 << '\n';
				detect(x,y);
			}
			else cout << 0 << '\n';
		}
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 3 ms 876 KB Output is correct
5 Correct 4 ms 1004 KB Output is correct
6 Correct 4 ms 1004 KB Output is correct
7 Correct 4 ms 1004 KB Output is correct
8 Correct 4 ms 1004 KB Output is correct
9 Correct 4 ms 1004 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 2 ms 876 KB Output is correct
3 Correct 2 ms 876 KB Output is correct
4 Correct 3 ms 876 KB Output is correct
5 Correct 4 ms 1004 KB Output is correct
6 Correct 4 ms 1004 KB Output is correct
7 Correct 4 ms 1004 KB Output is correct
8 Correct 4 ms 1004 KB Output is correct
9 Correct 4 ms 1004 KB Output is correct
10 Correct 10 ms 1004 KB Output is correct
11 Correct 3 ms 748 KB Output is correct
12 Correct 155 ms 6656 KB Output is correct
13 Correct 66 ms 6248 KB Output is correct
14 Correct 286 ms 7276 KB Output is correct
15 Correct 291 ms 7096 KB Output is correct
16 Correct 300 ms 7148 KB Output is correct
17 Correct 329 ms 7404 KB Output is correct
18 Correct 337 ms 7276 KB Output is correct
19 Correct 326 ms 7532 KB Output is correct
20 Correct 323 ms 17120 KB Output is correct
21 Correct 348 ms 16976 KB Output is correct