제출 #418785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
418785		MohamedAhmed04	Furniture (JOI20_furniture)	C++14	0 / 100	2 ms	844 KiB

furniture

#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) ;
	}
}

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: 0 / 5
• Subtask 2: 0 / 95