oj.uz

Submission #422728

# Submission time Handle Problem Language Result Execution time Memory
422728 2021-06-10T11:18:31 Z Jasiekstrz Furniture (JOI20_furniture) C++17
100 / 100
 428 ms 20924 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e3;
vector<pair<int,int>> moves[2]={{{1,0},{0,1}},{{-1,0},{0,-1}}};
bool tab[N+10][N+10];
int ways[N+10][N+10][2];
int cnt[3*N+10];
void del(int x,int y,bool t)
{
	if(ways[x][y][t]==0)
		return;
	ways[x][y][t]=0;
	if(ways[x][y][!t]>0)
		cnt[x+y]--;
	for(auto mv:moves[t])
	{
		int vx=x+mv.fi,vy=y+mv.se;
		if(ways[vx][vy][t]==0)
			continue;
		if(ways[vx][vy][t]==1)
			del(vx,vy,t);
		else
			ways[vx][vy][t]--;
	}
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cnt[i+j]++;
			ways[i][j][0]=ways[i][j][1]=2;
			if(i==1 || j==1)
				ways[i][j][0]=1;
			if(i==n || j==m)
				ways[i][j][1]=1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>tab[i][j];
			if(tab[i][j])
			{
				del(i,j,0);
				del(i,j,1);
			}
		}
	}
	//for(int i=2;i<=n+m;i++)
	//	cerr<<"i+j="<<i<<" -> "<<cnt[i]<<"\n";
	//for(int i=1;i<=n;i++)
	//{
	//	for(int j=1;j<=m;j++)
	//		cerr<<"("<<ways[i][j][0]<<","<<ways[i][j][1]<<")"<<" \n"[j==m];
	//}
	int q;
	cin>>q;
	while(q--)
	{
		int a,b;
		cin>>a>>b;
		if(cnt[a+b]>1 || ways[a][b][0]==0 || ways[a][b][1]==0)
		{
			cout<<"1\n";
			if(ways[a][b][0]>0)
				del(a,b,0);
			if(ways[a][b][1]>0)
				del(a,b,1);
		}
		else
			cout<<"0\n";
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 4 ms 972 KB Output is correct
5 Correct 5 ms 972 KB Output is correct
6 Correct 4 ms 972 KB Output is correct
7 Correct 4 ms 976 KB Output is correct
8 Correct 4 ms 1100 KB Output is correct
9 Correct 4 ms 972 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 4 ms 972 KB Output is correct
5 Correct 5 ms 972 KB Output is correct
6 Correct 4 ms 972 KB Output is correct
7 Correct 4 ms 976 KB Output is correct
8 Correct 4 ms 1100 KB Output is correct
9 Correct 4 ms 972 KB Output is correct
10 Correct 13 ms 1212 KB Output is correct
11 Correct 3 ms 724 KB Output is correct
12 Correct 236 ms 13876 KB Output is correct
13 Correct 95 ms 10708 KB Output is correct
14 Correct 380 ms 18208 KB Output is correct
15 Correct 381 ms 18408 KB Output is correct
16 Correct 390 ms 19432 KB Output is correct
17 Correct 428 ms 20396 KB Output is correct
18 Correct 391 ms 19908 KB Output is correct
19 Correct 422 ms 20752 KB Output is correct
20 Correct 370 ms 20924 KB Output is correct
21 Correct 411 ms 20736 KB Output is correct