oj.uz

답안 #418787

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
418787 2021-06-05T21:45:08 Z MohamedAhmed04 Furniture (JOI20_furniture) C++14
100 / 100
 692 ms 63040 KB 
#include <bits/stdc++.h>

using namespace std ;

const int MAX = 1e3 + 10 ;

int arr[MAX][MAX] ;
int n , m ;

set<int>s[MAX] ;

void upd(int i , int j)
{
	if(arr[i][j-1] == 0 && arr[i+1][j-1] == 1)
	{
		s[i].erase(j-1) ;
		arr[i][j-1] = 1 ;
		upd(i , j-1) ;
	}
	if(arr[i-1][j] == 0 && arr[i-1][j+1] == 1)
	{
		s[i-1].erase(j) ;
		arr[i-1][j] = 1 ;
		upd(i-1 , j) ;
	}
	if(arr[i][j+1] == 0 && arr[i-1][j+1] == 1)
	{
		s[i].erase(j+1) ;
		arr[i][j+1] = 1 ;
		upd(i , j+1) ;
	}
	if(arr[i+1][j] == 0 && arr[i+1][j-1] == 1)
	{
		s[i+1].erase(j) ;
		arr[i+1][j] = 1 ;
		upd(i+1 , j) ;
	}
}

bool check(int i , int j)
{
	int x = 1e9 , y = -1e9 ;
	if(s[i+1].size())
		x = *s[i+1].begin() ;
	if(s[i-1].size())
		y = *s[i-1].rbegin() ;
	return (x < j || y > j) ;
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m ;
	for(int i = 0 ; i <= n+1 ; ++i)
	{
		for(int j = 0 ; j <= m+1 ; ++j)
			arr[i][j] = 1 ;
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 1 ; j <= m ; ++j)
			cin>>arr[i][j] ;
	}
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int j = 1 ; j <= m ; ++j)
		{
			if(arr[i][j] == 0)
				s[i].insert(j) ;
		}
	}
	for(int i = n ; i >= 1 ; --i)
	{
		for(int j = m ; j >= 1 ; --j)
		{
			if(arr[i][j] == 1)
				upd(i , j) ;
		}
	}
	int q ;
	cin>>q ;
	while(q--)
	{
		int i , j ;
		cin>>i>>j ;
		if(arr[i][j] == 1)
			cout<<1<<"\n" ;
		else if(check(i , j))
		{
			cout<<1<<"\n" ;
			arr[i][j] = 1 , s[i].erase(j) ;
			upd(i , j) ;
		}
		else
			cout<<0<<"\n" ;
	}
	return 0 ;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 844 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 4 ms 1100 KB Output is correct
4 Correct 5 ms 1228 KB Output is correct
5 Correct 6 ms 1228 KB Output is correct
6 Correct 6 ms 1228 KB Output is correct
7 Correct 6 ms 1228 KB Output is correct
8 Correct 6 ms 1224 KB Output is correct
9 Correct 8 ms 1336 KB Output is correct

Subtask #2
95.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 844 KB Output is correct
2 Correct 2 ms 844 KB Output is correct
3 Correct 4 ms 1100 KB Output is correct
4 Correct 5 ms 1228 KB Output is correct
5 Correct 6 ms 1228 KB Output is correct
6 Correct 6 ms 1228 KB Output is correct
7 Correct 6 ms 1228 KB Output is correct
8 Correct 6 ms 1224 KB Output is correct
9 Correct 8 ms 1336 KB Output is correct
10 Correct 21 ms 3168 KB Output is correct
11 Correct 5 ms 1100 KB Output is correct
12 Correct 520 ms 50612 KB Output is correct
13 Correct 231 ms 41792 KB Output is correct
14 Correct 692 ms 52936 KB Output is correct
15 Correct 682 ms 53496 KB Output is correct
16 Correct 558 ms 57944 KB Output is correct
17 Correct 644 ms 60980 KB Output is correct
18 Correct 684 ms 59460 KB Output is correct
19 Correct 593 ms 62924 KB Output is correct
20 Correct 534 ms 63032 KB Output is correct
21 Correct 556 ms 63040 KB Output is correct