Submission #1038517

#TimeUsernameProblemLanguageResultExecution timeMemory
1038517vjudge1Furniture (JOI20_furniture)C++17
100 / 100
175 ms13140 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; #define pb push_back #define pf push_front #define fi first #define se second const ll mod = 1e9+7, mxn = 1007; bool blocked[mxn][mxn]; ll dia[mxn<<1], n, m; void block(ll i, ll j) { blocked[i][j] = 1; dia[i+j]--; if ((i-1 >= 1 && !blocked[i-1][j])) { if (i-1 >= 1 && j+1 <= m) {if (blocked[i-1][j+1]) block(i-1,j);} else block(i-1,j); } if ((i+1 <= n && !blocked[i+1][j])) { if (i+1 <= n && j-1 >= 1) {if (blocked[i+1][j-1]) block(i+1,j);} else block(i+1,j); } if ((j-1 >= 1 && !blocked[i][j-1])) { if (i+1 <= n && j-1 >= 1) {if (blocked[i+1][j-1]) block(i,j-1);} else block(i,j-1); } if ((j+1 <= m && !blocked[i][j+1])) { if (i-1 >= 1 && j+1 <= m) {if (blocked[i-1][j+1]) block(i,j+1);} else block(i,j+1); } } bool ck(ll i, ll j) { if (dia[i+j] == 1 && !blocked[i][j]) return 0; if (blocked[i][j]) return 1; block(i,j); return 1; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr); cin >> n >> m; // cerr << n << ' ' << m << '\n'; for (ll i = 1; i <= n; i++) for (ll j = 1; j <= m; j++) dia[i+j]++; for (ll i = 1; i <= n; i++) for (ll j = 1; j <= m; j++) {ll x; cin >> x; if (x) ck(i,j);} ll q; cin >> q; while (q--) { ll x, y; cin >> x >> y; if (ck(x,y)) cout << 1 << '\n'; else cout << '0' << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...