oj.uz

Submission #1038517

# Submission time Handle Problem Language Result Execution time Memory
1038517 2024-07-29T21:52:59 Z vjudge1 Furniture (JOI20_furniture) C++17
100 / 100
 175 ms 13140 KB 
#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';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 660 KB Output is correct
9 Correct 2 ms 604 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 660 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 5 ms 856 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 85 ms 5888 KB Output is correct
13 Correct 33 ms 3160 KB Output is correct
14 Correct 141 ms 10736 KB Output is correct
15 Correct 144 ms 10992 KB Output is correct
16 Correct 150 ms 12064 KB Output is correct
17 Correct 161 ms 12628 KB Output is correct
18 Correct 155 ms 12208 KB Output is correct
19 Correct 175 ms 12884 KB Output is correct
20 Correct 157 ms 13140 KB Output is correct
21 Correct 172 ms 12868 KB Output is correct