Submission #876360

#	Time	Username	Problem	Language	Result	Execution time	Memory
876360		vjudge1	Furniture (JOI20_furniture)	C++17	5 / 100	5014 ms	12976 KiB

furniture

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back //emplace_back
#define pp pop_back
#define pii pair<ll, ll> //pair<int, int>
#define all(x) (x).begin(),(x).end()
#define mp(a,b) make_pair(a , b)
#define lb lower_bound
#define ub upper_bound
#define sz(x) (ll)(x).size()
#define F first
#define S second
#define bg(x) (x).begin()
#define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
#define debug(x) cout << #x << " : " << x << endl
#define endl (char)(10)
#define arr(x) array<int , (x)>
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);
     
ll Sum(ll a , ll b , ll MOD)
{
    a %= MOD;
    b %= MOD;
    a += b;
    return a % MOD;
}
     
ll Mul(ll a , ll b , ll MOD)
{
    a %= MOD;
    b %= MOD;
    a *= b;
    return a % MOD;
}
     
ll Pow(ll a , ll b , ll MOD)
{
    ll res = 1;
    while(b)
    {
        if((b & 1))res = Mul(res , a , MOD);
        a = Mul(a , a , MOD);
        b >>= 1;
    }
    return res;
}
     
ll Min(ll a , ll b)
{
    if(a > b)return b;
    return a;
}
     
ll Max(ll a , ll b)
{
    if(a > b)return a;
    return b;
}
     
ll Ceil(ll a , ll b)
{
    if(a % b)return (a/b)+1;
    return a/b;
}
     
/////////////////////
//VALS
ll n, m, q;
const ll maxn = 1100;

bool a[maxn][maxn];
ll b[maxn][maxn];

/////////////////////
//FUNCTIONS
bool chk(ll aa, ll bb)
{
	if(aa == n-1 and bb == m-1)return 1;
	if(b[aa][bb] > -1)return b[aa][bb];
	if(a[aa][bb] == 1)return 0;
	ll ans = 0;
	if(aa+1 != n)
	if(chk(aa+1,bb))ans = 1;
	if(bb+1 != m)
	if(chk(aa,bb+1))ans = 1;

	return b[aa][bb] = ans;
}
/////////////////////
//SOLVE
void solve()
{
	cin >> n >> m;

	For(i,n)
		For(j,m)
			cin >> a[i][j];

	cin >> q;

	while(q--)
	{
			For(i,n)
				For(j,m)
					b[i][j] = -1;
			
			ll aa,bb;
			cin >> aa >> bb;
			aa--;
			bb--;

			a[aa][bb] = 1;
			if(chk(0,0))cout << 1 << endl;
			else
			{
				cout << 0 << endl;
				a[aa][bb] = 0;
			}

	}
}
/////////////////////
//MAIN
int main()
{
    FAST;
    ll t = 1;
//    cin >> t;
    while(t--)
    {
    solve();
    }
}
/////////////////////
/*
ZZZZZZZ     A        M     M     IIIIIII  N     N
     Z     A A      M M   M M       I     NN    N
    Z     A   A    M   M M   M      I     N N   N
   Z     AAAAAAA  M     M     M     I     N  N  N
  Z      A     A  M           M     I     N   N N
 Z       A     A  M           M     I     N    NN
ZZZZZZZ  A     A  M           M  IIIIIII  N     N  TREE
*/

Compilation message (stderr)

furniture.cpp: In function 'bool chk(long long int, long long int)':
furniture.cpp:94:19: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   94 |  return b[aa][bb] = ans;
      |         ~~~~~~~~~~^~~~~
furniture.cpp: In function 'void solve()':
furniture.cpp:19:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   19 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
furniture.cpp:102:2: note: in expansion of macro 'For'
  102 |  For(i,n)
      |  ^~~
furniture.cpp:19:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   19 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
furniture.cpp:103:3: note: in expansion of macro 'For'
  103 |   For(j,m)
      |   ^~~
furniture.cpp:19:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   19 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
furniture.cpp:110:4: note: in expansion of macro 'For'
  110 |    For(i,n)
      |    ^~~
furniture.cpp:19:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   19 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
furniture.cpp:111:5: note: in expansion of macro 'For'
  111 |     For(j,m)
      |     ^~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 95